`scipy.misc.comb`はアドホックな二項計算よりも高速ですか？

Question

scipy.misc.combが実際にアドホックな実装よりも高速になったことは間違いありませんか？組み合わせnCrを計算する際に、古い答え、Statistics: combinations in Pythonによると、この自作関数は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 

しかし、私自身のマシン上でいくつかのテストを実行した後、これはケースのように見えるしていません。このスクリプト使用：

：

from scipy.misc import comb 
import random, time 

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 

def timing(f): 
    def wrap(*args): 
     time1 = time.time() 
     ret = f(*args) 
     time2 = time.time() 
     print '%s function took %0.3f ms' % (f.__name__, (time2-time1)*1000.0) 
     return ret 
    return wrap 

@timing 
def test_func(combination_func, nk): 
    for n,k in nk: 
     combination_func(n, k) 

nk = [] 
for _ in range(1000): 
    n = int(random.random() * 10000) 
    k = random.randint(0,n) 
    nk.append((n,k)) 

test_func(comb, nk) 
test_func(choose, nk) 

を私は次の出力を得ます

$ 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 

時間プロファイリングテストでは、新しいがアドホックchoose()機能より高速であることが示されましたか？私のテストスクリプトに、タイミングが不正確なエラーがありますか？

scipy.misc.combが現在高速化しているのはなぜですか？ cython/cラップトリックのためですか？

---

が@WarrenWeckesserのコメントの後

編集：

scipy.misc.comb()を使用するときに点近似を浮動デフォルトを使用して、ために浮動小数点オーバーフローの計算休憩。アウト

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

[：

1000の組み合わせを計算するときに

代わりに以下の機能を使用して浮動小数点の長整数で計算し exact=Trueでテスト

が、それは多くの、より遅いです（ドキュメントのhttp://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.htmlを参照してください） ]：

$ 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 

あなたが提案更新ルーチンであるのに対し：

ntok = 1 
    ktok = 1 
    for t in xrange(1, min(k, n - k) + 1): 
     ntok *= n 
     ktok *= t 
     n -= 1 
    return ntok // ktok 

scipyのダウンロードの実装が遅い理由の私の推測では、サブルーチンは、それぞれの整数の除算を必要とするという事実によるものです反復処理では一回だけ除算を呼び出します。