如何让 SortedSet 更新旧值的位置？

Question

我有以下对象，我想将其保存在插入时排序且不包含重复项的容器中，因此我使用的是 SortedSet

from sortedcontainers import SortedSet, SortedList


class R():

    def __hash__(self):
        return hash(self.person_id)

    def __eq__(self, other):
        return self.__class__ == other.__class__ and self.person_id == other.person_id

    def __nq__(self, other):
        return not (self == other)

    def __lt__(self, other):
        return other.value < self.value

    def __init__(self, person_id, value):
        self.person_id = person_id
        self.value = value

    def __repr__(self):
        return "person: %s (%s)" % (self.person_id, self.value)

x = SortedSet()

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))

print(x)

当我运行这段代码时，我按预期得到以下输出：

SortedSet([person: 11 (21), person: 17 (4), person: 13 (2), person: 7 (-41)])

但是，如果我添加了一个额外的重复元素，即 17:

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))
x.add(R(17, -67))

print(x)

我希望将名为 person: 17 (4) 的 ID 为 17 的 R 对象移动到后面，其值为 person: 17 (-67)，例如：

SortedSet([person: 11 (21), person: 13 (2), person: 7 (-41), person: 17 (-67)])

但是没有任何变化：

SortedSet([person: 11 (21), person: 17 (4), person: 13 (2), person: 7 (-41)])

如何使用 SortedSet 或任何其他在插入时排序且没有重复的容器来实现所需的输出？

Answer 1

您可以继承 SortedSet，覆盖它的 add 和 remove 方法。我们需要覆盖 remove，因为原始实现使用 self._list.remove，这将失败，因为两个 R 对象不会被识别为相等。

class MySortedSet(SortedSet):
    def add(self, value):
        if value in self:
            self.remove(value)
        super().add(value)

    def remove(self, value):
        self._set.remove(value)
        for index, e in enumerate(self._list[:]):
            if hash(e) == hash(value):
                self._list.pop(index)
                break


x = MySortedSet()

x.add(R(13, 2))
x.add(R(17, 4))
x.add(R(11, 21))
x.add(R(7, -41))
x.add(R(17, -67))

print(x)

产出

MySortedSet([person: 11 (21), person: 13 (2), person: 7 (-41), person: 17 (-67)])

Answer 2

，但我要在这里发出一个框架挑战：这是一个糟糕的设计。

集合（逻辑构造）旨在存储独特的项目。如果 add 编辑到集合中的某物等于其中已有的东西，则没有理由替换旧项目，因为旧项目和新项目等价。如果您的 class 没有使用等式的定义，其中等式意味着可替换性（两个相等的实例可以在所有相关方式中互换使用），那么这些实例不适合在 set 中使用。即使没有 SortedSet 参与，使用普通的 set，这也行不通，因为当您插入“相等”项目时，set.add 不会替换项目；毕竟它们都是等价的，那么为什么要做额外的工作呢？

当您需要一个可以映射到值的键的概念时，可以在不知道原始值的情况下更改给定键的值，您需要一个映射（dict-like） , 不是集合 (set-like).

你想要的可能已经存在于 sortedcollections 包 (ValueSortedDict) 中，所以如果它有效，我会接受它。由于 sortedcontainers 不包含任何允许替换值和对值进行排序的内容，因此您必须进行 lot 的工作才能添加该行为，与从头开始实现它的数量级大致相同。

关于为什么这不起作用的附加说明：

除了您的用例根本不适合集合（逻辑概念，不仅仅是 set 本身）之外，SortedSet 本身异常不适合您的 class，因为隐式依赖于两个不变量（只有一个是 Python 严格要求的，尽管另一个通常遵守：

Python要求：__eq__应与__hash__一致：如果两个项目相等，则它们必须具有相同的散列，并且，尽可能地，两个不相等的项目应该 not 具有相同的散列（理想情况下散列应该基于相同的字段 __eq__ 进行比较，但它是合法的它在这些字段的子集上）
SortedSet 所必需的（并且通常由其他处理排序对象的东西假设）：__eq__ 应该与 __lt__（以及所有其他丰富的比较运算符）一致：如果 a == b，那么 a < b 和 b < a 应该都是假的；同样，如果 a < b 或 b < a 为真，则 a != b。 Python 中的大多数排序内容只坚持 __lt__ 比较以允许不一致的定义，但是如果您将相同的对象放在 tuple 中进行比较，突然之间词典顺序规则意味着 tuple 自己的 __lt__ 实现依赖于 class 的 __lt__ 和 __eq__，因此在实践中您无论如何都希望它们保持一致。

您的 class 违反了#2；排序规则完全与相等性的定义无关。 SortedSet 在这里混淆，根据 __hash__+__eq__ 确定唯一性并使用 __lt__ 排序，但在某些情况下（例如删除元素时）它依赖于 __lt__ 与 __eq__ 一致。具体来说，在从内部 set 中移除（使用 __hash__+__eq___）之后，它会从内部 SortedList 中移除，使用 SortedList 将其一分为二以找到要移除的元素，使用 __lt__，并使用 __eq__ 确认它通过相等性检查找到了正确的元素。由于 __eq__ 和 __lt__ 不一致（只有当您尝试删除具有相同 person_id 和 value 的 R 时它们才会匹配），这永远不会找到它试图删除的值，并引发异常。

如何让 SortedSet 更新旧值的位置？

How to get SortedSet to update position of old value?

python

sorting

sortedset

sortedcontainers

关于为什么这不起作用的附加说明：