calculating the number of k-combinations with and without SciPy

Aristide Published at Dev

Aristide

I'm puzzled by the fact that the function comb of SciPy appears to be slower than a naive Python implementation. This is the measured time for two equivalent programs solving the Problem 53 of Project Euler.

With SciPy:

%%timeit
from scipy.misc import comb

result = 0
for n in range(1, 101):
    for k in range(1, n + 1):
        if comb(n, k) > 1000000:
            result += 1
result

Output:

1 loops, best of 3: 483 ms per loop

Without SciPy:

%%timeit
from math import factorial

def comb(n, k):
    return factorial(n) / factorial(k) / factorial(n - k)

result = 0
for n in range(1, 101):
    for k in range(1, n + 1):
        if comb(n, k) > 1000000:
            result += 1
result

Output:

10 loops, best of 3: 86.9 ms per loop

The second version is about 5 times faster (tested on two Macs, python-2.7.9-1, IPython 2.3.1-py27_0). Is this an expected behaviour of the comb function of SciPy (source code)? What am I doing wrong?

Edit (SciPy from the Anaconda 3.7.3-py27_0 distribution):

import scipy; print scipy.version.version
0.12.0

Edit (same difference outside IPython):

$ time python with_scipy.py
real    0m0.700s
user    0m0.610s
sys     0m0.069s

$ time python without_scipy.py
real    0m0.134s
user    0m0.099s
sys     0m0.015s

Aristide

Answering my own question. It seems that there exist two different functions for the same thing in SciPy. I'm not quite sure why. But the other one, binom, is 8.5 times faster than comb, and 1.5 times faster than mine, which is reassuring:

%%timeit
from scipy.special import binom
result = 0
for n in range(1, 101):
    for k in range(1, n + 1):
        if binom(n, k) > 1000000:
            result += 1
result

Output: