суббота, 25 июля 2009 г.

Сортировка Шварца

Представим, что у нас есть масив @ar , нужно получить масив @ar_new отортировав масив @ar следующим образом :
@ar_new = sort { slow_sub ($a) <=> slow_sub($b) } @ar 
Все бы хорошо но для сортировки n елементов блок сравнения будет вызван примерно n log n раз, а каждое сравнение это двойной вызов slow_sub. И в данной ситуации сортировка Шварца все решает.

@ar_new = map  { $_->[0] } 
                       sort { $a->[1] <=> $b->[1] }  
          map  { [ $_, slow_sub($_) ] } @ar;
Теперь slow_sub будет вызвана для каждого значени всего один раз.

2 коммент.:

zantor комментирует...

koorchik, баяним? ;)

koorchik комментирует...

Для кого "бояним", а для кого и откровение, помнится объяснял кому-то это даже ;)

Отправить комментарий

Не забудьте добавить себя в постоянные читатели и включить уведомления о новых комментариях, либо воспользуйтесь RSS каналом ;)