Самый быстрый способ (время выполнения), чтобы найти самый длинный элемент в списке

Question

Является ли это самым быстрым (временем выполнения) способом поиска самого длинного элемента в списке?

#!/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; 

Answer 1

Когда вы пытаетесь найти только один элемент списка, нет необходимости создавать структуру данных размера 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 показал, что индекс массива в приведенном выше коде немного узким местом. Экспериментируя немного больше, я, наконец, нашел метод, который быстрее, чем 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%  -- 

Answer 2

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

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%  -- 

Answer 3

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

Далее, итерация оптимизирована по алгоритму reduce, вызов length вряд ли оптимизирован.

Answer 4

Вот слегка модифицированной версией 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%  -- 

Обратите внимание, что пригодность алгоритма сильно варьируется в зависимости от специфики данных (я бы предположил, что более длинные строки могут увеличить вес функции в алгоритме).

EDIT: Вот полный код теста (версия длинного массива, короткий отсутствует 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]; 
    }, 
}); 

Answer 5

Если вы действительно хотите, чтобы отсечка количества вычисленных length-х, затем взгляните на Schwartian transform и примите его к вашей проблеме.

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; 

Answer 6

немного golfish:

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: отображение/сортировка/карта является Schwartzian transform для тех, кто не знаком с этой техникой и интересно.

Answer 7

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

my $longest = $array[0]; 
my $len = length $longest; 
for my $str (@array) { 
    if (length($str) > $len) { 
     $longest = $str; 
     $len = length($str); 
    } 
} 

Answer 8

Мой быстрый является:

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's sub

Answer 9

Сначала я проверил, если все процедуры дают мне правильный результат. Процедура MBO не прошла первый тест (он возвращает ссылку на массив); чтобы дать ему второе изменение, я изменил процедуру, чтобы получить правильный результат.

Я запускаю бенчмарк несколько раз, и я не всегда получал тот же порядок. Итак, я бы сказал (как уже здесь здесь) ysth's и fasest_Eric_Strom являются самыми быстрыми, но list_utils уменьшается почти так же быстро, как и они; Что легко прочитать из результатов, так это то, что версия David Precious-sort является самой медленной, а модифицированная сокращенная версия MBO занимает второе место.

Мой вывод: list_utils reduce является победителем лучшего соотношения цены и качества.
редактировать: я был слишком быстр с церемонии награждения: List::Util - reduce - length - encoding - question

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() }, 
}); 

Answer 10

Это, как представляется, значительно быстрее, чем другие решения (на основе 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%   --