Czy `scipy.misc.comb` jest szybszy niż obliczanie dwumianowe ad-hoc?

Question

Czy jest przekonujące, że teraz scipy.misc.comb jest rzeczywiście szybszy niż implementacja ad-hoc?

Według starej odpowiedź, Statistics: combinations in Python ten homebrew funkcja jest szybszy niż scipy.misc.comb kiedy liczące kombinacje nCr:

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 

ale po uruchomione pewne testy na moim komputerze, to nie wydaje się sprawy za pomocą tego skryptu:

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) 

uzyskać następujące dane wyjściowe:

$ 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 

Czy test profilowania czasu wykazał, że nowy scipy.misc.comb jest szybszy niż funkcja ad-hoc choose()? Czy wystąpił błąd w moim skrypcie testowym, który powoduje, że czas jest niedokładny?

Dlaczego teraz scipy.misc.comb jest szybszy? To z powodu niektórych sztuczek owijających cython/c?

---

EDITED

Po @WarrenWeckesser komentarza:

Korzystanie z domyślnego zmiennoprzecinkowych przybliżenie podczas korzystania scipy.misc.comb(), przerwy obliczeń zmiennoprzecinkowych z powodu przepełnienia.

(patrz http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.html dla dokumentacji)

Kiedy testowane exact=True który oblicza z długich liczb całkowitych zamiast zmiennoprzecinkowych użyciu funkcji poniżej, jest to o wiele wolniej przy obliczaniu 1000 kombinacje:

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

[out ]:

$ 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

Odnosząc się do kodu źródłowego scipy.misc.comb, procedura aktualizacji wynik jest:

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

podczas rutynowej aktualizacji zasugerował to:

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

Domyślam z powodów realizacja scipy jest wolniejsze ze względu na fakt, że podprogram wiąże się podział całkowitej na siebie iteracja, podczas gdy twoja wywołuje podział tylko raz na oświadczeniu zwrotnym.