如何实现临时功能"memoization"？

Question

要记忆的函数不是"pure"（它的return值将来可能会改变）所以我不能使用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、""、[]、{}等假值是不可能的return expensive).

的值

这样好看吗？

Answer 1

我会坚持使用 try/except 版本，因为假设 expensive 的 return 值是真实的对于普遍性来说是个坏主意（并且在性能方面，作为实现细节，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 subclass，它遵循 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))

写完 class，你可以用更少的缓存相关 kruft 来编写你的函数：

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

Answer 2

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

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

..但是，现在我们已经分离出 setup/teardown，如果我们想用 x 执行其他任务（[=16 除外），我们可以稍后返回此代码=]) 我们之前可能没有考虑过，包括 g(x) 和 h(x):

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

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

如何实现临时功能"memoization"？

How to implement temporary function "memoization"?

python

memoization

python-2.7