python - 如何实现临时函数 "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 级内置的(因为理论上，有一些竞争条件 setdefault 可以触发在执行 Python 级 __eq__ 函数以解决冲突时真正的病态条件下)，但最坏的情况只是重复数据删除不起作用。

如果您不喜欢函数本身的所有 kruft，将其分解的一个好方法是推出您自己的 dict 子类，它遵循 集合的一般模式。 defaultdict (但使用 key 作为计算默认值的一部分)。这并不难，感谢 __missing__ 钩子(Hook) 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)