Python Copy vs Incremental store (Binary search)
Suppose there will be k snapshot, for each snapshot n element\n\n# Copy: \ntime O(1) space O(kn), actual Runtime: 416 ms beats 85.74 %, Memory Usage: 37.4 MB\n\
Suppose there will be `k` snapshot, for each snapshot `n` element\n\n# Copy: \ntime `O(1)` space `O(kn)`, actual Runtime: 416 ms beats 85.74 %, Memory Usage: 37.4 MB\n\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.d=collections.defaultdict(dict)\n        self.snap_id=0\n\n    def set(self, index: int, val: int) -> None:\n        self.d[self.snap_id][index]=val\n\n    def snap(self) -> int:\n        self.d[self.snap_id+1]=self.d[self.snap_id].copy()\n        self.snap_id+=1\n        return self.snap_id-1\n        \n\n    def get(self, index: int, snap_id: int) -> int:\n        return self.d[snap_id].get(index, 0)\n```\n\n# Incremental store (Binary search): \n\ntime `O(logn)` space `O(k*avg increamental number)`, actual Runtime: 652 ms beats 14.36 %, Memory Usage: 34.2 MB\n\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.d=collections.defaultdict(list)\n        self.c={}\n        self.snap_id=0\n        self.l=length\n\n    def set(self, index: int, val: int) -> None:\n        self.c[index]=val\n\n    def snap(self) -> int:\n        snap_id=self.snap_id\n        for i, v in self.c.items():\n            self.d[i].append((snap_id, v))\n        \n        self.snap_id+=1\n        self.c={}\n        return snap_id\n        \n\n    def get(self, index: int, snap_id: int) -> int:\n        if index not in self.d:\n            return 0\n        history=self.d[index]\n        if snap_id<history[0][0]:\n            return 0\n        st, en=0, len(history)-1\n        while st<=en:\n            mid=int((st+en)/2)\n            if(history[mid][0]==snap_id):\n                return history[mid][1]\n            elif(history[mid][0]<snap_id):\n                st=mid+1\n            else:\n                en=mid-1\n        #0,1,5\n\n        return history[st-1][1]\n```\n\n# Another copy implementation: \nShould be same time/space complexity with first copy implemtation, however cost 932 ms\t37.4 MB. I bet may due to wierd memory locality implementation in Python vm.\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.d={}\n        self.c={}\n\n    def set(self, index: int, val: int) -> None:\n        self.c[index]=val\n\n    def snap(self) -> int:\n        snap_id = len(self.d)\n        self.d[snap_id]=self.c.copy()\n        return snap_id\n        \n\n    def get(self, index: int, snap_id: int) -> int:\n        return self.d[snap_id].get(index, 0)\n```
[]