cách hiệu quả để lấy quyền hạn của một vector

Question

Tôi đã viết một mã số sử dụng đa thức Legendre lên đến một số thứ tự cao thứ n. Ví dụ:

.... 
case 8 
p = (6435*x.^8-12012*x.^6+6930*x.^4-1260*x.^2+35)/128; return 
case 9 
... 

Nếu vectơ x lâu thì điều này có thể chậm. Tôi thấy rằng có sự khác biệt hiệu suất giữa số x.^4 và x.*x.*x.*x và nghĩ rằng tôi có thể sử dụng điều này để cải thiện mã của mình. Tôi đã sử dụng timeit và thấy rằng cho:

x=linspace(0,10,1e6); 
f1= @() power(x,4) 
f2= @() x.4; 
f3= @() x.^2.^2 
f4= @() x.*x.*x.*x 

f4 là nhanh bởi một yếu tố hơn phần còn lại. Tuy nhiên, khi tôi truy cập x.^6, có rất ít sự khác biệt giữa (x.*x.*x).^2 và x.*x.*x.*x.*x.*x (trong khi tất cả các tùy chọn khác đều chậm hơn).

Có cách nào để cho biết cách hiệu quả nhất để nắm lấy sức mạnh của véc tơ là gì? Bạn có thể giải thích tại sao có sự khác biệt lớn về hiệu suất?

Answer 1

Đây không phải là chính xác một câu trả lời cho câu hỏi của bạn, nhưng nó có thể giải quyết vấn đề của bạn:

x2 = x.*x; % or x.^2 or power(x,2), whichever is most efficient 
p = ((((6435*x2-12012)*x2+6930)*x2-1260)*x2+35)/128 

Bằng cách này bạn làm sức mạnh chỉ một lần, và chỉ với số mũ 2. Thủ thuật này có thể được áp dụng cho tất cả Đa thức Legendre (trong các đa thức bậc lẻ một x2 được thay thế bằng x).

Answer 2

Dưới đây là một vài suy nghĩ:

power(x,4) và x.^4 là tương đương (chỉ đọc doc).

x.*x.*x.*x có lẽ là tối ưu hóa để một cái gì đó giống như x.^2.^2

---

x.^2.^2 có lẽ đánh giá là: Hãy bình phương của mỗi phần tử (nhanh), và lấy vuông đó một lần nữa (nhanh một lần nữa).

x.^4 có thể được đánh giá trực tiếp là: Lấy công suất thứ tư của mỗi phần tử (chậm).

Nó không phải là quá lạ để thấy rằng 2 hoạt động nhanh chóng mất ít thời gian hơn 1 hoạt động chậm. Chỉ là quá xấu mà tối ưu hóa không được thực hiện trong trường hợp 4 quyền lực, nhưng có lẽ nó sẽ không luôn luôn làm việc hoặc đi kèm với chi phí (kiểm tra đầu vào, bộ nhớ?).

---

Giới thiệu về thời gian: Trên thực tế có sự khác biệt nhiều hơn hệ số 2!

Như bạn gọi cho họ trong một chức năng hiện nay, chức năng chi phí được bổ sung trong từng trường hợp, làm cho sự khác biệt tương đối nhỏ:

y=x;tic,power(x,4);toc 
y=x;tic,x.^4;toc 
y=x;tic,x.^2.^2;toc 
y=x;tic,x.*x.*x.*x;toc 

sẽ cung cấp cho:

Elapsed time is 0.034826 seconds. 
Elapsed time is 0.029186 seconds. 
Elapsed time is 0.003891 seconds. 
Elapsed time is 0.003840 seconds. 

Vì vậy, nó là gần một yếu tố 10 khác biệt. Tuy nhiên, lưu ý rằng sự khác biệt về thời gian tính bằng giây vẫn còn nhỏ, vì vậy đối với hầu hết các ứng dụng thực tế, tôi chỉ cần đi theo cú pháp đơn giản.

