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

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

当仅尝试查找列表的一个元素时，无需构建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 fastestlongest 44245/s      --    -21%    -30%    -47%drewk   55854/s     26%      --    -11%    -33%reduce  63014/s     42%     13%      --    -25%fastest 83638/s     89%     50%     33%      --