演算法練習:有版本號的key-value store

要求

寫一個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"

Leave a Comment

Your email address will not be published.