Python的itertools.product()效率

发布时间：2020-12-20 13:06:45 所属栏目：Python 来源：网络整理

导读：所以我正在研究计算n个数组的笛卡尔积的不同方法,并且我遇到了使用以下代码的相当优雅的解决方案(此处为SO)： import itertools for array in itertools.product(*arrays): print array 看一下对于itertools.product()的python doc page(我用2.7,顺便说一句)

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

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

看一下对于itertools.product()的python doc page(我用2.7,顺便说一句),它说代码等同于以下内容：

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循环).

我错了吗？

解决方法

你是绝对正确的.也就是说,在两个数组输入的特殊情况下,两者的大小为n.在1 …中i的大小为n [i]的k个数组的一般情况下,它将是O(所有n [i]的乘积).

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!