Python的itertools.product()的效率 [英] efficiency of Python's itertools.product()

问题描述

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

So I'm looking at different ways to compute the Cartesian product of n arrays, and I came across the rather elegant solution (here on SO) of using the following code:

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

查看 python文档页面(我对 itertools.product()使用2.7，顺便说一句，它表示代码等效于以下内容:

Looking at the python doc page (I'm using 2.7, btw) for itertools.product(), it says the code is equivalent to the following:

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)

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

(It does note the following: This function is equivalent to the following code, except that the actual implementation does not build up intermediate results in memory:)

我不是CS专家-因此我在评估此算法的效率方面非常不擅长.我的第一个猜测是 O(n ^ 2)(由于嵌套了for循环).

I'm not a CS person - so I'm pretty bad at estimating the efficiency of this algorithm. My first guess would be O(n^2) (due to the nested for loop).

我错了吗?

推荐答案

您绝对正确.也就是说，在两个数组输入的特殊情况下，两个数组的大小均为 n .在一般情况下，对于 i 中的 n [ i ]大小为 n [ i ]的 k 数组.> k 将为O(所有 n [ i ]的乘积).

You are absolutely right. That is, in the special case of two arrays input, both of the size n. In the general case of k arrays of the sizes n[i] for i in 1..k it will be O(Product of all n[i]).

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

Why is this the case and why is there no way to optimize this any further?

好吧，在这种情况下，输出的大小直接是所有 n [ i ]的乘积"，这正是我们正在讨论的函数的本质.Python通过将其实现为生成器，从而使这一点更加明显.因此，对于每个元素，此生成器都会生成一个元素，最后，生成的元素将与所述乘积一样多.

Well, in this case the size of the output is directly this "Product of all n[i]" which lies in the nature of the function we are discussing. Python makes this even more obvious by implementing it as a generator. So for each element, this generator yields one element, in the end it will be as many yielded elements as the said product.

当然，如果某件事明显地做了 x 次，它的效率就不会比O( x )好.如果每个元素的工作量还取决于输入大小，则可能会更糟.因此，确切地说，此处每个元素的工作量取决于我们放入的数组的数量，因此真正的工作量将是

Of course, if something so obviously does anything x times, its efficiency cannot be better than O(x). It could be worse if the effort for each element was also depending on the input size. So, to be precise, the effort for each element here is depending on the number of arrays we put in, so the true effort would be

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

O(k × Product of all n[i])

这篇关于Python的itertools.product()的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！