キーから（revision_number、actual_value）タプルのリストにマッピングするディクショナリを1つだけ作成します。現在の値は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()