我想在 python 中使用 dict,但将键/值对的数量限制为 X。换句话说,如果 dict 当前正在存储 X 个键/值对并且我执行插入,我想要其中之一要删除的现有对。如果它是最近最少插入/访问的密钥,那就太好了,但这并不是完全必要的。
如果这存在于标准库中,请节省我一些时间并指出来!
我想在 python 中使用 dict,但将键/值对的数量限制为 X。换句话说,如果 dict 当前正在存储 X 个键/值对并且我执行插入,我想要其中之一要删除的现有对。如果它是最近最少插入/访问的密钥,那就太好了,但这并不是完全必要的。
如果这存在于标准库中,请节省我一些时间并指出来!
Python 2.7 和 3.1 有OrderedDict并且有早期 Python 的纯 Python 实现。
from collections import OrderedDict
class LimitedSizeDict(OrderedDict):
def __init__(self, *args, **kwds):
self.size_limit = kwds.pop("size_limit", None)
OrderedDict.__init__(self, *args, **kwds)
self._check_size_limit()
def __setitem__(self, key, value):
OrderedDict.__setitem__(self, key, value)
self._check_size_limit()
def _check_size_limit(self):
if self.size_limit is not None:
while len(self) > self.size_limit:
self.popitem(last=False)
您还必须重写可以插入项目的其他方法,例如update
. 的主要用途OrderedDict
是让您可以轻松控制弹出的内容,否则正常dict
工作。
cachetools将为您提供很好的 Mapping Hashes 实现(它适用于 python 2 和 3)。
文档摘录:
就本模块而言,缓存是具有固定最大大小的可变映射。当缓存已满时,即通过添加另一个项,缓存将超过其最大大小,缓存必须根据合适的缓存算法选择丢弃哪些项。
这是一个简单的、无 LRU Python 2.6+ 的解决方案(在较旧的 Python 中,您可以使用 执行类似的操作UserDict.DictMixin
,但在 2.6 及更高版本中不建议这样做,并且collections
无论如何最好使用 ABC...):
import collections
class MyDict(collections.MutableMapping):
def __init__(self, maxlen, *a, **k):
self.maxlen = maxlen
self.d = dict(*a, **k)
while len(self) > maxlen:
self.popitem()
def __iter__(self):
return iter(self.d)
def __len__(self):
return len(self.d)
def __getitem__(self, k):
return self.d[k]
def __delitem__(self, k):
del self.d[k]
def __setitem__(self, k, v):
if k not in self and len(self) == self.maxlen:
self.popitem()
self.d[k] = v
d = MyDict(5)
for i in range(10):
d[i] = i
print(sorted(d))
正如其他答案所提到的,您可能不想将 dict 子类化 -self.d
不幸的是,显式委托是样板文件,但它确实保证所有其他方法都由collections.MutableMapping
.
这是一个简单而高效的 LRU 缓存,使用简单的 Python 代码编写,可在任何 Python 1.5.2 或更高版本上运行:
class LRU_Cache:
def __init__(self, original_function, maxsize=1000):
self.original_function = original_function
self.maxsize = maxsize
self.mapping = {}
PREV, NEXT, KEY, VALUE = 0, 1, 2, 3 # link fields
self.head = [None, None, None, None] # oldest
self.tail = [self.head, None, None, None] # newest
self.head[NEXT] = self.tail
def __call__(self, *key):
PREV, NEXT = 0, 1
mapping, head, tail = self.mapping, self.head, self.tail
link = mapping.get(key, head)
if link is head:
value = self.original_function(*key)
if len(mapping) >= self.maxsize:
old_prev, old_next, old_key, old_value = head[NEXT]
head[NEXT] = old_next
old_next[PREV] = head
del mapping[old_key]
last = tail[PREV]
link = [last, tail, key, value]
mapping[key] = last[NEXT] = tail[PREV] = link
else:
link_prev, link_next, key, value = link
link_prev[NEXT] = link_next
link_next[PREV] = link_prev
last = tail[PREV]
last[NEXT] = tail[PREV] = link
link[PREV] = last
link[NEXT] = tail
return value
if __name__ == '__main__':
p = LRU_Cache(pow, maxsize=3)
for i in [1,2,3,4,5,3,1,5,1,1]:
print(i, p(i, 2))
您可以通过子类化 dict 创建自定义字典类。在您的情况下,您必须重写__setitem__
以检查您自己的长度并在限制被重新缓存时删除某些内容。以下示例将在每次插入后打印当前长度:
class mydict(dict):
def __setitem__(self, k, v):
dict.__setitem__(self, k, v)
print len(self)
d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'
dict 没有这种行为。您可以创建自己的类来执行此操作,例如
class MaxSizeDict(object):
def __init__(self, max_size):
self.max_size = max_size
self.dict = {}
def __setitem__(self, key, value):
if key in self.dict:
self.dict[key] = value
return
if len(self.dict) >= self.max_size:
...
关于这个的几点说明
dict
。从技术上讲,您可以这样做,但它很容易出错,因为这些方法不相互依赖。您可以使用UserDict.DictMixin
来节省必须定义所有方法。如果您将dict
.collections.OrderedDict
,但现在分别保持键的顺序应该可以正常工作(使用 acollections.deque
作为队列)。popitem
方法删除任意一项。有很多很好的答案,但我想指出一个简单的、pythonic 的 LRU 缓存实现。这类似于 Alex Martelli 的回答。
from collections import OrderedDict, MutableMapping
class Cache(MutableMapping):
def __init__(self, maxlen, items=None):
self._maxlen = maxlen
self.d = OrderedDict()
if items:
for k, v in items:
self[k] = v
@property
def maxlen(self):
return self._maxlen
def __getitem__(self, key):
self.d.move_to_end(key)
return self.d[key]
def __setitem__(self, key, value):
if key in self.d:
self.d.move_to_end(key)
elif len(self.d) == self.maxlen:
self.d.popitem(last=False)
self.d[key] = value
def __delitem__(self, key):
del self.d[key]
def __iter__(self):
return self.d.__iter__()
def __len__(self):
return len(self.d)