Python - Optimizing combination generation

Question

Why is the first method so slow?

It can be up to 1000 times slower, any ideas on how to make it faster?

In this case, performance is number one priority. In my first attempt I tried to make it multipricessing, but it was quite slow as well.

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)

Please add a description of what the indended purpose is of your code. — khelwood, Sep 15 '17 at 11:28
@Carcigenicate think OP is asking why one implementation (using `reduce`) is slower than another (using `for...`). Which is a totally valid (if vaguely worded) SO question. — Jared Smith, Sep 15 '17 at 11:30
Well, `iter_manual` is calling a function (`kthCombination`) on every iteration of the `for` loop, which itself calls `nCr`, while `iter` isn't really doing anything. And `kthCombination` looks recursive? — roganjosh, Sep 15 '17 at 11:31
@JaredSmith Oh, whoops. Missed the comparison part. Good call. — Carcigenicate, Sep 15 '17 at 11:31
Also, `itertools` is [written in C](https://github.com/python/cpython/blob/master/Modules/itertoolsmodule.c) while your first approach relies on Python `for` loops, which cannot compete. — roganjosh, Sep 15 '17 at 11:41

Jared Smith · Answer 1 · 2017-09-15T11:47:43.830

There are several factors at play here.

The most important is garbage collection. Any method that generates a lot of unnecessary allocations is going to be slow because of GC pauses. In this vein, list comprehensions are fast (for Python) because they are highly optimized under the hood in their allocation and execution. Wherever speed is important, prefer list comprehensions.

Next up you've got function calls. Function calls are relatively expensive as @roganjosh points out in the comments. This is (again) particularly true if the function generates a lot of garbage or holds on to long-lived closures.

Now we come to loops. Garbage is again the biggest concern, hoist your variables outside the loop and reuse them on each iteration.

Last but certainly not least is that Python is, in a sense, a hosted language: generally on the CPython runtime. Anything implemented in the runtime itself (particularly if the thing in question is implemented in C rather than Python itself) is going to be faster than your (logically equivalent) code.

NOTE

All of this advice is detrimental to code quality. Use with caution. Profile first. Also note that compilers are generally smart enough to do all of this for you, for instance PyPy will generally run faster for the same code than the standard Python runtime because it does optimizations like this for you when it runs your code.

NOTE 2

One of the implementations uses reduce. In theory, reduce could be fast. But it isn't for lots of reasons, the chief of which could possibly be summed up as "Guido didn't/doesn't care". So don't use reduce when speed is important.

Python - Optimizing combination generation

1 Answers1

NOTE

NOTE 2