क्या `scipy.misc.comb` विज्ञापन-हॉक द्विपदीय गणना से तेज़ है?

Question

क्या यह निर्णायक है कि अब scipy.misc.comb विज्ञापन-क्रियान्वयन से वास्तव में तेज़ है?

एक पुराने जवाब है, Statistics: combinations in Python के अनुसार, इस homebrew समारोह scipy.misc.comb तुलना में तेजी से जब गणना के संयोजन 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 

लेकिन अपने ही मशीन पर कुछ परीक्षण चलाने के बाद, इस मामले की तरह प्रतीत नहीं होता , इस स्क्रिप्ट का उपयोग:

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 

क्या समय प्रोफाइलिंग परीक्षण दिखाता है कि नया 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 

जबकि अद्यतन दिनचर्या आप का सुझाव दिया है:

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

कारण है कि SciPy के कार्यान्वयन धीमी है की मेरा अनुमान है तथ्य यह है कि सबरूटीन प्रत्येक पर एक पूर्णांक विभाजन शामिल है की वजह से है पुनरावृत्ति जब आपका रिटर्न स्टेटमेंट पर केवल एक बार विभाजन को कॉल करता है।