"scipy.misc.comb" ad hoc bir binom hesaplamasından daha mı hızlı?

Question

scipy.misc.comb'un artık anlık uygulamadan daha hızlı olduğu kesin midir?

eski cevap, Statistics: combinations in Python göre bu homebrew fonksiyon hızlı scipy.misc.comb daha hesaplanırken kombinasyonlar nCr geçerli:

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 

Fakat kendi makinede bazı testler çalıştırdıktan sonra, bu vaka gibi görünmüyor Bu komut dosyası kullanarak:

: aşağıdaki çıktı üretmesi olsun

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 

Zaman profili oluşturma testi, yeni scipy.misc.comb'un, geçici choose() işlevinden daha hızlı olduğunu gösterdi mi? Test komutumda zamanlamayı yanlış yapan herhangi bir hata var mı?

Neden scipy.misc.comb şimdi daha hızlıdır? Bazı cython/c kaydırma hileleri yüzünden mi?

---

@WarrenWeckesser yorumunun ardından

EDITED:

scipy.misc.comb() kullanırken noktası yaklastırmasını yüzen varsayılan kullanarak, çünkü kayan nokta taşması nedeniyle hesaplama sonları. üzerinden

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

[:

1000 kombinasyonlar hesaplanırken

yerine aşağıdaki fonksiyonunu kullanarak kayan nokta uzun tamsayı ile hesaplar exact=True ile test

, bu çok daha yavaş (belgelerine http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.html bakınız) ]:

$ 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 kaynak kodu, güncelleştirme rutini atfen Sonuç şudur: önerilen güncelleme rutindir

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

oysa:

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

scipy en uygulaması yavaştır nedeni de Benim tahminim altyordamı her birinde bir tamsayı bölme içerdiğini gerçeği nedeniyle Yineleme, yalnızca sizin beyannamenizde bir kez geri dönüş bildirimi olarak çağırır.