如何實現保留訂單並具有快速插入/刪除功能的數據結構？

Question

我正在尋找一個保留其元素順序的數據結構（這可能會改變數據結構的生命週期，因爲客戶端可能會移動元素）。

應該允許快速搜索，插入前/給定的元素後，除去給定的元件，所述第一和最後一個元素的查找，和雙向迭代的開始在給定的元件。

什麼是一個很好的實現？

這是我第一次嘗試：

來自collections.abc.Iterable和collections.abc.MutableSet包含鏈接列表和字典的類派生。字典的鍵是元素，值是鏈接列表中的節點。字典將處理搜索給定元素的節點。一旦找到元素，鏈表將處理插入前/後，刪除和迭代。字典將通過添​​加或刪除相關的鍵/值對進行更新。很明顯，通過這種方法，元素必須是可散列且唯一的（否則，我們需要另一層間接尋址，其中每個元素由自動分配的數字標識符表示，並且只有那些標識符存儲爲鍵）。

它我看來，這將是在漸進比任何list或collections.deque複雜嚴格的更好，但我可能是錯的。 [編輯：錯誤，正如@roliu指出的那樣。與list或deque不同，我無法通過O(1)中的數字索引找到元素。到目前爲止，它是O(N)，但我肯定有一些方法可以使它O(log N)如果有必要。]

Answer 1

稍微修改的Raymond Hettinger's OrderedSet recipe版本似乎滿足我的所有要求。我只增加了對基於位置的訪問和讀/寫的支持。

# changes vs. original recipe at http://code.activestate.com/recipes/576696/: 
# added a position parameter to add 
# changed how pop works, and added popleft 
# added find, get_start, get_end, next_pos, prev_pos, __getitem__, __setitem__ 

class OrderedSetPlus(collections.MutableSet, collections.Iterable): 
    ''' 
    >>> oset = OrderedSetPlus([3, 3, 3, 2, 1, 8, 8]) 
    >>> oset.add(13) 
    >>> p = oset.find(2) 
    >>> oset.add(15, p) 
    >>> oset 
    OrderedSetPlus([3, 15, 2, 1, 8, 13]) 
    >>> p = oset.next_pos(p) 
    >>> oset[p] 
    1 
    >>> oset.add(7, p) 
    >>> oset 
    OrderedSetPlus([3, 15, 2, 7, 1, 8, 13]) 
    >>> oset[p] = 20 
    >>> oset 
    OrderedSetPlus([3, 15, 2, 7, 20, 8, 13]) 
    ''' 

    class DuplicateElement(Exception): 
     pass 

    def __init__(self, iterable=None): 
     self.end = end = [] 
     end += [None, end, end]   # sentinel node for doubly linked list 
     self.map = {}     # key --> [key, prev, next] 
     if iterable is not None: 
      self |= iterable 

    def __len__(self): 
     return len(self.map) 

    def __contains__(self, key): 
     return key in self.map 

    def find(self, key): 
     return self.map.get(key, None) 

    # inserts element before the specified position 
    # if pos is None, inserts at the end 
    # position can only be obtained by calling instance methods 
    def add(self, key, pos = None): 
     if pos is None: 
      pos = self.end 
     if key not in self.map: 
      curr = pos[PREV] 
      curr[NEXT] = pos[PREV] = self.map[key] = [key, curr, pos] 

    def discard(self, key): 
     if key in self.map:   
      key, prev, next = self.map.pop(key) 
      prev[NEXT] = next 
      next[PREV] = prev 

    def __iter__(self): 
     end = self.end 
     curr = end[NEXT] 
     while curr is not end: 
      yield curr[KEY] 
      curr = curr[NEXT] 

    def get_end(self): 
     return self.end[PREV] 

    def get_start(self): 
     return self.end[NEXT] 

    def next_pos(self, pos): 
     pos = pos[NEXT] 
     return None if pos is self.end else pos 

    def prev_pos(self, pos): 
     pos = pos[PREV] 
     return None if pos is self.end else pos 

    def __getitem__(self, pos): 
     return pos[KEY] 

    def __setitem__(self, pos, key): 
     if key in self.map: 
      raise DuplicateElement 
     pos[KEY] = key 

    def __reversed__(self): 
     end = self.end 
     curr = end[PREV] 
     while curr is not end: 
      yield curr[KEY] 
      curr = curr[PREV] 

    def popleft(self): 
     return self.pop(pos = self.get_start()) 


    def pop(self, pos=None): 
     if not self: 
      raise IndexError() 
     if pos is None: 
      pos = self.get_end() 
     key = self[pos] 
     #key = next(reversed(self)) if last else next(iter(self)) 
     self.discard(key) 
     return key 

    def __repr__(self): 
     return '{}({})'.format(self.__class__.__name__, list(self)) 

    def __eq__(self, other): 
     if isinstance(other, OrderedSet): 
      return len(self) == len(other) and list(self) == list(other) 
     return set(self) == set(other) 

Answer 2

在Python中使用雙鏈表是有點罕見。但是，您自己提出的雙鏈表和字典解決方案具有正確的複雜性：您要求的所有操作都是O（1）。

我不認爲標準庫中有更直接的實現。理論上樹可能不錯，但也有缺點，如O（log n）或（確切）它們缺乏標準庫。

Answer 3

我知道這不完全是對你的問題的直接回答（因爲這不是一個python實現的解決方案），但是如果你的數據結構將會相當大，我會考慮一個Redis db。您可以使用redis-pi與Python進行交談。