Perl - статьи

         

Не оптимизируйте код -- замеряйте его производительность!


Если Вам нужна функция для удаления дублирующихся элементов массива, вполне естественно, что однострочная версия наподобие этой:

sub uniq { return keys %{ { map {$_ => 1} @_ } } }

будет более эффективна, чем два оператора:

sub uniq { my %seen; return grep {!$seen{$_}++} @_; }

До тех пор пока Вы не будете глубоко знакомы с внутренностями Perl-интерпретатора (а в этом случае Вы наверняка уже будете решать вопросы посложнее), интуиция по поводу относительного быстродействия двух конструкций является ничем иным как неосознанным выбором.

Единственный способ узнать какая из двух альтернатив быстрее — замерить каждую из них. Со стандартным модулем Benchmark это просто:

# Короткий список не-совсе-уникальных значений... our @data = qw( do re me fa so la ti do );

# Различные кандидаты... sub unique_via_anon { return keys %{ { map {$_ => 1} @_ } }; }

sub unique_via_grep { my %seen; return grep { !$seen{$_}++ } @_; }

sub unique_via_slice { my %uniq; @uniq{ @_ } = (); return keys %uniq; }

# Сравнить, используя текущий набор данных из @data... sub compare { my ($title) = @_; print "\n[$title]\n";

# Создать сравнительную таблицу различных замеров времени, # при том, чтобы каждый запуск продолжался минимум 10 секунд... use Benchmark qw( cmpthese ); cmpthese -10, { anon => 'my @uniq = unique_via_anon(@data)', grep => 'my @uniq = unique_via_grep(@data)', slice => 'my @uniq = unique_via_slice(@data)', };

return; }

compare('8 элементов, 10% повторяющихся');

# Зве копии исходных данных... @data = (@data) x 2; compare('16 элементов, 56% повторяющихся');

# Сто копий исходных данных... @data = (@data) x 50; compare('800 элементов, 99% повторяющихся');

Процедура cmpthese() принимает в качестве аргумента число и далее ссылку на хэш с тестами. Число обозначает либо точное число запусков каждого теста (если это число положительное), либо количество секунд процессорного времени, в течение которого нужно гонять каждый тест (если число отрицательное). Обычные используемые значения — примерно 10'000 повторений или 10 CPU-секунд, но модуль предупредит Вас если тест будет слишком коротким для получения точного замера.


Ключи хэша с тестами представляют собой имена тестов, а их значения ‐ код соответствующих тестов. Эти значения могут быть как строками (которые будут выполнены с помощью eval) или ссылками на функции (которые будут вызваны напрямую).

Код для замера быстродействия, приведённый выше, выдаст что-то типа:

[8 элементов, 10% повторяющихся] Rate anon grep slice anon 28234/s -- -24% -47% grep 37294/s 32% -- -30% slice 53013/s 88% 42% --

[16 элементов, 56% повторяющихся] Rate anon grep slice anon 21283/s -- -28% -51% grep 29500/s 39% -- -32% slice 43535/s 105% 48% --

[800 элементов, 99% повторяющихся] Rate anon grep slice anon 536/s -- -65% -89% grep 1516/s 183% -- -69% slice 4855/s 806% 220% --

Каждая из выведенных таблиц содержит отдельную строку для каждого из поименованных тестов. В первой колонке -- абсолютная скорость каждого кандидата, в повторениях в секунду, а остальные колонки позволяют Вам сравнить полученный результат с остальными двумя тестами. Например последний тест показывает, что grep по сравнению с anon

выполняется в 1.83 раза быстрее (это 185 процента). Также grep был на 69 процентов медленнее (на -69 процентов быстрее) чем slic.

В целом, все три теста показывают, что решения, основанные на slice

неизменно быстрее других на этом наборе данных на этой конкретной машине. Также становится ясно, что с увеличением размера массива, slice

всё больше выигрывает у конкурентов.

Однако эти два заключения были сделаны на основании всего трёх наборов данных (а именно, на основании трёх запусков замера быстродействия). Для того, чтобы получить более показательное сравнение этих трёх методов, Вы также должны протестировать другие возможности, такие как длинный список неповторяющихся значений или короткий список, состоящий только из повторений.

Лучше всего попробуйте тесты на реальных данных, которые Вам нужно будет обрабатывать.

Например, если данные являются отсортированным списком из четверти миллиона слов, с минимальными повторениями, а после обработки список должен оставаться отсортированным, то вот тест для такого случая:



our @data = slurp '/usr/share/biglongwordlist.txt';

use Benchmark qw( cmpthese );

cmpthese 10, { # Note: the non-grepped solutions need a post-uniqification re-sort anon => 'my @uniq = sort(unique_via_anon(@data))', grep => 'my @uniq = unique_via_grep(@data)', slice => 'my @uniq = sort(unique_via_slice(@data))', };

Неудивительно, что решение, основанное на grep

здесь на высоте:

s/ iter anon slice grep anon 4.28 -- -3% -46% slice 4.15 3% -- -44% grep 2.30 86% 80% --

Причём решение с grep оставляет список отсортированным. Всё это даёт основания полагать, что превосходство решения, основанного на slice — это частный случай и это решение подрывается растущей стоимостью манипуляций с хэшами в случаях, когда хэш вырастает до слишком больших размеров.

Последний пример показывает, что выводы, сделанные Вами на основании тестирования быстродействия с какими-либо наборами данных, распространяются главным образом именно на этот конкретный вид данных.

Perl.com Compilation Copyright © 1998-2006 O'Reilly Media, Inc.


Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий