Python优化组合生成

Question

为什么第一种方法这么慢？在

再慢一点，怎么能把速度提高到1000倍呢？在

在这种情况下，性能是第一要务。在我的第一次尝试中，我试图使它多重定价，但它是相当缓慢的。在

Python - Set the first element of a generator - Applied to itertools

import time
import operator as op
from math import factorial
from itertools import combinations


def nCr(n, r):

    # https://stackoverflow.com/a/4941932/1167783

    r = min(r, n-r)
    if r == 0: 
        return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer // denom


def kthCombination(k, l, r):

    # https://stackoverflow.com/a/1776884/1167783

    if r == 0:
        return []
    elif len(l) == r:
        return l
    else:
        i = nCr(len(l)-1, r-1)
        if k < i:
            return l[0:1] + kthCombination(k, l[1:], r-1)
        else:
            return kthCombination(k-i, l[1:], r)


def iter_manual(n, p):

    numbers_list = [i for i in range(n)]

    for comb in xrange(factorial(n)/(factorial(p)*factorial(n-p))):

        x = kthCombination(comb, numbers_list, p)

        # Do something, for example, store those combinations
        # For timing i'm going to do something simple



def iter(n, p):

    for i in combinations([i for i in range(n)], p):

    # Do something, for example, store those combinations
    # For timing i'm going to do something simple
        x = i


#############################


if __name__ == "__main__":  

    n = 40
    p = 5

    print '%s combinations' % (factorial(n)/(factorial(p)*factorial(n-p)))

    t0_man = time.time()

    iter_manual(n, p)

    t1_man = time.time()
    total_man = t1_man - t0_man


    t0_iter = time.time()

    iter(n, p)

    t1_iter = time.time()
    total_iter = t1_iter - t0_iter

    print 'Manual: %s' %total_man
    print 'Itertools: %s' %total_iter
    print 'ratio: %s' %(total_man/total_iter)

Answer 1

这里有几个因素在起作用。在

最重要的是垃圾收集。任何生成大量不必要分配的方法都会因为GC暂停而变得缓慢。在这种情况下，列表理解是fast（对于Python），因为它们在分配和执行过程中都是高度优化的。在速度很重要的地方，最好列出理解力。在

接下来是函数调用。正如@roganjosh在评论中指出的，函数调用相对昂贵。如果函数生成大量垃圾或保留长时间的闭包，这一点（再次）尤其正确。在

现在我们来看看循环。垃圾也是最大的问题，把你的变量放到循环之外，在每次迭代中重用它们。在

最后一点，但肯定不是最不重要的一点是，Python在某种意义上是一种托管的语言：通常在CPython运行时上。在运行时本身实现的任何东西（特别是如果所讨论的东西是用C实现的，而不是Python本身）都将比您的（逻辑上等价的）代码更快。在

注

所有这些建议都不利于代码质量。小心使用。先做侧写。还请注意，编译器通常足够聪明，可以为您完成所有这些工作，例如，PyPy对同一代码的运行速度通常比标准Python运行时更快，因为它在运行代码时会为您进行这样的优化。在

注2

其中一个实现使用reduce。理论上讲，减少可能很快。但原因并不是很多，其中的主要原因可以概括为“圭多不在乎”。所以当速度很重要时不要使用reduce。在