Брайан Д Фой предложил использовать хеш, который дает O (1) поисков, за счет немного более дорогого создания хешей. Существует методика, которую Марк Джейсон Доминус описывает в своей книге Perl высшего порядка, где хеш используется для запоминания (или кеширования) результатов подпрограммы для данного параметра. Так, например, если findit(1000) всегда возвращает одно и то же для данного параметра, нет необходимости каждый раз пересчитывать результат. Техника реализована в модуле Memoize (входит в ядро Perl).
Запоминание не всегда является победой. Иногда накладные расходы на запомненную обертку превышают затраты на вычисление результата. Иногда данный параметр вряд ли когда-либо будет проверен более одного раза или относительно несколько раз. И иногда нельзя гарантировать, что результат функции для данного параметра всегда будет одинаковым (т. Е. Кэш может устареть). Но если у вас дорогая функция со стабильными возвращаемыми значениями для каждого параметра, запоминание может быть большим выигрышем.
Так же, как ответ Брайана Д. Фоя использует хеш, Memoize использует хеш внутри. В реализации Memoize есть дополнительные издержки, но преимущество использования Memoize заключается в том, что он не требует рефакторинга исходной подпрограммы. Вы просто use Memoize;, а затем memoize( 'expensive_function' );, при условии, что оно соответствует критериям для извлечения выгоды из запоминания.
Я взял вашу оригинальную подпрограмму и преобразовал ее для работы с целыми числами (просто для простоты тестирования). Затем я добавил вторую версию, которая передала ссылку на исходный массив, а не копировала массив. С этими двумя версиями я создал еще два сабвуфера, которые я запомнил. Затем я провел сравнительный анализ четырех подводных лодок.
В бенчмаркинге мне приходилось принимать некоторые решения. Во-первых, сколько итераций для тестирования. Чем больше итераций мы тестируем, тем выше вероятность того, что мы получим хорошие попадания в кеш для запомненных версий. Затем я также должен был решить, сколько элементов поместить в массив выборок. Чем больше элементов, тем меньше вероятность попадания в кеш, но тем значительнее экономия при обращении к кешу. В итоге я выбрал массив для поиска, содержащий 8000 элементов, и выбрал поиск по 24000 итераций. Это означает, что в среднем должно быть два попадания в кэш на запомненный вызов. (Первый вызов с заданным параметром записывает в кеш, а второй и третий вызовы читают из кеша, поэтому в среднем два хороших попадания).
Вот код теста:
use warnings;
use strict;
use Memoize;
use Benchmark qw/cmpthese/;
my $n = 8000; # Elements in target array
my $count = 24000; # Test iterations.
my @a = ( 1 .. $n );
my @find = map { int(rand($n)) } 0 .. $count;
my ( $orx, $ormx, $opx, $opmx ) = ( 0, 0, 0, 0 );
memoize( 'orig_memo' );
memoize( 'opt_memo' );
cmpthese( $count, {
original => sub{ my $ret = original( $find[ $orx++ ], @a ); },
orig_memo => sub{ my $ret = orig_memo( $find[ $ormx++ ], @a ); },
optimized => sub{ my $ret = optimized( $find[ $opx++ ], \@a ); },
opt_memo => sub{ my $ret = opt_memo( $find[ $opmx++ ], \@a ); }
} );
sub original {
my ( $var, @a) = @_;
foreach my $e ( @a ) {
return 1 if $var == $e;
}
return 0;
}
sub orig_memo {
my ( $var, @a ) = @_;
foreach my $e ( @a ) {
return 1 if $var == $e;
}
return 0;
}
sub optimized {
my( $var, $aref ) = @_;
foreach my $e ( @{$aref} ) {
return 1 if $var == $e;
}
return 0;
}
sub opt_memo {
my( $var, $aref ) = @_;
foreach my $e ( @{$aref} ) {
return 1 if $var == $e;
}
return 0;
}
А вот и результаты:
Rate orig_memo original optimized opt_memo
orig_memo 876/s -- -10% -83% -94%
original 972/s 11% -- -82% -94%
optimized 5298/s 505% 445% -- -66%
opt_memo 15385/s 1657% 1483% 190% --
Как видите, запомненная версия вашей исходной функции была на самом деле медленнее. Это связано с тем, что на создание копий массива 8000 элементов была затрачена большая часть стоимости исходной подпрограммы в сочетании с тем фактом, что при работе с запомненной версией возникают дополнительные затраты на стек вызовов и бухгалтерию.
Но как только мы передадим ссылку на массив вместо копии, мы уберем затраты на передачу всего массива. Ваша скорость прыгает значительно. Но явным победителем является оптимизированная (то есть передаваемая ссылка на массив) версия, которую мы запомнили (кэшировали), на 1483% быстрее, чем ваша исходная функция. С запоминанием поиск O (n) происходит только при первой проверке заданного параметра. Последующие поиски происходят за O (1) раз.
Теперь вам нужно решить (с помощью бенчмаркинга), поможет ли вам запоминание. Конечно, передача массива ref делает. И если запоминание не поможет вам, возможно, лучше использовать метод хэширования Брайана. Но с точки зрения отсутствия необходимости переписывать большой объем кода, памятная записка в сочетании с передачей ссылки на массив может быть отличной альтернативой.