Швидкість проходу циклів у Perl’i

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Маю перебірний алґоритм з поважною кількістю прокручування циклів. Питання: чи однаковою є швидкодія проходу по списку від першого до останнього елемента і навпаки. Під C відповідь була би очевидною, тут же — залежить від внутрішностей перла, яких я не знаю.

Тест 1 (проходи від першого до останнього).

my $bb; my @aa = 1..10000; my $t0 = time;
for (my $i = 0; $i <= $#aa; ++$i) {
for (my $j = 0; $j <= $i; ++$j) { $bb = $aa[$j].$aa[$j]; }
}
print (time — $t0), «\n»;

Тест 2 (проходи ззаду наперед).

my $bb; my @aa = 1..10000; my $t0 = time;
for (my $i = $#aa; $i >= 0; $i—) {
for (my $j = $i; $j >= 0; $j—) { $bb = $aa[$j].$aa[$j]; }
}
print (time — $t0), «\n»;

Другий тест працює на 5% повільніше. Але в реальній задачі трішечки зручніше було би ходити, все ж, ззаду наперед. От і виходить шило на мило. Чи, може, є якісь мануали щодо швидкодії на перлі? якісь дослідження? Щоб не відкривати цю америку заново :-)

Я розумію, що такі речі правильніше робити на тому ж C і, зрештою, так собі й планую — відкатати алґоритм на перлі, а потім перенести його «обчислювальну» частину під C. Але поки ще настане те «потім»...

Варіянти з прямим перебором списку (for my $a (@aa)) я теж пробував, до слова — вони дають суттєво гірші результати.

Теми: Perl

Ctrl + Enter

Павло Дзіковський 26.05.2011 16:55

Коментар порушує правила спільноти і видалений модераторами.

Леголас Трандуилович 26.05.2011 16:44

1. ну і яка відповідь тобі очевидна під С?
2. А ти впевнений що тобі принципові ті +/- 5%?
2.1 Хошеш анегдот про швидкодію перла? Программа на перлі має достатню швидкою якщо вона видає результат раніше ніж приходить бос і звільняє тебе за то що досі нема результату.

2.2 пам’ятаєш преше правило оптимізації? те яке говорить Ніколи не оптимізуй завчасно. Напиши свій алгоритм, поміряй швидкодію. Якщо швидокодія не задовільняє — оптимізуй.... і то знову ж таки помірявши що саме потребує тої оптимізації.

Відповісти

Підтримати

Павло Дзіковський 26.05.2011 16:56

:-))) По пунктах (нумеруєш, до речи — чому не від 0? ніпарядооок...).
1. Під C, так думаю, швидкість буде однаковою.

2. 5% — не принципові. Але до того, як я це перевірив, було зовсім не очевидно, що там 5%, а не 50% — тому й взявся це тестувати. Для прикладу — якщо крутити «відрізки списків» (for my $a (@bb[0..$i])) — швидкість, по першому враженню, падає вже доволі суттєво.

2.2 Тут маю якраз той самий виняточок, який підтверджує загальне правило — оскільки йдеться про один і той самий алґоритм. Але написати прохід в правильному напряму від початку — це просто, а правити навіть таку дрібницю, коли код розпухне — це вже буде зайва морока.

Павло Дзіковський 26.05.2011 11:44

RomanV 26.05.2011 11:39

Hi,

взял на себя смелость немного переписать кусок кода в таком направлении:

use Benchmark qw(:all) ;
timethese(10, {
’test1′ => sub {
my $bb; my @aa = 1..10000;
for (my $i = 0; $i <= $#aa; ++$i) {
for (my $j = 0; $j <= $i; ++$j) {
$bb = $aa[$j].$aa[$j];
}
}
},
’test2′ => sub {
my $bb; my @aa = 1..10000;
for (my $i = $#aa; $i >= 0; $i—) {
for (my $j = $i; $j >= 0; $j—) {
$bb = $aa[$j].$aa[$j];
}
}
},

});

Получил прямо противоположный результат: второй кусок кода на 3.5% быстрее.

Benchmark: timing 10 iterations of test1, test2...
test1: 286 wallclock secs (284.18 usr + 0.08 sys = 284.26 CPU) @ 0.04/s (n=10)

test2: 276 wallclock secs (274.61 usr + 0.08 sys = 274.69 CPU) @ 0.04/s (n=10)

Не сталкивался ни чем подобным (о чем спрашивается в теме: разное время при разном прохождении цикла), возможно коллеги поправят.

Ваш результат тестування тішить мене навіть більше, ніж свій власний :-) А за підказку, як культурно писати такі тести — спасибі!

Швидкість проходу циклів у Perl’i

4 коментарі

Підписатись на коментарі