tính đa thức tính toán đa thức hiệu quả

Question

Tôi đang cố gắng đánh giá đa thức (mức 3'd) bằng cách sử dụng gọn gàng. Tôi thấy rằng làm điều đó bằng mã python đơn giản sẽ hiệu quả hơn nhiều.

import numpy as np 
import timeit 

m = [3,7,1,2] 

f = lambda m,x: m[0]*x**3 + m[1]*x**2 + m[2]*x + m[3] 
np_poly = np.poly1d(m) 
np_polyval = lambda m,x: np.polyval(m,x) 
np_pow = lambda m,x: np.power(x,[3,2,1,0]).dot(m) 

print 'result={}, timeit={}'.format(f(m,12),timeit.Timer('f(m,12)', 'from __main__ import f,m').timeit(10000)) 
result=6206, timeit=0.0036780834198 

print 'result={}, timeit={}'.format(np_poly(12),timeit.Timer('np_poly(12)', 'from __main__ import np_poly').timeit(10000)) 
result=6206, timeit=0.180546045303 

print 'result={}, timeit={}'.format(np_polyval(m,12),timeit.Timer('np_polyval(m,12)', 'from __main__ import np_polyval,m').timeit(10000)) 
result=6206, timeit=0.227771043777 

print 'result={}, timeit={}'.format(np_pow(m,12),timeit.Timer('np_pow(m,12)', 'from __main__ import np_pow,m').timeit(10000)) 
result=6206, timeit=0.168987989426 

Tôi có bỏ lỡ điều gì đó không?

Có cách nào khác để đánh giá một đa thức không?

Answer 1

Vâng, nhìn vào việc thực hiện polyval (đó là hàm cuối cùng được gọi khi bạn đánh giá poly1d), có vẻ như người triển khai đã quyết định bao gồm một vòng lặp rõ ràng ... Từ nguồn của 1.6.2:

def polyval(p, x): 
    p = NX.asarray(p) 
    if isinstance(x, poly1d): 
     y = 0 
    else: 
     x = NX.asarray(x) 
     y = NX.zeros_like(x) 
    for i in range(len(p)): 
     y = x * y + p[i] 
    return y 

Một mặt, tránh vòng tua cấp có lợi thế về mặt tốc độ thuận lợi, mặt khác, vòng tua vít có nhiều thứ.

Dưới đây là một sự thay thế NumPy-ish implemenation:

POW = np.arange(100)[::-1] 
def g(m, x): 
    return np.dot(m, x ** POW[m.size : ]) 

Đối với tốc độ, tôi tránh tái tạo mảng điện trên mỗi cuộc gọi. Ngoài ra, để được công bằng khi điểm chuẩn chống lại numpy, bạn nên bắt đầu với mảng numpy, không danh sách, để tránh hình phạt của chuyển đổi danh sách để gumpy trên mỗi cuộc gọi.

Vì vậy, khi thêm m = np.array(m), số g ở trên chỉ chạy chậm hơn khoảng 50% so với f của bạn.

Mặc dù là chậm hơn trên ví dụ bạn đăng, để đánh giá một đa thức độ thấp trên một vô hướng x, bạn thực sự không thể làm nhanh hơn nhiều so với một implemenation explict (như f của bạn) (tất nhiên bạn có thể , nhưng có lẽ không nhiều mà không cần viết mã cấp thấp hơn). Tuy nhiên, đối với các mức độ cao hơn (nơi bạn phải thay thế biểu thức giải thích bằng một loại vòng lặp), cách tiếp cận gọn gàng (ví dụ: g) sẽ chứng minh nhanh hơn khi mức độ tăng lên và cũng cho đánh giá vectorized, tức là khi x là một vectơ .

Answer 2

Giống như 23 năm trước, tôi đã kiểm tra một bản sao của Press et al Bí quyết số trong C từ thư viện của trường đại học. Có rất nhiều thứ mát mẻ trong cuốn sách đó, nhưng có một đoạn mà đã bị mắc kẹt với tôi trong những năm qua, page 173 here:

Chúng tôi giả định rằng bạn biết đủ không bao giờ để đánh giá một đa thức theo cách này:

p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; 

hoặc (thậm chí tồi tệ hơn!),

p=c[0]+c[1]*x+c[2]*pow(x,2.0)+c[3]*pow(x,3.0)+c[4]*pow(x,4.0); 

Hãy đến sự (máy tính) cách mạng, tất cả những người bị kết tội về hành vi tội phạm như vậy sẽ sum được thực thi một cách nhanh chóng, và các chương trình của họ sẽ không !Đó là một vấn đề của hương vị, tuy nhiên, cho dù để viết

p = c[0]+x*(c[1]+x*(c[2]+x*(c[3]+x*c[4]))); 

hoặc

p = (((c[4]*x+c[3])*x+c[2])*x+c[1])*x+c[0]; 

Vì vậy, nếu bạn đang thực sự lo lắng về hiệu suất, bạn muốn thử rằng, sự khác biệt sẽ rất lớn cho các đa thức mức độ cao hơn:

In [24]: fast_f = lambda m, x: m[3] + x*(m[1] + x*(m[2] + x*m[3])) 

In [25]: %timeit f(m, 12) 
1000000 loops, best of 3: 478 ns per loop 

In [26]: %timeit fast_f(m, 12) 
1000000 loops, best of 3: 374 ns per loop 

Nếu bạn muốn dính với vón cục, có một lớp đa thức mới chạy nhanh hơn 2xtrên hệ thống của tôi, nhưng vẫn là chậm hơn nhiều so với các vòng trước:

In [27]: np_fast_poly = np.polynomial.polynomial.Polynomial(m[::-1]) 

In [28]: %timeit np_poly(12) 
100000 loops, best of 3: 15.4 us per loop 

In [29]: %timeit np_fast_poly(12) 
100000 loops, best of 3: 8.01 us per loop