9

Consider the following function, which returns all the unique permutations of a set of elements:

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)

This prints

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

as expected. However, when I add the lru_cache decorator, which memoizes the function:

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)

it prints the following:

(1, 1, 2)

Why is it only printing the first permutation?

4

1 回答 1

22

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

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

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

生成器 for(1,)也被使用了两次，这甚至在第三个结果降到().

要查看发生了什么，请将 a 添加为函数的第一行（并在主循环print(elements)中的调用中添加某种标记，以便您分辨出区别）。然后将记忆版本的输出与原始版本进行比较。printfor

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

于 2016-04-22T21:48:30.053 回答