Том Дафф (создатель устройства Даффа): " Если ваш код слишком медленный, вы должны сделать его быстрее. Если лучшего алгоритма нет, вы должны обрезать циклы. "
Я не согласен с тем, что это ситуация, когда хеш подходит лучше всего. Конечно, хеш - идиоматическое соответствие, это метод, упомянутый в perlfaq4, и он не тратит впустую элементы в вашем контейнере счетчика. Но он говорит о 100_000_000 целых числах от 1 до 999. Количество элементов, используемых в контейнере счетчика, незначительно. Количество итераций, необходимых для подсчета, очень значительно. 100 000 000 итераций занимают много времени.
Если вместо этого мы используем массив, мы выбрасываем элемент, индексированный в ноль. И если все целые числа имеют одинаковое значение, мы выбрасываем еще 998 элементов. Это такое большое дело? С другой стороны, несмотря на то, что как индексирование в массив, так и индексирование в хэш-агрегирование с O (1) операциями, нотация Big-O рассказывает только часть истории. И где 'n' - это общее количество целых чисел (100 000 000), и подход с использованием массива, и подход с использованием хэша являются O (n) операциями. Таким образом, все сводится к тому, какой подход является более эффективным в вычислительном отношении. Несмотря на то, что поиск в массиве и поиск в хеше - это O (1), оказывается, что для поиска в хэшах требуется значительно больше циклов.
Итерация более 100 000 000 целых чисел и увеличение счетчиков занимает время. Но оказывается, что внутри хеша это занимает больше времени, чем в массиве. Я знаю, что это кощунство с точки зрения "общих идиом". Но это может быть очень особый случай, когда эффективность вычислений важнее, чем идиоматический код, и важнее, чем использование памяти в качестве счетчика при увеличении объема памяти.
Вот код, демонстрирующий то, о чем я говорю:
use strict;
use warnings;
use Benchmark qw/ cmpthese /;
use List::Util qw/ max min /;
use Test::More;
use Readonly;
Readonly my $datasize => 100_000_000;
Readonly my $test_size => 100_000;
my @array_results = keys count_in_array( $test_size );
my @hash_results = keys count_in_hash( $test_size );
is( max( @array_results ), 999, "max( keys count_in_array() ) in range." );
is( min( @array_results ), 1, "min( keys count_in_array() ) in range." );
is( max( @hash_results ), 999, "max( keys count_in_hash() ) in range." );
is( min( @hash_results ), 1, "min( keys count_in_hash() ) in range." );
done_testing();
cmpthese( 5, {
array => sub{ my $results = count_in_array() },
hash => sub{ my $results = count_in_hash() },
} );
sub count_in_array {
my @container;
for( 1 .. $datasize ) {
$container[ int( rand( 999 ) ) + 1 ]++;
}
return {
map{
$container[$_] > 0
? ( $_ => $container[$_] )
: ()
} 1 .. $#container
};
}
sub count_in_hash {
my %container;
for( 1 .. $datasize ) {
$container{ int( rand ( 999 ) ) + 1 }++;
}
return \%container;
}
А вот результаты этого теста:
ok 1 - max( keys count_in_array() ) in range.
ok 2 - min( keys count_in_array() ) in range.
ok 3 - max( keys count_in_hash() ) in range.
ok 4 - min( keys count_in_hash() ) in range.
1..4
s/iter hash array
hash 24.9 -- -42%
array 14.5 72% --
Это большой выигрыш для массива (он на 72% быстрее). Если это все еще слишком медленно, обрежьте циклы, используя Inline :: C, чтобы переписать подход массива, используя массив целых чисел. Это будет на порядок быстрее.
Это может быть 3%, если оптимизация оправдана.
Итак, что мы делаем, чтобы смягчить последствия отказа от общепризнанной идиомы? Мы обязательно документируем, что мы делаем, чтобы будущие читатели (включая нас самих в будущем) понимали, что делается, и почему это делается не таким знакомым нам способом.
Только мой .02.