是`scipy.misc.comb`比临时二项式计算快吗？

Question

现在scipy.misc.comb确实比即席实现快吗？

根据一个古老的答案Statistics: combinations in Python，在计算组合nCr时，这个自制函数比scipy.misc.comb快：

def choose(n, k):
    """
    A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
    """
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in xrange(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

但在我自己的机器上运行了一些测试之后，使用以下脚本，情况似乎并非如此：

^{pr2}$

我得到以下输出：

$ python test.py
/usr/lib/python2.7/dist-packages/scipy/misc/common.py:295: RuntimeWarning: overflow encountered in exp
  vals = exp(lgam(N+1) - lgam(N-k+1) - lgam(k+1))
999
test_func function took 32.869 ms
999
test_func function took 1859.125 ms

$ python test.py
/usr/lib/python2.7/dist-packages/scipy/misc/common.py:295: RuntimeWarning: overflow encountered in exp
  vals = exp(lgam(N+1) - lgam(N-k+1) - lgam(k+1))
999
test_func function took 32.265 ms
999
test_func function took 1878.550 ms

时间分析测试是否显示新的scipy.misc.comb比特殊的choose()函数快吗？我的测试脚本中是否存在导致计时不准确的错误？在

为什么现在scipy.misc.comb更快？是因为一些cython/c包装技巧？

---

已编辑

@WarrenWeckesser评论后：

使用scipy.misc.comb()时使用默认的浮点近似，计算会因浮点溢出而中断。在

（有关文档，请参阅http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.html）

当使用exact=True进行测试时，它使用长整数而不是使用下面的函数计算浮点，在计算1000个组合时要慢得多：

@timing
def test_func(combination_func, nk):
    for i, (n,k) in enumerate(nk):
        combination_func(n, k, exact=True)

[出来]：

$ python test.py
test_func function took 3312.211 ms
test_func function took 1764.523 ms

$ python test.py
test_func function took 3320.198 ms
test_func function took 1782.280 ms

Answer 1

参考scipy.misc.comb的源代码，结果的更新例程是：

    val = 1
    for j in xrange(min(k, N-k)):
        val = (val*(N-j))//(j+1)
    return val

而您建议的更新程序是：

^{pr2}$

我对SciPy实现速度较慢的原因的猜测是，子例程在每次迭代中都涉及整数除法，而您的子程序在return语句中只调用一次除法。在