有没有一种数据结构可以像"缓冲字典"一样运行？

Question

我需要一种数据结构，它的行为大多像字典（可以通过键访问/删除任何元素），但也具有以下属性：

• 最多可以容纳N个元素（在实际中，N在数百到数千之间）。
• 该结构包含每次访问（获取/设置/删除）时递增的最后操作号码。
• 元素的上次访问会被跟踪 - 每当添加或访问一个项目时，操作编号就会保存在该结构中的项目旁边。
• 如果要添加新项并且该结构保持最大元素数量，则删除操作编号最低的元素（比其他元素的最后访问时间早很长时间），并替换为新元素。

我使用这样的结构来维护对象缓存 - 检索每个元素非常耗时，并且只有少量元素被频繁访问。如果元素不再经常使用，它将最终落在此缓存的底部，并在下一次插入到该结构中时被替换。

我的当前实现（在Python 3中）是一个字典，其中包含键 -> 上次访问编号和对象本身的元组。它运行良好，但我几乎肯定已经在某个地方看到过非常类似的结构 - 是否有像这样缓存的结构呢？

- Dragoon Aethis

---

这是一个LRU缓存吗？你确定需要为每个元素记录操作次数吗？ - Malice

https://pypi.python.org/pypi/py_lru_cache - Malice

Python 3内置了一个LRU缓存：https://docs.python.org/3/library/functools.html#functools.lru_cache - Tomalak

是的，这就是我一直在寻找的。谢谢！ - Dragoon Aethis

Answer 1

就我所知，没有原生的数据结构能够像这种“缓存”一样运作。 CircularDict满足了您的第一个要求（设置最大元素数量或内存），并且部分地满足了最后一个要求（当添加新元素时，若已满，则会删除最早插入的元素）。但它是基于您进行put和set操作的顺序。目前，它不考虑get操作。

from circular_dict import CircularDict

# Initialize a CircularDict with a maximum length of 3
my_cache = CircularDict(maxlen=3)

# Fill it with 4 items (one more than maxlen)
my_cache['1'] = 'value1'
my_cache['2'] = 'value2'
my_cache['3'] = 'value3'
my_cache['4'] = 'value4'

print(circ_dict)

输出将如下所示：

{'2': 'value2', '3': 'value3', '4': 'value4'} 

- Haru Kaeru