3

我正在寻找在 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()需要明确的是，与修订关联的状态是方法调用之前的字典状态。因此，如果我可以在修订版中多次更改与键关联的值，并且只记住最后一个。

我想要一个相当节省内存的实现：内存使用量应该与增量成正比。因此，仅仅拥有一个字典副本列表并不能解决我的问题。应该假设密钥数以万计，而修订数以十万计。

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

所有帮助表示赞赏。

4

2 回答 2

2

只有一个字典，从键映射到 (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()
于 2010-04-15T22:29:40.370 回答
2

豪华的解决方案是使用B+Trees和写时复制。我在 B+Trees 上使用了一个变体来实现我的blist数据类型（可用于非常有效地创建列表的修订，与您的问题完全相似）。

总体思路是将数据存储在平衡树中。创建新修订时，您只复制根节点。如果您需要修改与旧版本共享的节点，则复制该节点并修改副本。这样，旧树仍然完全完好无损，但您只需要更改内存（从技术上讲，O(k * log n) 其中 k 是更改的数量，n 是项目的总数）。

不过，实施起来并非易事。

于 2010-04-16T01:21:14.163 回答