在列表中找到最长元素的最快方法（执行时间）

一尘不染

在列表中找到最长元素的最快方法（执行时间）

algorithm

这是在列表中找到最长元素的最快方法（执行时间）吗？

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

阅读 726

2020-07-28

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

2020-07-28