python - Python 的 itertools.product() 的效率

Question

所以我正在寻找不同的方法来计算 n 数组的笛卡尔积，并且我遇到了使用以下代码的相当优雅的解决方案(此处为 SO):

import itertools
    for array in itertools.product(*arrays):
        print array

查看 python doc page (我正在使用 2.7，顺便说一下)itertools.product()，它表示代码等同于以下内容:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

(它确实注意到以下内容:此函数等效于以下代码，只是实际实现不会在内存中构建中间结果:)

我不是 CS 人员 - 所以我很不擅长估计这个算法的效率。我的第一个猜测是 O(n^2)(由于嵌套的 for 循环)。

我错了吗？

Answer 1

你完全正确。也就是说，在两个数组输入的特殊情况下，两个数组的大小都是 n。在 k 个大小为 n[i] 的数组的一般情况下，i 在 1..k 它将是 O(所有 n[i] 的乘积)。

为什么会这样，为什么没有进一步优化的方法？

嗯，在这种情况下，输出的大小直接是这个“所有 n[i] 的乘积”，这取决于我们正在讨论的函数的性质. Python 通过将其实现为生成器使这一点更加明显。因此，对于每个元素，此生成器都会生成一个元素，最终生成的元素数将与所述产品一样多。

当然，如果某个东西如此明显地做了 x 次，它的效率不可能比 O(x) 好。如果每个元素的工作量也取决于输入大小，情况可能会更糟。所以，准确地说，这里每个元素的工作量取决于我们放入的数组数量，所以真正的工作量是

O(k × 所有n[i]的乘积)