Answer 3

Dường như Mathworks có các ô vuông đặc biệt trong chức năng nguồn của nó (thật không may, đó là tất cả các nguồn đóng được xây dựng mà chúng ta không thể nhìn thấy). Trong thử nghiệm của tôi trên R2013b, có vẻ như .^, power và realpow sử dụng cùng một thuật toán. Đối với các ô vuông, tôi tin rằng chúng có đặc biệt là x.*x.

1.0x (4.4ms): @()x.^2 
1.0x (4.4ms): @()power(x,2) 
1.0x (4.5ms): @()x.*x 
1.0x (4.5ms): @()realpow(x,2) 
6.1x (27.1ms): @()exp(2*log(x)) 

Đối với hình khối, câu chuyện khác. Chúng không còn được bao bọc đặc biệt nữa. Một lần nữa, .^, power, và realpow tất cả đều giống nhau, nhưng chậm hơn thời gian này:

1.0x (4.5ms): @()x.*x.*x 
1.0x (4.6ms): @()x.*x.^2 
5.9x (26.9ms): @()exp(3*log(x)) 
13.8x (62.3ms): @()power(x,3) 
14.0x (63.2ms): @()x.^3 
14.1x (63.7ms): @()realpow(x,3) 

Hãy nhảy lên với sức mạnh 16 để xem cách các thuật toán quy mô:

1.0x (8.1ms): @()x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x 
2.2x (17.4ms): @()x.^2.^2.^2.^2 
3.5x (27.9ms): @()exp(16*log(x)) 
7.9x (63.8ms): @()power(x,16) 
7.9x (63.9ms): @()realpow(x,16) 
8.3x (66.9ms): @()x.^16 

Vì vậy: .^, power và realpow tất cả chạy trong một thời gian liên tục liên quan đến số mũ, trừ khi nó được đặc biệt cased (-1 cũng dường như đã được đặc biệt cased). Sử dụng thủ thuật exp(n*log(x)) cũng là thời gian liên tục liên quan đến số mũ và nhanh hơn. Kết quả duy nhất tôi không hoàn toàn hiểu tại sao bình phương lặp đi lặp lại là chậm hơn so với phép nhân.

Như dự kiến, tăng kích thước x với hệ số là 100 sẽ tăng thời gian tương tự cho tất cả các thuật toán.

Vì vậy, đạo đức của câu chuyện? Khi sử dụng số nguyên nguyên vô hướng, luôn tự làm phép nhân. Có rất nhiều thông minh trong số power và bạn bè (số mũ có thể là dấu phẩy động, vectơ, v.v.). Ngoại lệ duy nhất là nơi Mathworks đã thực hiện tối ưu hóa cho bạn. Trong năm 2013b, có vẻ như là x^2 và x^(-1). Hy vọng rằng họ sẽ thêm nhiều thời gian hơn. Tuy nhiên, nói chung, lũy thừa là khó và nhân rất dễ dàng. Trong mã hiệu suất nhạy cảm, tôi không nghĩ rằng bạn có thể đi sai bằng cách luôn gõ x.*x.*x.*x. (Tất nhiên, trong trường hợp của bạn, hãy làm theo lời khuyên của Luis` và tận dụng các kết quả trung gian trong mỗi học kỳ!)

function powerTest(x) 

f{1} = @() x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x.*x; 
f{2} = @() x.^2.^2.^2.^2; 
f{3} = @() exp(16.*log(x)); 
f{4} = @() x.^16; 
f{5} = @() power(x,16); 
f{6} = @() realpow(x,16); 

for i = 1:length(f) 
    t(i) = timeit(f{i}); 
end 

[t,idxs] = sort(t); 
fcns = f(idxs); 

for i = 1:length(fcns) 
    fprintf('%.1fx (%.1fms):\t%s\n',t(i)/t(1),t(i)*1e3,func2str(fcns{i})); 
end