Самый быстрый способ (время выполнения), чтобы найти самый длинный элемент в списке
Это самый быстрый способ (время выполнения) для поиска самого длинного элемента в списке?
#!/usr/bin/env perl
use warnings;
use 5.012;
use List::Util qw(reduce);
use List::Util::XS;
my @array = qw( one two three four five six seven eight nine ten eleven );
my $l = reduce{ length($a) > length($b) ? $a : $b } @array;
say $l;
Ответы
Ответ 1
Когда вы пытаетесь найти только один элемент списка, нет необходимости строить структуру данных размера N, как это было сделано здесь. Самый быстрый способ O(N) сделать это - это перемещение массива, отслеживание самого большого элемента. Таким образом, у вас есть O(N) доступ к списку и O(1) использование памяти.
sub longest {
my $max = -1;
my $max_i = 0;
for (0 .. $#_) { # for each index
my $len = length $_[$_]; # only get length once per item
if ($len > $max) { # save index and update max if larger
$max = $len;
$max_i = $_;
}
}
$_[$max_i] # return the largest item
}
Если вы собираетесь использовать вышеприведенный код много раз, я бы предложил вставить тело подпрограммы.
EDIT:
drewk benchmark показал, что индекс массива в приведенном выше коде является немного узким местом. Экспериментируя немного больше, я, наконец, нашел метод, который быстрее, чем решение reduce:
sub fastest {
my $max = -1;
my $max_ref;
for (@_) {
if (length > $max) { # no temp variable, length() twice is faster
$max = length;
$max_ref = \$_; # avoid any copying
}
}
$$max_ref
}
что приводит к следующему эталону:
Rate longest drewk reduce fastest
longest 44245/s -- -21% -30% -47%
drewk 55854/s 26% -- -11% -33%
reduce 63014/s 42% 13% -- -25%
fastest 83638/s 89% 50% 33% --
Ответ 2
Вот немного измененная версия OMG_peanuts с переменными и для меньших переменных:
my $len = length $array[0];
my $longest = 0;
for my $i (1 .. $#array) {
my $i_len = length $array[$i];
if($i_len > $len) {
$longest = $i;
$len = $i_len;
}
}
my $l = $array[$longest];
Я немного играл с бенчмарками, получая это за небольшие числа (оригинальный массив)
Rate REDUCE TMPVAR TMPFOR
REDUCE 234862/s -- -0% -7%
TMPVAR 235643/s 0% -- -6%
TMPFOR 251326/s 7% 7% --
и это для большего количества или элементов (исходный массив x 100)
Rate TMPVAR TMPFOR REDUCE
TMPVAR 3242/s -- -28% -32%
TMPFOR 4503/s 39% -- -5%
REDUCE 4750/s 47% 5% --
Обратите внимание, что пригодность алгоритма сильно зависит от специфики данных (я бы предположил, что более длинные строки могут увеличить вес функции length в алгоритме).
РЕДАКТИРОВАТЬ. Вот полный код для теста (длинная версия массива, short отсутствует x 100 в определении массива)
use Benchmark qw(:all);
use List::Util qw(reduce);
my @array = qw( one two three four five six seven eight nine ten eleven ) x 100;
cmpthese(-2, {
REDUCE => sub {
my $l = reduce{ length($a) gt length($b) ? $a : $b } @array;
},
TMPVAR => sub {
my $idx = 1;
my $lastLength = length $array[0];
my $lastElt = $array[0];
my $listLength = scalar @array;
while ($idx < $listLength) {
my $tmpLength = length $array[$idx];
if ($tmpLength > $lastLength) {
$lastElt = $array[$idx];
$lastLength = $tmpLength
}
$idx++
}
my $l = $lastElt;
},
TMPFOR => sub {
my $len = length $array[0];
my $longest = 0;
for my $i (1 .. $#array) {
my $i_len = length $array[$i];
if($i_len > $len) {
$longest = $i;
$len = $i_len;
}
}
my $l = $array[$longest];
},
});
Ответ 3
Самый быстрый из них:
sub drewk {
my $len = -1;
for (@_) {
my $tmp=length($_);
if ( $tmp > $len ) {
$longest = $_;
$len = $tmp;
}
}
return $longest;
}
Но сравнительный анализ против:
sub strom {
my $max = -1;
my $max_i = 0;
for (0 .. $#_) { # for each index
my $len = length $_[$_]; # only get length once per item
if ($len > $max) { # save index and update max if larger
$max = $len;
$max_i = $_;
}
}
$_[$max_i] # return the largest item
}
sub red {
return reduce{ length($a) > length($b) ? $a : $b } @_;
}
Показывает, что reduce является самым быстрым:
Rate strom drewk reduce
strom 1323455/s -- -38% -45%
drewk 2144549/s 62% -- -10%
reduce 2390707/s 81% 11% --
Другим эталоном является Eric Strom sub
Ответ 4
Немного гольфиста:
my @unsorted = qw( one two three four five six seven eight nine ten eleven );
my $longest = (
map { $_->[0] }
sort { $b->[1] <=> $a->[1] }
map { [ $_, length $_ ] } @unsorted
)[0];
say $longest;
EDIT: map/sort/map является преобразованием Шварца для тех, кто не знаком с этой техникой и задается вопросом.
Ответ 5
Предполагая, что цель состоит в том, чтобы просто найти самую длинную строку, а не ее индекс:
my $longest = $array[0];
my $len = length $longest;
for my $str (@array) {
if ( length($str) > $len ) {
$longest = $str;
$len = length($str);
}
}
Ответ 6
Если вы действительно хотите сократить количество вычисленных length, а затем посмотрите преобразование Шварца и перенесите его на ваша проблема.
EDIT:
Я вижу, что никто не опубликовал полный пример, который я имел в виду, так что вот он (я еще не проверил его, пока меня нет на моем персональном компьютере):
my @array = qw( one two three four five six seven eight nine ten eleven );
my $longest = (
reduce { $a->[1] > $b->[1] ? $a : $b }
map { [ $_, length $_ ] }
@array
)[0];
say $longest;
Ответ 7
Это выглядит значительно быстрее, чем другие решения (на основе fastest_Eric_Storm),
use warnings;
use 5.012;
use Benchmark qw(:all) ;
use List::Util qw(reduce);
my @array = map { ($_) x 50 } qw( one two three four five six seven eight nine ten eleven );
sub list_util_xs {
my $l = reduce{ length($a) > length($b) ? $a : $b } @array;
return $l;
}
sub fastest_Eric_Strom {
my $max = -1; my $max_ref;
for (@array) {
if (length > $max) {
$max = length;
$max_ref = \$_;
}
}
return $$max_ref;
}
sub ysth {
my $longest = $array[0];
my $len = length $longest;
for my $str (@array) {
if ( length($str) > $len ) {
$longest = $str;
$len = length($str);
}
}
return $longest;
}
sub mpapec {
my $max = -1;
my $max_ref;
length > $max and ($max, $max_ref) = (length, \$_) for @array;
return $$max_ref;
}
cmpthese( -10, {
'list_util_xs' => sub{ list_util_xs() },
'fastest_Eric_Storm' => sub{ fastest_Eric_Strom() },
'ysth' => sub{ ysth() },
'mpapec' => sub{ mpapec() },
});
Выход
Rate list_util_xs fastest_Eric_Storm ysth mpapec
list_util_xs 13479/s -- -24% -24% -29%
fastest_Eric_Storm 17662/s 31% -- -0% -6%
ysth 17680/s 31% 0% -- -6%
mpapec 18885/s 40% 7% 7% --
Ответ 8
Вы можете использовать некоторую временную переменную var, чтобы избежать повторной вычисления длины:
my @unsorted = qw( one two three four five six seven eight nine ten eleven );
my $idx = 1;
my $lastLength = length $unsorted[0];
my $lastElt = $unsorted[0];
my $listLength = scalar @unsorted;
while ($idx < $listLength) {
my $tmpLength = length $unsorted[$idx];
if ($tmpLength > $lastLength) {
$lastElt = $unsorted[$idx];
$lastLength = $tmpLength
}
$idx++
}
print "Longest element:$lastElt";
Результаты тестов:
Rate REDUCE TMPVAR
REDUCE 169297/s -- -29%
TMPVAR 237926/s 41% --
Ответ 9
Сначала я тестировал, если все подпрограммы дают мне правильный результат. Программа MBO не прошла первый тест (он возвращает ссылку на массив); чтобы дать ему второе изменение, я изменил процедуру, чтобы получить правильный результат.
Я запускаю бенчмарк несколько раз, и я не всегда получал тот же порядок.
Поэтому я бы сказал (как уже здесь здесь) ysth и fasest_Eric_Strom являются самыми быстрыми, но list_utils уменьшается почти так же быстро, как и они;
что легко читать из результатов, так это то, что версия David Precious-sort является самой медленной, а модифицированная сокращенная версия MBO является второй самой медленной.
Мой вывод: list_utils reduce является победителем лучшего соотношения цены и качества.
редактировать:
Я был слишком быстр с церемонией награждения:
Список:: Util - сокращение - длина - кодировка - вопрос
David_Precious 64147/s -- -36% -73% -79% -80% -81% -85% -86% -87%
MBO 100195/s 56% -- -58% -67% -69% -70% -77% -79% -80%
OMG_peanuts 237772/s 271% 137% -- -21% -27% -30% -45% -50% -52%
longest_Eric_Strom 300466/s 368% 200% 26% -- -8% -11% -31% -36% -40%
drewk 325883/s 408% 225% 37% 8% -- -4% -25% -31% -34%
bvr 338156/s 427% 237% 42% 13% 4% -- -22% -28% -32%
list_util_xs 434114/s 577% 333% 83% 44% 33% 28% -- -8% -13%
fastest_Eric_Strom 471812/s 636% 371% 98% 57% 45% 40% 9% -- -5%
ysth 497198/s 675% 396% 109% 65% 53% 47% 15% 5% --
.
#!/usr/bin/env perl
use warnings;
use 5.012;
use Benchmark qw(:all) ;
use List::Util qw(reduce);
my @array = qw( one two three four five six seven eight nine very_long_long ten eleven );
sub list_util_xs {
my $l = reduce{ length($a) > length($b) ? $a : $b } @array;
return $l;
}
sub longest_Eric_Strom {
my $max = -1; my $max_i = 0;
for (0 .. $#array) {
my $len = length $array[$_];
if ($len > $max) {
$max = $len;
$max_i = $_;
}
}
return $array[$max_i];
}
sub fastest_Eric_Strom {
my $max = -1; my $max_ref;
for (@array) {
if (length > $max) {
$max = length;
$max_ref = \$_;
}
}
return $$max_ref;
}
sub David_Precious {
my $longest = ( map { $_->[0] } sort { $b->[1] <=> $a->[1] } map { [ $_, length $_ ] } @array )[0];
return $longest;
}
sub MBO {
my $longest = ( reduce { $a->[1] > $b->[1] ? $a : $b } map { [ $_, length $_ ] } @array )[0];
return $longest->[0];
}
sub drewk {
my $len = -1; my $longest;
for (@array) {
my $tmp=length($_);
if ( $tmp > $len ) {
$longest = $_;
$len = $tmp;
}
}
return $longest;
}
sub ysth {
my $longest = $array[0];
my $len = length $longest;
for my $str (@array) {
if ( length($str) > $len ) {
$longest = $str;
$len = length($str);
}
}
return $longest;
}
sub bvr {
my $len = length $array[0];
my $longest = 0;
for my $i (1 .. $#array) {
my $i_len = length $array[$i];
if($i_len > $len) {
$longest = $i;
$len = $i_len;
}
}
return $array[$longest];
}
sub OMG_peanuts {
my $idx = 1;
my $lastLength = length $array[0];
my $lastElt = $array[0];
my $listLength = scalar @array;
while ($idx < $listLength) {
my $tmpLength = length $array[$idx];
if ($tmpLength > $lastLength) {
$lastElt = $array[$idx];
$lastLength = $tmpLength
}
$idx++
}
return $lastElt;
}
cmpthese( -10, {
'list_util_xs' => sub{ list_util_xs() },
'longest_Eric_Storm' => sub{ longest_Eric_Strom() },
'fastest_Eric_Storm' => sub{ fastest_Eric_Strom() },
'David_Precious' => sub{ David_Precious() },
'MBO' => sub{ MBO() },
'drewk' => sub{ drewk() },
'ysth' => sub{ ysth() },
'OMG_peanuts' => sub{ OMG_peanuts() },
'bvr' => sub{ bvr() },
});
Ответ 10
Вы могли бы сократить количество раз, когда вам нужно рассчитать длину строки, сократив до структуры или массива, содержащей длину рядом с самой строкой.
Кроме того, итерация оптимизирована алгоритмом reduce, вызов length вряд ли оптимизирован.
