python - 在有和没有SciPy的情况下计算k组合的数量

Question

我感到困惑的是，函数 comb of SciPy似乎比朴素的Python实现要慢。这是解决Problem 53 of Project Euler的两个等效程序的测量时间。

使用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

输出:

1 loops, best of 3: 483 ms per loop

没有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

输出:

10 loops, best of 3: 86.9 ms per loop

第二个版本大约快5倍(在两台Mac上测试，python-2.7.9-1，IPython 2.3.1-py27_0)。这是SciPy( source code)的 comb函数的预期行为吗？我究竟做错了什么？

编辑(Anaconda 3.7.3-py27_0发行版中的SciPy):

import scipy; print scipy.version.version
0.12.0

编辑(与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

Answer 1

看来您可能运行了错误的计时，并测量了将scipy加载到内存所需的时间。当我运行时:

import timeit
from scipy.misc import comb
from math import factorial

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

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

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

T = timeit.Timer(test)
print T.repeat(3,50)

T2 = timeit.Timer(test2)
print T2.repeat(3,50)

我得到:

[2.2370951175689697, 2.2209839820861816, 2.2142510414123535]
[2.136591911315918, 2.138144016265869, 2.1437559127807617]

这表明scipy比python版本要快一些。