Я хочу многократно искать значения в массиве, который не изменяется.
До сих пор я делал это так: я помещал значения в хэш (поэтому у меня есть массив и хеш с по существу одним и тем же содержимым), и я ищу хэш с помощью exists.
Мне не нравятся две разные переменные (массив и хэш), которые сохраняют одно и то же; однако хэш намного быстрее для поиска.
Я узнал, что в Perl 5.10 есть оператор ~~ (smartmatch). Насколько это эффективно при поиске скаляра в массиве?
Если вы хотите найти одиночный скаляр в массиве, вы можете использовать List:: Util first подпрограмму. Он останавливается, как только он знает ответ. Я не ожидаю, что это будет быстрее, чем хэш-поиск, если у вас уже есть хэш, но если вы подумаете о создании хэша и его в памяти, вам может быть удобнее просто искать уже имеющийся массив.
Что касается умений оператора smart-match, если вы хотите увидеть, насколько он умен, проверьте его.:)
Существует не менее трех случаев, которые вы хотите изучить. В худшем случае каждый элемент, который вы хотите найти, находится в конце. Лучше всего, что каждый элемент, который вы хотите найти, находится в начале. Вероятным случаем является то, что элементы, которые вы хотите усреднить, находятся в середине.
Теперь, прежде чем я начну этот тест, я ожидаю, что если умное совпадение может быть короткое (и оно может быть записано в perlsyn), что лучшие времена будут оставаться неизменными, несмотря на размер массива, в то время как другие становятся все хуже. Если он не может замыкаться на короткое замыкание и должен каждый раз проверять весь массив, не должно быть разницы во времени, потому что каждый случай требует такого же объема работы.
Здесь контрольный показатель:
#!perl
use 5.12.2;
use strict;
use warnings;
use Benchmark qw(cmpthese);
my @hits = qw(A B C);
my @base = qw(one two three four five six) x ( $ARGV[0] || 1 );
my @at_end = ( @base, @hits );
my @at_beginning = ( @hits, @base );
my @in_middle = @base;
splice @in_middle, int( @in_middle / 2 ), 0, @hits;
my @random = @base;
foreach my $item ( @hits ) {
my $index = int rand @random;
splice @random, $index, 0, $item;
}
sub count {
my( $hits, $candidates ) = @_;
my $count;
foreach ( @$hits ) { when( $candidates ) { $count++ } }
$count;
}
cmpthese(-5, {
hits_beginning => sub { my $count = count( \@hits, \@at_beginning ) },
hits_end => sub { my $count = count( \@hits, \@at_end ) },
hits_middle => sub { my $count = count( \@hits, \@in_middle ) },
hits_random => sub { my $count = count( \@hits, \@random ) },
control => sub { my $count = count( [], [] ) },
}
);
Вот как это делали различные части. Обратите внимание, что это логарифмический график на обеих осях, поэтому склоны погружающихся линий не так близки, как они выглядят:
Итак, похоже, что оператор smart match немного умный, но на самом деле это вам не поможет, потому что вам все равно придется сканировать весь массив. Вы, вероятно, не знаете заранее, где найдете свои элементы. Я ожидаю, что хеш будет выполнять то же самое, что и лучший смарт-матч, даже если вам нужно отказаться от него.
Хорошо, так что умное совпадение - умное время два - это здорово, но реальный вопрос: "Должен ли я его использовать?". Альтернативой является хэш-поиск, и это подталкивало меня к тому, что я не рассматривал этот случай.
Как и в случае с любым эталоном, я начинаю думать о том, какими могут быть результаты, прежде чем я их испытаю. Я ожидаю, что если у меня уже есть хеш, поиск ценности будет молниеносно. Этот случай не является проблемой. Меня больше интересует случай, когда у меня еще нет хэша. Как быстро я могу сделать хэш и найти ключ? Я ожидаю, что это будет не так хорошо, но все же лучше, чем наихудший смарт-матч?
Прежде чем вы увидите контрольный показатель, помните, что почти никогда не хватает информации о том, какую технику вы должны использовать, просто просматривая цифры. Контекст проблемы выбирает лучший метод, а не самый быстрый, бесконтактный микро-тест. Рассмотрим несколько случаев, которые будут выбирать различные методы:
Теперь, учитывая эти соображения, я добавляю к своей предыдущей программе:
my %old_hash = map {$_,1} @in_middle;
cmpthese(-5, {
...,
new_hash => sub {
my %h = map {$_,1} @in_middle;
my $count = 0;
foreach ( @hits ) { $count++ if exists $h{$_} }
$count;
},
old_hash => sub {
my $count = 0;
foreach ( @hits ) { $count++ if exists $old_hash{$_} }
$count;
},
control_hash => sub {
my $count = 0;
foreach ( @hits ) { $count++ }
$count;
},
}
);
Вот сюжет. Цвета немного трудно отличить. Самая низкая строка - это случай, когда вам нужно создать хэш в любое время, когда вы хотите его искать. Это очень плохо. Самые высокие две (зеленые) линии - это управление хешем (на самом деле нет хэша) и существующий поиск хэша. Это график журнала/журнала; эти два случая быстрее, чем даже интеллектуальный контроль соответствия (который просто вызывает подпрограмму).
Есть несколько других замечаний. Строки для "случайного" случая немного отличаются. Это понятно, потому что каждый контрольный показатель (так, как только один раз в масштабе массива запускается) случайным образом помещает хитовые элементы в массив-кандидат. Некоторые прогоны ставят их немного раньше, а некоторые немного позже, но поскольку я только создаю массив @random один раз за один запуск всей программы, они немного перемещаются. Это означает, что удары в линии незначительны. Если бы я пробовал все позиции и усреднял, я ожидал, что "случайная" строка будет такой же, как "средняя".
Теперь, глядя на эти результаты, я бы сказал, что смарт-матч намного быстрее в худшем случае, чем хэш-поиск в худшем случае. В этом есть смысл. Чтобы создать хеш, я должен посетить каждый элемент массива, а также сделать хэш, который много копирует. Нет копирования с умным совпадением.
Вот еще один случай, который я не буду изучать. Когда хэш становится лучше, чем умный матч? То есть, когда накладные расходы на создание хэша распространяются достаточно на повторные поиски, что хэш является лучшим выбором?
Быстро для небольших количеств потенциальных совпадений, но не быстрее, чем хэш. Хеши - действительно правильный инструмент для тестирования набора членства. Поскольку хэш-доступ равен O (log n), а smartmatch в массиве все еще O (n) линейное сканирование (хотя и короткое замыкание, в отличие от grep), с большим количеством значений в разрешенных совпадениях, smartmatch становится относительно хуже.
#!perl
use 5.12.0;
use Benchmark qw(cmpthese);
my @hits = qw(one two three);
my @candidates = qw(one two three four five six); # 50% hit rate
my %hash;
@hash{@hits} = ();
sub count_hits_hash {
my $count = 0;
for (@_) {
$count++ if exists $hash{$_};
}
$count;
}
sub count_hits_smartmatch {
my $count = 0;
for (@_) {
$count++ when @hits;
}
$count;
}
say count_hits_hash(@candidates);
say count_hits_smartmatch(@candidates);
cmpthese(-5, {
hash => sub { count_hits_hash((@candidates) x 1000) },
smartmatch => sub { count_hits_smartmatch((@candidates) x 1000) },
}
);
Rate smartmatch hash
smartmatch 404/s -- -65%
hash 1144/s 183% --
"Умный" в "умном матче" не касается поиска. Это о правильной работе в нужное время в зависимости от контекста.
Вопрос о том, нужно ли быстрее прокручивать массив или индекс в хэш, - это то, что вам нужно было бы тестировать, но в целом он должен быть довольно маленьким массивом, который можно ускорить, чем индексировать в хэш.