最快的方法（执行时间）找到一个名单最长元素 [英] The fastest way (execution time) to find the longest element in an list

问题描述

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

 ＃！的/ usr / bin中/ perl的包膜
使用警告;
用5.012;
使用List ::的Util QW（减少）;
使用List ::的Util :: XS;

我@array = QW（一二三四五六七八九十十一）;

我的$ L = {缩短长度（$ A）＆GT;长度（$ B）？ $ A：$ B} @array;

说$ L;
 

解决方案

当只是想找到一个列表中的一个元素，就没有必要构建一个N大小的数据结构尽可能多的答案在这里所做的一切。最快 O（N）办法做到这一点是走阵，跟踪最大的元素。这样，你有 O（N）列表和 O（1）内存使用的访问。

 子最长{
    我的$最大= -​​1;
    我的$ max_i = 0;
    为（0 .. $＃_）{＃每个索引
        我的$ LEN =长度$ _ [$ _] ＃只得到一次长每件
        如果（$ LEN＆GT; $最大值）{＃保存索引并更新最大值，如果大
            $最大值= $ LEN;
            $ max_i = $ _;
        }
    }
    $ _ [$ max_i]＃返回的最大项
}
 

如果你要运行上述code很多次，我建议内联子程序的身体。

编辑：

drewk的基准测试显示，在上述code数组的索引是一个有点瓶颈。尝试多一点，我终于找到了一种方法，比减少解决方案快：

 子最快{
    我的$最大= -​​1;
    我的$ max_ref;
    对于 （@_） {
        如果（长度＆GT; $最大值）{＃没有临时变量，长度（）两次更快
            $最大值=长度;
            $ max_ref = \ $ _; ＃避免任何复制
        }
    }
    $$ max_ref
}
 

这将导致以下基准：

 评级最长drewk减少最快
最长的44245 /秒 -  -21％-30％-47％
drewk 55854 / s的26％ -  -11％-33％
减少63014 / s的42％，13％， -  25％
最快的83638 / s的89％，50％，33％ - 
 

Is this the fastest (execution time) way to find the longest element in a list?

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

解决方案

When only trying to find one element of a list, there is no need to construct an N sized data structure as many answers here have done. The fastest O(N) way to do this is to walk the array, keeping track of the largest element. That way you have O(N) accesses of the list, and O(1) memory usage.

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
}

If you are going to be running the above code many times, I would suggest inlining the body of the subroutine.

EDIT:

drewk's benchmark revealed that the array index in the above code is a bit of a bottleneck. Experimenting a little more, I have finally found a method that is faster than the reduce solution:

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
}

which results in the following benchmark:

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

这篇关于最快的方法（执行时间）找到一个名单最长元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！