È `scipy.misc.comb` più veloce di un calcolo binomiale ad-hoc?

Question

È decisivo che ora lo scipy.misc.comb sia effettivamente più veloce dell'implementazione ad-hoc?

Secondo una vecchia risposta, Statistics: combinations in Python, questa funzione homebrew è più veloce di scipy.misc.comb quando calcolo combinazioni 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 

Ma dopo l'esecuzione dei test sulla mia macchina, questo non mi sembra il caso , utilizzando questo script:

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) 

ottengo il seguente output:

$ 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 

Il test di profiling del tempo ha mostrato che il nuovo scipy.misc.comb è più veloce della funzione ad-hoc choose()? C'è qualche errore nel mio script di test che rende i tempi imprecisi?

Perché lo scipy.misc.comb è più veloce ora? È a causa di alcuni trucchi di avvolgimento dello cython/c?

---

Edited

Dopo commento @WarrenWeckesser:

Utilizzando il valore predefinito virgola mobile ravvicinamento utilizzando scipy.misc.comb(), le interruzioni di calcolo a causa di trabocco virgola mobile.

(vedi http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.html per la documentazione)

Quando testato con exact=True che calcola con lunghe interi, invece di virgola mobile utilizzando la funzione qui sotto, è molto più lento nel calcolo 1000 combinazioni:

@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

riferimento al codice sorgente di scipy.misc.comb, la routine di aggiornamento il risultato è:

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

mentre la routine di aggiornamento che avete suggerito è:

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

mia ipotesi del motivo per cui l'implementazione di SciPy è più lento è dovuto al fatto che la subroutine comporta un divisione intera ad ogni iterazione mentre la tua chiama solo divisione una volta nell'istruzione return.