Python 以特定大小顺序覆盖字典

Question

我有一个不断向字典添加数据的脚本（无法更改意味着没有列表或停止添加数据）。它可以轻松触及其中的 1000 多个不同的键。

我需要每个键和值，但不想重置字典 foo。

foo = {"369610": "a", "109122": "a", "907897": "a", "333291":"a", "381819": "a", "387583": "a", "677430": "a", "660221": "a", "118095":"a", "612172": "a"}

print(len(foo))  # At 10

foo["223533"] = "a"  # Replaces 369610 in the dictionary
foo["601336"] = "a"  # Replaces 109122 in the dictionary

print(len(foo))  # Should be 10

如果我要向字典添加更多键，它将替换 907897 然后 333291 然后 381819 然后 387583。一旦达到 10 的限制，再添加将替换第一个索引 223533。我仍然想访问每个键的每个值关于为什么这是字典而不是列表。

我想遍历字典，然后获取每个条目并用以下内容覆盖该条目：

del foo[index]
foo[random.randint(5000,100000)] = "a"

但我觉得这是一个低效的解决方案。

Answer 1

好吧，如果有人来这里寻找不允许重写键或删除键（仅插入和查找）的字典，那么这就是我的解决方案：

class CircularBuffer:
    def __init__(self, size):
        self.maxsize = size

        self.array = [None] * size
        self.ptr = 0
        self.get_ordered = self.GOpartial
        self.add = self.ADDpartial
        self.len = self.LENpartial

    def __getitem__(self, item):
        return self.array[item]

    def LENpartial(self):
        return self.ptr

    def LENfull(self):
        return self.maxsize

    def ADDpartial(self, item):
        self.array[self.ptr] = item
        self.ptr = self.ptr + 1
        if self.ptr == self.maxsize:
            self.add = self.ADDfull
            self.get_ordered = self.GOfull
            self.len = self.LENfull
            self.ptr = 0
        return None

    def ADDfull(self, item):
        ret = self.array[self.ptr]
        self.array[self.ptr] = item
        self.ptr = (self.ptr + 1) % self.maxsize
        return ret

    def GOpartial(self):
        return self.array[:self.ptr]

    def GOfull(self):
        return self.array[self.ptr:] + self.array[0: self.ptr]

    def __repr__(self):
        return self.array.__repr__()

    def __len__(self):
        return self.len()



class CircularBufferDict:
    def __init__(self, size):
        self.keys = CircularBuffer(size)
        self.mapping = {}
        
    def add(self, k, v):
        if k in self.mapping:
            raise KeyError(f"Key {k} already exists in the dictionary.")
            
        rewritten = self.keys.add(k)
        if rewritten is not None:
            del self.mapping[rewritten]
        self.mapping[k] = v
        
    def get(self, k):
        return self.mapping[k]

达到最大尺寸后，它保持恒定数量的元素。每个操作时间属于 O(1)（在哈希查找时摊销）。使用此结构时，删除（并因此覆盖）效率低下（对数组进行碎片整理需要线性时间）。

Answer 2

from collections import OrderedDict

class FooDict(OrderedDict):
    def __init__(self, maxsize=5, /, *args, **kwds):
        self.maxsize = maxsize
        super().__init__(*args, **kwds)

    def __getitem__(self, key):
        value = super().__getitem__(key)
        return value

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        if len(self) > self.maxsize:
            oldest = next(iter(self))
            del self[oldest]

foo = FooDict()

for i in range(10):
    foo[random.randint(5000,100000)] = "a"
    print(foo)

FooDict([(82596, 'a')])
FooDict([(82596, 'a'), (67860, 'a')])
FooDict([(82596, 'a'), (67860, 'a'), (13232, 'a')])
FooDict([(82596, 'a'), (67860, 'a'), (13232, 'a'), (45835, 'a')])
FooDict([(82596, 'a'), (67860, 'a'), (13232, 'a'), (45835, 'a'), (15591, 'a')])
FooDict([(67860, 'a'), (13232, 'a'), (45835, 'a'), (15591, 'a'), (36689, 'a')])
FooDict([(13232, 'a'), (45835, 'a'), (15591, 'a'), (36689, 'a'), (60175, 'a')])
FooDict([(45835, 'a'), (15591, 'a'), (36689, 'a'), (60175, 'a'), (87882, 'a')])
FooDict([(15591, 'a'), (36689, 'a'), (60175, 'a'), (87882, 'a'), (59414, 'a')])
FooDict([(36689, 'a'), (60175, 'a'), (87882, 'a'), (59414, 'a'), (87218, 'a')])

Python 以特定大小顺序覆盖字典

Python overwrite a dictionary sequentially at certain size

python

caching

python-3.x