字典大小和内存消耗之间的平衡

Question

我正在使用^{} decorator缓存重复调用。我看到了一些中等规模测试用例的回忆录，执行速度提高了4倍。在

对于更大的测试用例，将输入映射到输出的内存占用了相当多的内存，以至于我得到了"java.lang.OutOfMemoryError: Java heap space"个错误（我使用的是Jython）。在

我可以通过使用memoized_cache[hash(key)] = value而不是memoized_cache[key]: value来节省一些内存，假设hash(key)比key少。正如@gnibbler指出的，如果存在哈希冲突，这将导致问题。在

我可以介绍的另一个节省内存的方法是将字典的大小限制为固定数量的条目。这样的SizedDict recipe已经存在，但我希望截断访问频率最低的元素。在

以下是我写的：

from collections import Counter

class FrequencySizedDict(dict):
    def __init__(self, size=1000):
        dict.__init__(self)
        self._maxsize = size
        self._counter = Counter()
    def __getitem__(self, key):
        self._counter[key] += 1
        return dict.__getitem__(self, key)
    def resize(self, size):
        keys = list(self._counter.most_common(size))
        items = [(key, dict.__getitem__(self, key)) for key in keys]
        self.clear()
        dict.update(self, items)
    def __setitem__(self, key, value):
        if len(self._queue) >= self._maxsize:
            self.resize(self._maxsize/2)
        self._counter[key] += 1
        dict.__setitem__(self, key, value)

有没有一种更好的数据方法可以用更少的内存或时间开销来实现这一点？resize相当昂贵：O(n log n)

Answer 1

使用^{}

@functools.lru_cache(maxsize=128, typed=False)

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.

或pylru，如答案memoization library for python 2.7所述