Как заставить SortedSet обновлять позицию старого значения?

Question

У меня есть следующий объект, который я хотел бы сохранить в контейнере, который сортируется при вставке и не содержит дубликатов, поэтому я использую

      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([человек: 11 (21), человек: 17 (4), человек: 13 (2), человек: 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)

Я ожидаю, что объект R с идентификатором 17 назван person: 17 (4)переместиться на задний план со значением person: 17 (-67)как:

SortedSet([человек: 11 (21), человек: 13 (2), человек: 7 (-41), человек: 17 (-67)])

Однако ничего не меняется:

SortedSet([человек: 11 (21), человек: 17 (4), человек: 13 (2), человек: 7 (-41)])

Как я могу добиться желаемого результата, как описано, с помощью SortedSetили любой другой контейнер, который сортируется при вставке и не имеет дубликатов?

Answer 1

Ответ DeepSpace охватывает выполнение этой работы (хотя и несколько неэффективно) , но я собираюсь поставить здесь задачу: это плохой дизайн.

Наборы (логическая конструкция) предназначены для хранения уникальных предметов. Если что-то added к набору равен чему-то уже в нем, нет причин заменять старый элемент, потому что старый элемент и новый элемент эквивалентны . Если в вашем классе не используется определение равенства, в котором равенство подразумевает взаимозаменяемость (два одинаковых экземпляра могут использоваться взаимозаменяемо всеми соответствующими способами), то эти экземпляры не подходят для использования в классе . Даже без участия, используя plain , это не сработает, потому что set.addне заменяет элемент, когда вы вставляете «равный» элемент; в конце концов, они оба эквивалентны, так зачем же выполнять дополнительную работу?

Когда вам нужно иметь концепцию ключей, которые могут отображаться в значения, где значения для данного ключа могут быть изменены позже, не зная исходного значения, вам нужно сопоставление ( dict-подобный), а не набор (-подобный).

Келли Банди предполагает , что то, что вы хотите, может уже существовать в sortedcollectionsупаковка ( ValueSortedDict), так что я бы пошел с этим, если это работает. С sortedcontainersне содержит ничего, что позволяло бы заменять значения и сортировать значения, вам пришлось бы проделать большую работу, чтобы добавить это поведение, примерно того же порядка, что и его реализация с нуля.

---

Дополнительные примечания о том, почему это не работает:

Помимо того, что ваш вариант использования принципиально не подходит для наборов (логическая концепция, а не только сама по себе), он сам по себе необычно не подходит для вашего класса, поскольку неявно полагается на два инварианта (только один из которых строго требуется Python, хотя другой обычно придерживаются):

1. Требуется Python: должно соответствовать: Если два элемента равны, они должны иметь одинаковый хеш, и, насколько это возможно, два неравных элемента не должны иметь одинаковый хеш (в идеале хеш должен быть основан на одинаковых полях, сравнивает , но можно основывать его на подмножестве этих полей)
2. Требуется SortedSet (и часто предполагается другими вещами, работающими с отсортированными объектами): должно быть согласовано с (и всеми другими расширенными операторами сравнения): If a == b, тогда и оба должны быть ложными; аналогично, если a < bили же b < aверно, то a != b. Большая часть средств сортировки в Python использует только сравнения, чтобы разрешить противоречивые определения, но если вы поместите одни и те же объекты в объект для сравнения, вдруг правила лексикографического упорядочения означают tupleсобственная реализация зависит как от вашего класса, так и от вашего класса, поэтому на практике вы все равно хотите, чтобы они были согласованы.

Ваш класс нарушает #2; правила сортировки совершенно не связаны с определением равенства. SortedSetздесь путается, определяя уникальность на основе + и упорядочивая с помощью , но в определенных обстоятельствах (например, при удалении элементов) он полагается на согласованность с . В частности, после удаления из внутреннего set(с использованием __hash__+_) потом удаляется из внутреннего SortedList, который делит пополам, чтобы найти элемент для удаления, используя , и подтверждает, что он нашел правильный элемент с проверкой на равенство, используя . С __eq__а также __lt__непоследовательны (они совпадут, только если вы попытаетесь удалить Rс тем же person_idа также value), никогда не находит значение, которое пытается удалить, и вызывает исключение.

Answer 2

Вы можете подкласс SortedSet, отменяя его addи методы. Нам нужно переопределить 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)])