Python 的 itertools.product() 的效率

Question

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

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)

（注意以下几点：这个函数等同于下面的代码，除了实际的实现不会在内存中建立中间结果：）

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

我错了吗？

Answer 1

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

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

嗯，在这种情况下，输出的大小直接就是这个"Product of all n[i]"，这取决于我们正在讨论的函数的性质。 Python 通过将其实现为生成器使这一点更加明显。所以对于每个元素，这个生成器产生一个元素，最后它会产生与所述产品一样多的元素。

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

O(k × 所有 n[i])

Python 的 itertools.product() 的效率

efficiency of Python's itertools.product()

python

algorithm

performance

set-theory

cartesian-product