如何实现临时功能“memoization”？

Question

要记忆的功能不是“纯粹的”（它的返回值将来可能会改变）所以我不能使用memoize装饰。而且，我需要调用它的值列表。

我做的是

def f(...):
    cache = {}
    for ...:
        try:
            x = cache[k]
        except KeyError:
            x = cache[k] = expensive(k)
        # use x here
    for x in cache.itervalues():
        cleanup(x)

我想知道这是否是表达范式的“pythonic”方式。

例如，我可以通过写作保存3行

def f(...):
    cache = {}
    for ...:
        x = cache[k] = cache.get(k) or expensive(k)
        # use x here
    for x in cache.itervalues():
        cleanup(x)

相反（假设None，0，""，[]，{}和其他假值不可能返回expensive的值）。

这看起来更好吗？

Answer 1

我坚持使用try / except版本，因为关于expensive的返回值的假设烘焙是一个普遍性的坏主意（并且在性能方面，作为一个实现细节，d[k]比CPython上的d.get(k)快，并且例外的成本通常与条件检查的成本相当，更不用说所有这些都可能是expensive函数旁边的噪声）。我会做一个调整，以便在两个线程竞争时统一结果，并最终计算出昂贵的结果，以避免它们各自接收自己的（可能是昂贵的）结果副本。更改except KeyError处理程序中的行：

x = cache[k] = expensive(k)

至：

x = cache.setdefault(k, expensive(k))

这样做，如果两个线程同时开始计算expensive，第一个完成它将存储缓存值，第二个将立即丢弃自己的结果，以支持第一个存储的缓存值。如果结果只是计算成本高，内存不昂贵或每个实例的其他资源成本，这不会造成损害，如果在其他方面它很昂贵，这很快就消除了重复的价值。

它实际上并不是CPython上100％的线程安全，除非k是一个C级内置（因为理论上，在执行Python级别的setdefault函数进行冲突解决时，有一些竞争条件__eq__可能在真正的病态条件下触发），但是最糟糕的情况是重复数据删除不起作用。

如果你不喜欢所有kruft卷入函数本身，一个很好的方法就是推出你自己的dict子类，它遵循collections.defaultdict的一般模式（但是使用键作为计算默认值的一部分）。这并不是那么难，多亏了__missing__钩dict提供：

# Easiest to let defaultdict define the alternate constructor and attribute name
from collections import defaultdict

class CacheDict(defaultdict):
    def __missing__(self, key):
        # Roughly the same implementation as defaultdict's default
        # __missing__, but passing the key as the argument to the factory function
        return self.setdefault(key, self.default_factory(key))

编写完该类之后，您可以使用远远少于缓存的kruft编写函数：

def f(...):
    cacheorcompute = CacheDict(expensive)
    for ...:
        x = cacheorcompute[k]
        # use x here
    for x in cacheorcompute.itervalues():
        cleanup(x)

Answer 2

ShadowRanger的答案可能就是你正在寻找的，但我也会考虑通过在一个地方进行设置和清理任务来进一步分离关注点，并使用x在其他地方利用contextlib.contextmanagers进行工作：

from contextlib import contextmanager

@contextmanager
def xs_manager(...):
    """Manages setup/teardown of cache of x's"""
    # setup
    cache = {}
    def gencache():
        """Inner generator for passing each x outside"""
        for ...:
            try:
                x = cache[k]
            except KeyError:
                x = cache[k] = expensive(k)
            yield x
    yield gencache()
    # external use of x's occurs here
    # teardown
    for x in cache.itervalues():
        cleanup(x)

def f(...):
    with xs_manager(...) as xvaluecache:
        for x in xvaluecache:
            # use x here

现在你可以这样做：

>>> f(...)

..但是，现在我们已经分离了设置/拆解，如果我们想要使用xs（除了f之外）我们可能以前没有考虑过的其他任务，包括g(x)和h(x)，我们可以稍后再回到这个代码：

>>> with xs_manager(...) as xvaluecache:
...    for x in xvaluecache:
...        g(x)
...        h(x)

所以这是更多的代码，但它为您提供了更多的可能性。