限制python字典的大小

我想在python中使用dict，但将键/值对的数量限制为X.换句话说，如果dict当前正在存储X个键/值对，并执行插入操作，我想要现有的对将被丢弃。 如果这是最近最less插入/访问键，那将会很好，但这不是完全必要的。

如果这在标准库中存在，请节省我一些时间并指出！

Answer 1

Python 2.7和3.1已经有了OrderedDict ，而早期的Pythons也有纯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) 

您还必须覆盖其他可以插入项目的方法，例如更新。 OrderedDict的主要用途是可以轻松控制popup的内容，否则正常的字典将会起作用。

Answer 2

cachetools会为你提供很好的映射哈希实现，并且它可以在python 2和3上运行。

文档摘录：

就本模块而言，caching是固定最大大小的可变映射。 当caching已满时，即通过添加另一个项目，caching将超过其最大大小，caching必须根据合适的cachingalgorithmselect丢弃哪个项目。

Answer 3

这里有一个简单的，非LRU的Python 2.6+解决scheme（在较老的Pythons中，你可以使用UserDict.DictMixin做类似的工作，但是在2.6以及更好的版本中，不build议这样做， collections中的ABCs也是可取的）

 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] = vd = MyDict(5) for i in range(10): d[i] = i print sorted(d) 

作为其他答案提到，你可能不想子类dict – 明确的委派self.d是不幸的boilerplatey，但它确实保证每个其他方法由collections.MutableDict正确提供。

Answer 4

这里是一个简单而有效的LRUcaching，用简单的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)) 

Answer 5

字典没有这种行为。 你可以让自己的class级这样做，例如类似的东西

 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 。
• 字典不知道最近添加的关键字是什么，因为字典是无序的。
  • 2.7将引入collections.OrderedDict ，但现在单独保持键的顺序应该可以正常工作（使用collections.deque作为队列）。
  • 如果获得最老的并不是那么重要，那么可以使用popitem方法删除一个任意的项目。
• 大概解释为最初的插入意思。 你将不得不做一些有点不同的消除LRU项目。 最显而易见的有效策略将涉及到保存一个双向链接的键列表，引用节点本身存储为字典值（连同真实值）。 这变得更加复杂，在纯Python中实现它会带来很多开销。

Answer 6

你可以通过inheritancedict来创build一个自定义字典类。 在你的情况下，你将不得不重写__setitem__检查你自己的长度，并删除一些东西，如果限制是recahed。 以下示例将在每次插入后打印当前的长度：

 class mydict(dict): def __setitem__(self, k, v): dict.__setitem__(self, k, v) print len(self) d = mydict() d['foo'] = 'bar' d['bar'] = 'baz' 

Answer 7

有很多很好的答案，但是我想指出一个简单的pythonic实现LRUcaching。 这与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)