只有一个字典,从键映射到(修订号,实际值)元组列表。当前值为
the_dict[akey][-1][1]
. 回滚只涉及从每个列表的末尾弹出适当的条目。
更新:回滚示例
场景1:当前版本是30,回滚到25:什么都没有发生
场景2:当前30,返回到15:弹出最后一个条目
场景3:当前30,返回到5:弹出两个条目
更新2:更快的回滚(有折衷)
我认为你对弹出每个列表的担忧最好表达为“需要检查每个列表,看看它是否需要弹出”。使用更丰富的数据结构(更多的内存,更多的时间来维护add和update操作中的丰富位),您可以减少回滚时间。
添加一个数组(按修订号索引),其值是在该修订中更改的字典值的列表。
# 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:]
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()
