查找列表中最长元素的最快方法(执行时间)

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(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
}

如果你要多次运行上面的代码,我会建议内联子程序的主体.

编辑:

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

以下是带有for和更少变量的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算法中函数的权重).

编辑:这是基准测试的完整代码(长数组版本,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];
    },
});