如何减少此处使用的内存量？

Question

所以，我为this问题编写了一段代码。

代码：

import copy

class SnapshotArray:

    def __init__(self, length: int):
        self.lst = [0] * length
        self.snap_id = -1
        self.hash = []
        self.by_snap_id = 0
        return None

    def set(self, index: int, val: int) -> None:
        self.lst[index] = val
        return None

    def snap(self) -> int:
        self.snap_id += 1
        self.copy = copy.copy(self.lst)
        self.hash.append(self.copy)
        del self.lst
        self.lst = self.hash[self.snap_id]
        return self.snap_id

    def get(self, index: int, snap_id: int) -> int:
        return self.hash[snap_id][index]

在 69 / 75 测试用例中显示 MLE

所以我尝试只制作一个列表，我也将从中获取当前列表的值，但它不起作用。那么，如何减少内存使用量呢？

Answer 1

问题可能是您存储了整个列表的多个副本。要优化内存使用，仅存储快照所做的更改：

class SnapshotArray:

def __init__(self, length: int):
    self.snapshots = [{}] 
    self.current = {}
    self.snap_id = 0
def set(self, index: int, val: int) -> None:
    self.current[index] = val
def snap(self) -> int:
    self.snapshots.append(self.current.copy())
    self.current = {}
    self.snap_id += 1
    return self.snap_id - 1
def get(self, index: int, snap_id: int) -> int:
    for i in range(snap_id, -1, -1):
        if index in self.snapshots[i]:
            return self.snapshots[i][index]
    return 0