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

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