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是项目的总数）。尽管如此，实现并不是微不足道的。