эффективный способ захвата полномочий вектора

Question

Я написал код, который численно использует полиномы Лежандра до некоторого высокого n-го порядка. Например:

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

Если вектор x долго это может быть медленным. Я видел, что есть разница в производительности между словами x.^4 и x.*x.*x.*x, и я думал, что могу использовать это, чтобы улучшить свой код. Я использовал timeit и обнаружили, что для:

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

f4 является быстрее по фактор 2, чем остальные. Однако, когда я перехожу к x.^6, разница между (x.*x.*x).^2 и x.*x.*x.*x.*x.*x очень мала (хотя все остальные варианты медленнее).

Есть ли возможность рассказать, какой будет наиболее эффективный способ взять векторный вектор? Можете ли вы объяснить, почему существует такая большая разница в производительности?

Answer 1

Это не совсем ответ на ваш вопрос, но это может решить вашу проблему:

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 

Таким образом, вы делаете силу только один раз, и только с показателем 2. Этот прием может быть применен ко всем Многочлены Лежандра (в полиномах нечетной степени один x2 заменяется на x).

Answer 2

Вот некоторые мысли:

power(x,4) и x.^4 эквивалентны (только что прочитал документ).

x.*x.*x.*x, вероятно, оптимизирован для чего-то вроде x.^2.^2

---

x.^2.^2, вероятно, оценивается как: Возьмите квадрат каждого элемента (быстро), и возьмите квадрат, что снова (быстро снова).

x.^4, вероятно, непосредственно оценивается как: Возьмите четвертую мощность каждого элемента (медленно).

Не так странно видеть, что 2 быстрых операции занимают меньше времени, чем 1 медленная работа. Слишком плохо, что оптимизация не выполняется в случае питания 4, но, возможно, она не всегда будет работать или будет стоить (проверка ввода, память?).

---

О таймингах: На самом деле есть гораздо больше разницы, чем фактор 2!

Как вы называете их в функции теперь функция накладные расходы добавляются в каждом случае, делая относительные различия меньше:

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 

даст:

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

Таким образом, это почти разность фактора 10. Однако обратите внимание, что разница во времени в секундах по-прежнему незначительна, поэтому для большинства практических приложений я бы просто пошел на простой синтаксис.

Answer 3

Кажется, что Mathworks имеет специальные квадраты с ячейками в своей функции власти (к сожалению, это все встроенный закрытый источник, который мы не можем видеть). В моем тестировании на R2013b кажется, что .^, power и realpow используют тот же алгоритм. Для квадратов я считаю, что они имеют специальную оболочку 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)) 

Для кубов история отличается. Они больше не являются специальными. Опять же, .^, power и realpow все похожи, но гораздо медленнее, на этот раз:

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) 

Давайте прыгать до 16 власти, чтобы увидеть, как эти алгоритмы масштаба:

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 

Итак: .^, power и realpow все работают в течение постоянного времени относительно экспоненты, если только это не было специальным корпусом (-1 тоже, по-видимому, было специально обложено). Использование трюка exp(n*log(x)) также является постоянным временем относительно экспоненты и быстрее. Единственный результат я не совсем понимаю, почему повторное квадратирование медленнее, чем умножение.

Как и ожидалось, увеличение размера x в 100 раз увеличивает время аналогично для всех алгоритмов.

Итак, мораль истории? При использовании скалярных целых показателей всегда выполняйте умножение самостоятельно. В power много друзей, и друзья (экспоненты могут быть плавающей точкой, вектором и т. Д.). Единственные исключения - это то, где Mathworks выполнила оптимизацию для вас. В 2013b, кажется, x^2 и x^(-1). Надеюсь, они со временем добавят больше. Но, в целом, возведение в степень трудно и умножение легко. В коде, чувствительном к производительности, я не думаю, что вы можете ошибаться, всегда печатая x.*x.*x.*x. (Конечно, в вашем случае, следуйте советам Luis` и использовать промежуточные результаты в каждом члене!)

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