我想知道如果有是建立在弱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和MutableSet ABC可以很容易地编写一个OrderedSet。
同样,你可以重用现有weakref.WeakSet并用OrderedSet取代它的底层set()。
索引是更难以实现 - 需要时将其转换为一个列表,这些最简单的方法。这是因为集和类型的字典在本质上是疏是必要的。
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
,它都将正常工作:-)
雷蒙德有一个伟大的和简洁的答案,像往常一样,但其实我来到这里而回感兴趣的可转位部分,比weakref部分更多。我最终建成我自己的答案,成为the IndexedSet
type in the boltons utility library。基本上,它是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兼容)。