栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

当仅尝试查找列表的一个元素时,无需构建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%      --


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/633578.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号