要求
写一个kv store，需要实现按版本查找的method，简单的每次take新snapshot，就把map复制一次，放到list里面，这样按版本找可以实现O(1)。如果想省空间可以次snapshot只存diff。查的时候要把每个snapshot都查一次，就变成O(num_snapshots)。
Python 实现
class kvstore:
def __init__(self):
self.store = {}
self.snapshots = []
self.changed_keys = set()
def set(self, k, v):
self.store[k] = v
self.changed_keys.add(k)
def get(self, k):
return self.store.get(k, None)
def snapshot(self):
d = {}
for k in self.changed_keys:
d[k] = self.store[k]
self.snapshots.append(d)
self.changed_keys = set()
return len(self.snapshots) - 1
def get_from_snap(self, snap_version, key):
for version in range(snap_version, -1, -1):
if key in self.snapshots[version]:
return self.snapshots[version][key]
return None
store = kvstore()
store.set("k1", "v1")
store.set("k2", "v2")
assert store.get("k1") == "v1"
last_snapshot = store.snapshot()
assert last_snapshot == 0
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "v2"
assert store.get_from_snap(last_snapshot, "k3") == None
last_snapshot = store.snapshot()
assert last_snapshot == 1
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "v2"
assert store.get_from_snap(last_snapshot, "k3") == None
store.set("k3", "v3")
store.set("k2", "k2-1")
last_snapshot = store.snapshot()
assert last_snapshot == 2
assert store.get("k1") == "v1"
assert store.get_from_snap(last_snapshot, "k1") == "v1"
assert store.get_from_snap(last_snapshot, "k2") == "k2-1"
assert store.get_from_snap(last_snapshot, "k3") == "v3"
