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。在1 ...中i的大小为n [i]的k个数组的一般情况下，它将是O（所有n [i]的乘积）。

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

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

当然，如果某事明显地做了x次，那么它的效率不会比O（x）好。如果每个元素的努力也取决于输入大小，则可能会更糟。所以，准确地说，这里每个元素的工作量取决于我们放入的数组的数量，因此真正的努力将是

O（k×所有n [i]的乘积）