Cài đặt có thể lập chỉ mục yếu có thể lập chỉ mục trong Python

Question

Tôi đã tự hỏi liệu có một cách dễ dàng để xây dựng một bộ đặt hàng có thể lập chỉ mục yếu trong Python hay không. Tôi đã cố gắng xây dựng một bản thân. Dưới đây là những gì tôi đã đưa ra:

""" 
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]) 

Có cách nào dễ dàng hơn để thực hiện việc này không?

Answer 1

Cách dễ nhất là tận dụng các thành phần hiện có trong thư viện chuẩn.

OrderedDict và MutableSet ABC giúp bạn dễ dàng viết một OrderedSet.

Tương tự như vậy, bạn có thể tái sử dụng các weakref.WeakSet hiện có và thay thế bộ cơ bản của nó() với một OrderedSet:

import collections, weakref 

class OrderedSet(collections.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) 

Answer 2

Raymond có một câu trả lời tuyệt vời và gọn gàng, như thường lệ, nhưng tôi thực sự đến đây một thời gian trở lại quan tâm đến phần có thể lập chỉ mục, nhiều hơn phần yếu kém. Tôi cuối cùng đã xây dựng câu trả lời của riêng tôi, mà đã trở thành the IndexedSet type in the boltons utility library. Về cơ bản, đó là tất cả các phần tốt nhất của các API list và set, được kết hợp.

>>> 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' 

Nếu phần weakref là rất quan trọng bạn có khả năng có thể thêm nó thông qua thừa kế hoặc sửa đổi trực tiếp của một bản sao của mã (module là độc lập, tinh khiết-Python, và 2/3 tương thích).