python - 如果我保留对底层迭代器的引用，为什么 islice(permutations) 会快 100 倍？

Question

如果我只保留对 permutations 迭代器的额外引用，则通过 islice(permutations(a), n) 进行迭代会快 100 倍。在有和没有额外引用之间交替:

  2.1 ms  with
202.2 ms  without
  2.1 ms  with
195.8 ms  without
  2.1 ms  with
192.4 ms  without

这是怎么回事？

完整代码(Try it online!):

from timeit import timeit
from itertools import permutations, islice
from collections import deque

a = range(10 ** 7)
n = 10 ** 5

for label in ['with', 'without'] * 3:
    if label == 'with':
        perms = islice((foo := permutations(a)), n)
    else:
        perms = islice(permutations(a), n)
    next(perms)
    t = timeit(lambda: deque(perms, 0), number=1)
    print('%5.1f ms ' % (t * 1e3), label)

Answer 1

我才明白为什么。如果我不不保留一个引用，那么迭代器和它所包含的所有内容都会在计时结束时被垃圾收集起来，并且包含在时间中。

请注意，我构建排列的列表非常大。所以每个排列都非常大。所以 permutations 迭代器有一个很大的结果元组和内部状态数据结构，我还有数百万个范围内的整数对象。所有这些都必须清理干净。

当我将 a 的大小减半为 a = range(10 ** 7//2) 时，“没有”额外引用的时间下降到大约一半(100 毫秒)。

当我将 a 的大小加倍到 a = range(10 ** 7 * 2) 时，“没有”额外引用的时间大约加倍(超过 400毫秒)。

这两种变化都不影响“with”时间(总是在 2 毫秒左右)。

---

_{万一有人想知道为什么我要对这么大的列表进行排列:我是 looking into permutations 提供所有 n! n 个元素的排列。人们可能认为它需要 O(n × n!)，因为这是整体结果大小。但是它reuses and modifies its result tuple如果可以，那么它不会从头开始构建每个排列，而只需要对其进行一些更新。所以我tested that使用较大的 n 以查看可以和不能重用其结果元组之间的速度差异。如果可以的话，它确实要快得多，而且似乎只需要 O(n!) 时间来提供所有排列。它似乎平均 change just 2.63 elements从一个排列到下一个排列。}