efektywny sposób na przejęcie mocy wektora

Question

Napisałem kod, który numerycznie wykorzystuje wielomiany Legendre do pewnego wysokiego n-tego rzędu. Na przykład:

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

Jeśli wektor x jest długi, może się spowolnić. Widziałem, że istnieje różnica w wydajności między słowami x.^4 i x.*x.*x.*x i myślę, że mógłbym użyć tego do ulepszenia mojego kodu. Użyłem timeit i okazało się, że dla:

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

f4 jest szybciej przez czynnik 2 niż reszta. Jednak po przejściu na x.^6 różnica między (x.*x.*x).^2 i x.*x.*x.*x.*x.*x jest bardzo niewielka (podczas gdy wszystkie pozostałe opcje są wolniejsze).

Czy jest tam, aby powiedzieć, jaki będzie najskuteczniejszy sposób na wykorzystanie mocy wektora? Czy możesz wyjaśnić, dlaczego istnieje tak duża różnica w wydajności?

Answer 1

To nie jest dokładnie odpowiedź na swoje pytanie, ale może to rozwiązać problem:

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 

W ten sposób można zrobić zasilanie tylko raz i tylko z wykładnikiem 2. Ten trik można zastosować do wszystkich Wielomiany legendarne (w wielomianach stopnia nieparzystego jeden x2 jest zastępowany przez x).

Answer 2

Oto kilka myśli:

power(x,4) i x.^4 są równoważne (wystarczy przeczytać doc).

x.*x.*x.*x prawdopodobnie jest zoptymalizowany do czegoś jak x.^2.^2

---

x.^2.^2 prawdopodobnie jest oceniany jako: Weź kwadrat każdego elementu (fast) i wziąć kwadrat że znowu (szybko ponownie).

x.^4 jest prawdopodobnie bezpośrednio oceniane jako: Weź czwartą moc każdego elementu (wolno).

Nie jest tak dziwne, że 2 szybkie operacje zajmują mniej czasu niż 1 wolna operacja. Szkoda tylko, że optymalizacja nie jest wykonywana w przypadku power 4, ale być może nie zawsze będzie działać lub kosztować (sprawdzanie wejścia, pamięć?).

---

O czasie: w rzeczywistości jest o wiele więcej różnic niż współczynnik 2!

Jak nazywają je w funkcji pory napowietrznych funkcja dodaje się w każdym przypadku, co względne różnice mniejsze:

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 

dadzą:

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

Tak, to jest prawie różnica 10 czynników. Należy jednak zauważyć, że różnica czasu w sekundach jest wciąż niewielka, więc w przypadku większości praktycznych zastosowań wystarczyłaby prosta składnia.

Answer 3

Wygląda na to, że Mathworks posiada specjalne kwadratowe kwadraty w swojej funkcji mocy (niestety, wszystkie są wbudowane w zamknięte źródło, którego nie widzimy). W moich testach na R2013b wygląda na to, że używają tego samego algorytmu, co w przypadku wersji .^, power i realpow. Jeśli chodzi o kwadraty, uważam, że mają one specjalny przypadek 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)) 

W przypadku kostek historia jest inna. Nie są już specjalnymi przypadkami. Znowu .^, power i realpow wszystkie są podobne, ale znacznie wolniej tym razem: skok

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) 

Przejdźmy do 16 potęgi, aby zobaczyć jak to skala algorytmy:

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 

Więc: .^, power i realpow wszystkie działają w stałym czasie w odniesieniu do wykładnika, chyba że był to specjalny przypadek (-1 również wydaje się być specjalnym cased). Używanie triku exp(n*log(x)) to także stały czas w odniesieniu do wykładnika i szybszy. Jedynym rezultatem nie do końca rozumiem, dlaczego powtarzanie kwadratu jest wolniejsze niż mnożenie.

Zgodnie z oczekiwaniami zwiększenie rozmiaru x o współczynnik równy 100 zwiększa czas podobnie dla wszystkich algorytmów.

A więc, moralny z historii? Podczas używania skalarnych wykładników całkowitych, zawsze rób to samemu. Jest mnóstwo sprytów w power i znajomych (wykładnik może być zmiennoprzecinkowy, wektor itd.). Jedynymi wyjątkami są sytuacje, w których Mathworks przeprowadził optymalizację. W 2013b wydaje się być x^2 i x^(-1). Mam nadzieję, że dodadzą więcej w miarę upływu czasu. Generalnie jednak potęgowanie jest trudne, a mnożenie łatwe. W przypadku kodu wrażliwego na wydajność, nie sądzę, że możesz popełnić błąd, pisząc zawsze: x.*x.*x.*x. (Oczywiście, w przypadku wykonaj porady Luis` i wykorzystania wyników pośrednich w ramach każdego terminu!)

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