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

一个比较高级的解决方案是使用B+树和写时复制的方式。我用一种变体的B+树来实现我的blist数据类型（这个可以非常高效地创建列表的版本，正好和你遇到的问题类似）。

大致的想法是把数据存储在一个平衡的树结构里。当你创建一个新版本时，只需要复制树的根节点。如果你需要修改一个和旧版本共享的节点，你就复制这个节点，然后修改这个复制的节点。这样，旧的树结构就保持完好无损，而你只需要为变化的部分占用内存（从技术上讲，这个复杂度是O(k * log n)，其中k是变化的数量，n是总的数据项数）。

不过，实现起来并不简单。

Answer 2

只需要一个字典，它把键映射到一个包含（修订号，实际值）元组的列表。当前的值可以通过 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()