我正在寻找在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()方法调用之前的字典状态.因此,如果我可以在修订中“多次”更改与某个键关联的值,而只记住最后一个.

我想要一个相当内存有效的实现：内存使用量应与增量成比例.因此,仅仅拥有字典副本列表将无法解决我的问题.人们应该假设密钥在数以万计,而修订则在数十万.

我们可以假定值是不可变的,但不必是数字.对于其中的值是例如整数,这是一个相当简单的实现方式(具有从修订到修订的数值增量字典的列表).我不确定如何将其转换为一般形式.也许引导整数版本并添加值数组？

所有帮助表示赞赏.

解决方法:

只有一个字典,从键到(revision_number,actual_value)元组列表的映射.当前值为the_dict [akey] [-1] [1].回滚仅涉及从每个列表的末尾弹出适当的条目.

更新：回滚示例

密钥1-> [(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()