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

在时间和空间方面,更有效的方法是为每个索引使用一个列表来跟踪 snap_id s的位置 set 为索引调用,以便您可以使用 bisect.bisect 以查找 snap_id 最接近给定 snap_id 在一个 get 呼叫,降低的时间复杂性 收到 到 O(log n) 同时保持的空间复杂性 O(n) :

from bisect import bisect

class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0
        self.snaps = {}
        self.values = {}

    def set(self, index, value):
        if not (snaps := self.snaps.setdefault(index, [])) or snaps[-1] != self.snap_id:
            snaps.append(self.snap_id)
        self.values.setdefault(index, {})[self.snap_id] = value

    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        if snaps := self.snaps.get(index):
            return self.values[index][bisect(snaps, snap_id) - 1]
        return 0

演示: https://ideone.com/hgsoes

问题可能在于您存储了整个列表的多个副本。要优化内存使用情况,请仅存储对btw快照所做的更改:

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