Python 中的可索引弱有序集

Question

我想知道是否有一种简单的方法可以在 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])

有没有更简单的方法来做到这一点？

Answer 1

最简单的方法是利用标准库中的现有组件。

OrderedDict 和 MutableSet ABC 使编写 OrderedSet 变得容易。

同样，您可以重用现有的 weakref.WeakSet 并替换其底层 set() 与 OrderedSet。

索引更难实现——这些最简单的方法是在需要时将其转换为列表。这是必要的，因为集合和字典本质上是稀疏的。

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 开始，保证常规字典是有序的，因此您可以在本配方中用 dict 替换 OrderedDict ，一切都会正常工作： -)

Answer 2

像往常一样，雷蒙德有一个很棒而简洁的答案，但实际上我不久前来到这里对可索引部分感兴趣，而不是对弱引用部分感兴趣。我最终构建了自己的答案，它成为 IndexedSet 中的 IndexedSet 类型Boltons 实用程序库。基本上，它结合了 list 和 set API 的所有最佳部分。

>>> 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兼容）。