Có phải `scipy.misc.comb` nhanh hơn tính toán nhị thức đặc biệt không?

Question

Kết luận rằng bây giờ scipy.misc.comb có thực sự nhanh hơn so với triển khai quảng cáo đặc biệt không?

Theo một câu trả lời cũ, Statistics: combinations in Python, chức năng này homebrew là nhanh hơn so với scipy.misc.comb khi tính kết hợp 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 

Nhưng sau khi chạy một số xét nghiệm trên máy tính của riêng tôi, điều này dường như không giống như trường hợp , sử dụng kịch bản này:

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) 

tôi nhận được kết quả như sau:

$ 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 

Kiểm tra hồ sơ thời gian có hiển thị rằng scipy.misc.comb mới nhanh hơn chức năng quảng cáo đặc biệt choose() không? Có lỗi nào trong tập lệnh thử nghiệm của tôi khiến thời gian không chính xác không?

Tại sao bây giờ scipy.misc.comb nhanh hơn? Đó là vì một số thủ thuật gói cython/c?

---

EDITED

Sau khi bình luận @WarrenWeckesser:

Sử dụng mặc định nổi xấp xỉ điểm khi sử dụng scipy.misc.comb(), vỡ tính toán vì nổi tràn điểm.

(xem http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.misc.comb.html cho tài liệu)

Khi thử nghiệm với exact=True mà tính với số nguyên dài thay vì dấu chấm động bằng cách sử dụng chức năng dưới đây, nó chậm hơn rất nhiều khi tính toán 1000 kết hợp:

@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

Tham khảo mã nguồn của scipy.misc.comb, thường xuyên cập nhật kết quả là:

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

trong khi thói quen cập nhật bạn đề nghị là:

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

đoán của tôi về lý do tại sao thực hiện scipy là chậm hơn là do thực tế rằng chương trình con liên quan đến một bộ phận nguyên tại mỗi lặp lại trong khi bạn chỉ gọi phân chia một lần tại câu lệnh trả về.