Блог

Мне было интересно, есть ли простой способ создать индексируемый слабый упорядоченный набор в Python. Я попытался создать его сам. Вот что я придумал:

 """
An indexable, ordered set of objects, which are held by weak reference.
"""
from nose.tools import *
import blist
import weakref


class WeakOrderedSet(blist.weaksortedset):
    """
    A blist.weaksortedset whose key is the insertion order.
    """
    def __init__(self, iterable=()):
        self.insertion_order = weakref.WeakKeyDictionary()  # value_type to int
        self.last_key = 0
        super().__init__(key=self.insertion_order.__getitem__)
        for item in iterable:
            self.add(item)

    def __delitem__(self, index):
        values = super().__getitem__(index)
        super().__delitem__(index)
        if not isinstance(index, slice):
            # values is just one element
            values = [values]
        for value in values:
            if value not in self:
                del self.insertion_order[value]

    def add(self, value):
        # Choose a key so that value is on the end.
        if value not in self.insertion_order:
            key = self.last_key
            self.last_key  = 1
            self.insertion_order[value] = key
        super().add(value)

    def discard(self, value):
        super().discard(value)
        if value not in self:
            del self.insertion_order[value]

    def remove(self, value):
        super().remove(value)
        if value not in self:
            del self.insertion_order[value]

    def pop(self, *args, **kwargs):
        value = super().pop(*args, **kwargs)
        if value not in self:
            del self.insertion_order[value]

    def clear(self):
        super().clear()
        self.insertion_order.clear()

    def update(self, *args):
        for arg in args:
            for item in arg:
                self.add(item)


if __name__ == '__main__':
    class Dummy:
        def __init__(self, value):
            self.value = value

    x = [Dummy(i) for i in range(10)]
    w = WeakOrderedSet(reversed(x))
    del w[2:8]
    assert_equals([9,8,1,0], [i.value for i in w])
    del w[0]
    assert_equals([8,1,0], [i.value for i in w])
    del x
    assert_equals([], [i.value for i in w])
  

Есть ли более простой способ сделать это?

Самый простой способ — воспользоваться преимуществами существующих компонентов в стандартной библиотеке.

OrderedDict и изменяемый набор ABC упрощают написание упорядоченного набора.

Аналогично, вы можете повторно использовать существующий weakref .WeakSet и замените его базовый set() на OrderedSet .

Индексирование сложнее достичь — это самый простой способ преобразовать его в список, когда это необходимо. Это необходимо, потому что наборы и dicts по своей сути разрежены.

 import collections.abc
import weakref

class OrderedSet(collections.abc.MutableSet):
    def __init__(self, values=()):
        self._od = collections.OrderedDict().fromkeys(values)
    def __len__(self):
        return len(self._od)
    def __iter__(self):
        return iter(self._od)
    def __contains__(self, value):
        return value in self._od
    def add(self, value):
        self._od[value] = None
    def discard(self, value):
        self._od.pop(value, None)

class OrderedWeakrefSet(weakref.WeakSet):
    def __init__(self, values=()):
        super(OrderedWeakrefSet, self).__init__()
        self.data = OrderedSet()
        for elem in values:
            self.add(elem)
  

Используйте его так:

 >>> names = OrderedSet(['Alice', 'Bob', 'Carol', 'Bob', 'Dave', 'Edna'])
>>> len(names)
5
>>> 'Bob' in names
True
>>> s = list(names)
>>> s[2]
'Carol'
>>> s[4]
'Edna'
  

Обратите внимание, что начиная с Python 3.7, регулярные dicts гарантированно упорядочиваются, поэтому вы можете заменить dict OrderedDict в этом рецепте, и все будет работать нормально 🙂

У Раймонда, как обычно, отличный и краткий ответ, но я действительно пришел сюда некоторое время назад, интересуясь индексируемой частью больше, чем частью weakref. В конце концов я создал свой собственный ответ, который стал IndexedSet типом в библиотеке утилит boltons. По сути, это все лучшие части API list и set , вместе взятые.

 >>> x = IndexedSet(list(range(4))   list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'
  

Если часть weakref является критической, вы, вероятно, можете добавить ее с помощью наследования или прямой модификации копии кода (модуль является автономным, чистым Python и совместим с 2/3).