Benchmarking two methods of computing nCr.

gistfile1.py

# Benchmarking two methods of computing nCr.

# ncr1(1000, 5) 2.25343108177
# ncr2(1000, 5) 2.01950907707

# ncr1(1000, 500) 2.98434901237
# ncr2(1000, 500) 3.22741794586

# ncr1(1000000, 10) 3.69585800171
# ncr2(1000000, 10) 4.68463897705

# ncr1(1000000, 500) 4.11436390877
# ncr2(1000000, 500) 10.2328448296

import operator


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


def ncr2(n, r):
    r = min(r, n - r)
    count = 1
    for i in xrange(1, r + 1):
        count *= n - r + i
        count /= i
    return count


def runtimit(n, r, *args, **kwargs):
    print "ncr1(%d, %d)" % (n, r), timeit.timeit(lambda: ncr1(n, r), *args, **kwargs)
    print "ncr2(%d, %d)" % (n, r), timeit.timeit(lambda: ncr2(n, r), *args, **kwargs)
    print


if __name__ == '__main__':
    import timeit

    runtimit(1000, 5)
    runtimit(1000, 500, number=10000)
    runtimit(1000000, 10)
    runtimit(1000000, 500, number=10000)