delta-dictionary/dictionary在python中具有修訂意識？

Question

我期待在python中創建一個帶有「回滾」功能的字典。字典將以修訂版本號0開始，修訂版將僅通過明確的方法調用來提高。我不需要刪除密鑰，只需添加和更新密鑰，值對，然後回滾。我永遠不需要'前滾'，也就是說，當回滾字典時，所有較新的修訂版都可以被丟棄，並且我可以重新開始重新修復。因此，我希望喜歡的行爲：

>>> rr = rev_dictionary() 
>>> rr.rev 
0 
>>> rr["a"] = 17 
>>> rr[('b',23)] = 'foo' 
>>> rr["a"] 
17 
>>> rr.rev 
0 
>>> rr.roll_rev() 
>>> rr.rev 
1 
>>> rr["a"] 
17 
>>> rr["a"] = 0 
>>> rr["a"] 
0 
>>> rr[('b',23)] 
'foo' 
>>> rr.roll_to(0) 
>>> rr.rev 
0 
>>> rr["a"] 
17 
>>> rr.roll_to(1) 
Exception ... 

只要是明確的，與修訂相關聯的狀態是字典的狀態剛剛之前的roll_rev()方法調用。因此，如果我可以在修改版中多次更改與某個關鍵字相關的值，並且只記得最後一個。

我想要一個相當高效的內存實現：內存使用量應該與增量成正比。因此，僅僅具有字典的副本列表不會針對我的問題進行擴展。人們應該認爲鑰匙是成千上萬，並且修訂數量是幾十萬。

我們可以假定這些值是不可變的，但不一定是數字。對於數值例如是整數，有一個相當直接的實現（有一個從修訂到修訂的數字增量字典列表）。我不知道如何把它變成一般形式。也許引導整數版本並添加一個值的數組？

所有幫助表示讚賞。

Answer 1

只有一個字典，從鍵映射到（revision_number，actual_value）元組列表。當前值爲the_dict[akey][-1][1]。回滾僅涉及從每個列表的末尾彈出適當的條目。

更新：回滾的例子

KEY1 - > [（10， 'v1-10'），（20， 'v1-20'）]

方案1：當前修訂爲30 ，回滾到25：什麼也沒發生

場景2：當前30，回15：彈出最後一個條目

方案3：目前的30，回到5：彈出兩個條目

更新2：快回退（與取捨）

我覺得你對每一個彈出列表關心的是更好的表述爲「需要檢查每一個清單，看看是否需要啪」。隨着更奇特的數據結構（更多的內存，更多的時間來維護添加和更新操作中的花哨位），您可以減少回滾的時間。

添加一個數組（由修訂號索引），其值是在該修訂中更改的字典值的列表。

# Original rollback code: 
for rlist in the_dict.itervalues(): 
    if not rlist: continue 
    while rlist[-1][0] > target_revno: 
     rlist.pop() 

# New rollback code 
for revno in xrange(current_revno, target_revno, -1): 
    for rlist in delta_index[revno]: 
     assert rlist[-1][0] == revno 
     del rlist[-1] # faster than rlist.pop()  
del delta_index[target_revno+1:] 

更新3：票友方法

import collections 

class RevDict(collections.MutableMapping): 

    def __init__(self): 
     self.current_revno = 0 
     self.dict = {} 
     self.delta_index = [[]] 

    def __setitem__(self, key, value): 
     if key in self.dict: 
      rlist = self.dict[key] 
      last_revno = rlist[-1][0] 
      rtup = (self.current_revno, value) 
      if last_revno == self.current_revno: 
       rlist[-1] = rtup 
       # delta_index already has an entry for this rlist 
      else: 
       rlist.append(rtup) 
       self.delta_index[self.current_revno].append(rlist) 
     else: 
      rlist = [(self.current_revno, value)] 
      self.dict[key] = rlist 
      self.delta_index[self.current_revno].append(rlist) 

    def __getitem__(self, key): 
     if not key in self.dict: 
      raise KeyError(key) 
     return self.dict[key][-1][1] 

    def new_revision(self): 
     self.current_revno += 1 
     self.delta_index.append([]) 

    def roll_back(self, target_revno): 
     assert 0 <= target_revno < self.current_revno 
     for revno in xrange(self.current_revno, target_revno, -1): 
      for rlist in self.delta_index[revno]: 
       assert rlist[-1][0] == revno 
       del rlist[-1] 
     del self.delta_index[target_revno+1:] 
     self.current_revno = target_revno 

    def __delitem__(self, key): 
     raise TypeError("RevDict doesn't do del") 

    def keys(self): 
     return self.dict.keys() 

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

    def iteritems(self): 
     for key, rlist in self.dict.iteritems(): 
      yield key, rlist[-1][1] 

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

    def __iter__(self): 
     return self.dict.iterkeys() 

Answer 2

全碼豪華的解決辦法是使用B+Trees與寫入時複製。我使用B + Trees上的變體來實現我的blist數據類型（可用於非常高效地創建列表的修訂版，與您的問題完全類似）。

總的想法是將數據存儲在平衡樹中。當您創建新版本時，只複製根節點。如果您需要修改與舊版本共享的節點，請複製節點並修改副本。這樣，舊樹仍然完整無缺，但你只需要改變內存（技術上，O（k * log n），其中k是改變的數量，n是項目的總數）。儘管如此，實現並不是微不足道的。