为什么 functools.lru_cache 会破坏这个功能？

Question

考虑以下函数，其中 returns 一组元素的所有唯一排列：

def get_permutations(elements):
    if len(elements) == 0:
        yield ()
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for subpermutation in get_permutations(tuple(remaining_elements)):
                yield (first_element,) + subpermutation

for permutation in get_permutations((1, 1, 2)):
    print(permutation)

这会打印

(1, 1, 2)
(1, 2, 1)
(2, 1, 1)

符合预期。但是，当我添加 lru_cache 装饰器时，它会记住函数：

import functools

@functools.lru_cache(maxsize=None)
def get_permutations(elements):
    if len(elements) == 0:
        yield ()
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for subpermutation in get_permutations(tuple(remaining_elements)):
                yield (first_element,) + subpermutation

for permutation in get_permutations((1, 1, 2)):
    print(permutation)

它打印以下内容：

(1, 1, 2)

为什么只打印第一个排列？

Answer 1

lru.cache 记住函数的 return 值。您的函数 return 是一个生成器。生成器有状态并且可以被耗尽（即，你走到它们的尽头并且没有更多的项目被产生）。与函数的未修饰版本不同，每次使用给定参数集调用函数时，LRU 缓存都会为您提供 完全相同的生成器对象 。它最好，因为这就是它的用途！

但是您正在缓存的一些生成器使用了不止一次，并且在第二次和后续使用时部分或完全耗尽。（他们甚至可能同时 "in play" 不止一次。）

为了解释您得到的结果，请考虑当 elements 的长度为 0 而您 yield ()... 第一次时会发生什么。下次调用此生成器时，它已经结束并且根本不会产生任何结果。因此，您的子置换循环 什么都不做 并且不会产生任何进一步的结果。由于这是递归中的 "bottoming out" 情况，它对程序的运行至关重要，丢失它会破坏程序产生您期望的值的能力。

(1,) 的生成器也被使用了两次，这打破了第三个结果，甚至还没有下降到 ()。

要查看发生了什么，请在函数的第一行添加一个 print(elements)（并在 for 主循环中的 print 调用中添加某种标记，因此你可以分辨出区别）。然后比较记忆版本和原始版本的输出。

看来您可能想要某种方法来记住生成器的结果。在这种情况下，您要做的是将其编写为一个函数，该函数 return 是一个包含所有项目的列表（而不是一次生成一个项目）并记住它。

为什么 functools.lru_cache 会破坏这个功能？

Why does functools.lru_cache break this function?

python

caching

higher-order-functions

python-3.x

functools