如何限制字典的大小？

Question

我想在Python中使用字典，但是需要限制键/值对的数量为X。换句话说，如果该字典当前存储了X个键/值对，并且我执行插入操作，我希望其中一个现有的键/值对被删除。最好是最近插入/访问的键，但这并不完全必要。

如果标准库中存在此功能，请告诉我以节省时间！

- anthony

---

请问如何在Python中从字典中删除最旧的元素？ - Nick Dandoulakis

不错的发现。虽然我不需要LRU，但我想保留它。 - anthony

@Nick：限制大小似乎足以成为一个不同的问题，但是没错，那个问题是这个问题的一半。 - Roger Pate

Answer 1

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也可以工作。

- Roger Pate

---

你在Python 2.7上测试过你的代码吗？dict.pop需要至少1个参数。dict.popitem()可以工作，但它会删除最近的项。 - Sridhar Ratnakumar

此外，setitem 应该在实际设置项目之前检查大小限制，以免失去您正在设置的项目！ - Sridhar Ratnakumar

@Sridhar：现在看来，几个月后的现在，我不确定当时我在想什么；但是popitem更有意义。 - Roger Pate

准确来说，这并不是真正的LRU实现。这是一个FIFO实现，由于字典大小限制而进行删除。为了实现完整的LRU实现，需要重写“__contains__”方法，将最后使用或查询的项移动到字典链接列表的顶部。[我明白，然而这不是问题的主要目标] - Amir

我认为这个答案被高度评价过头了，因为它没有展示如何实现其他可能需要的方法，这些方法不仅包括作者提到的添加/插入元素的方法，还包括删除/移除元素的任何方法。 - martineau

Answer 2

cachetools 将为您提供漂亮的 Mapping Hashes 实现，它可以实现这一点（并且适用于 Python 2 和 3）。

以下是该文档的摘录：

对于本模块而言，缓存是具有固定最大大小的可变映射。当缓存已满时，即通过添加另一个条目，缓存将超过其最大大小时，缓存必须根据适当的缓存算法选择要丢弃的项目。

- vaab

Answer 3

这里有一个简单的Python 2.6+解决方案（在较旧的Python版本中，您可以使用UserDict.DictMixin进行类似的操作，但在2.6及更高版本中不建议使用该方法，还是应该使用collections中的抽象基类）：

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))

正如其他答案提到的那样，你可能不想继承字典--对self.d的显式委托确实很繁琐，但它确保了collections.MutableMapping提供的每个其他方法都是正确的。

- Alex Martelli

Answer 4

这是一个简单且高效的LRU缓存，使用简单易懂的Python代码编写，可在任何1.5.2或更新版本的Python上运行：

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))

- Raymond Hettinger

---

哇，你在如此短的时间内为各种用户案例编写了很多LRU代码，从无论是Python Cookbook（Activestate）、Python标准库、博客、Twitter还是PyCon讲座中阅读你的Python代码总是一种愉悦，现在在StackOverflow上也有了。 - sunqiang

这是非常符合Python风格的代码 -- 一个简单的类，使用字典、列表、基本赋值和解包的方法很直观。该逻辑是自包含的，没有外部依赖。这段代码也非常快速，并且可以轻松通过PyPy进一步优化。使用OrderedDict会增加空间开销（它在内部使用两个字典，而这段代码只使用一个），并且执行了不必要的工作，在这种情况下并没有什么用处。在这种情况下，MutableMapping并不提供任何有用的功能。 - Raymond Hettinger

@martineau 这只是为了显示链接的结构。 - Raymond Hettinger

这不编译。self.head[NEXT] = self.tail NameError：名称“NEXT”未定义。 - ealeon

@ealeon 感谢您的注意。我刚刚回滚到先前定义了NEXT的版本。 - Raymond Hettinger

Answer 5

有很多好的答案，但我想指出一种简单、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)

- Ian Chen

Answer 6

您可以通过子类化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'

- c089

---

子类化内置类型如dict通常是徒劳的。在正常情况下，使用子类化时，像update和setdefault这样的方法将依赖于重写的__getitem__，但这不是它在这里的工作方式。子类化内置类型使引入难以察觉的错误变得容易。当你消除所有这些错误时，通过子类化你并没有节省任何工作。 - Mike Graham

Answer 7

字典没有这种行为。你可以创建自己的类来实现这个功能，例如：

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进行子类化。你理论上可以这样做，但这容易出现bug，因为这些方法并不相互依赖。你可以使用UserDict.DictMixin来避免定义所有方法的麻烦。如果你对dict进行子类化，你可能只能重用少数方法。
• dict不知道最近添加的键是什么，因为它们是无序的。
  • 2.7版本将引入collections.OrderedDict，但现在将键按顺序保留应该也可以正常工作（使用collections.deque作为队列）。
  • 如果获取最老的元素并不是特别重要，你可以使用popitem方法删除任意一个元素。
• 我理解的“最老”指的是大致上最先插入的元素。您需要做一些不同的事情来消除LRU元素。最明显的有效策略涉及到保持具有节点本身的字典值（以及真实值）的键的双向链接列表。这变得更加复杂，在纯Python中实现会带来很多开销。

- Mike Graham

---

你可以直接重用字典(dict)、有序字典(OrderedDict)或其他基类中约一半的方法，甚至不需要使用DictMixin。编写其他方法的转发方法似乎并不容易出错，当然也不会比你在这里自己编写它们更容易出错。 - Roger Pate

我正在尝试找到解决手头问题的方法。如果您只关心键的有序性并且不会遇到多次删除和重新设置相同键的病态情况，导致deque被不在dict中的键污染，那么dict+deque可以为您提供O(1)的获取、设置和删除操作。 - Mike Graham

就像我所说的，我并不认为在这里使用子类化会带来太多好处。我确实认为这样做会引入一些危险——看起来应该可以工作的东西，在子类化Python类时可能无法正常工作。如果我想要引入这样的东西来维护代码，我需要看到一些真正的好处。 - Mike Graham

@Roger，我还没有定义需要执行哪些操作，如果OP根本不需要支持它，那么您无需在deque/list上执行O(n)搜索/删除操作，就像您必须在有序字典类型中维护当前键的容器一样。 - Mike Graham

@Roger：我非常清楚这一事实。我只是试图说服更多的人转向Python 3。 - Adrien Plisson

Answer 8

有一个名为CircularDict的库实现了这种行为。它允许限制dict可以存储的最大项目数量，同时也可以设置内存使用限制。

可以通过以下方式安装：

pip install circular-dict

而且这样使用：

from circular_dict import CircularDict

# Initialize a CircularDict with a maximum length of 3
my_dict = CircularDict(maxlen=3) # You could also set maxsize_bytes=8*1024 bytes

# Fill it with 4 items
my_dict['item1'] = 'value1'
my_dict['item2'] = 'value2'
my_dict['item3'] = 'value3'
# When adding this 4th item, the 1st one will be dropped
my_dict['item4'] = 'value4'
print(circ_dict)

输出将如下所示。

{'item2': 'value2', 'item3': 'value3', 'item4': 'value4'}

- Haru Kaeru