perl – 排序与线性搜索查找最小值/最大值

发布时间：2020-12-16 06:22:50 所属栏目：大数据来源：网络整理

导读：最近,我在perl中遇到了以下代码,它返回所有传递的参数中的最小数值. return 0 + ( sort { $a = $b } grep { $_ == $_ } @_ )[0]; 我通常使用简单的线性搜索来查找列表中的最小值/最大值,这对我来说似乎很简单且充分优化.以上代码是否比简单的线性搜索更好？

最近,我在perl中遇到了以下代码,它返回所有传递的参数中的最小数值.

return 0 + ( sort { $a <=> $b } grep { $_ == $_ } @_ )[0];

我通常使用简单的线性搜索来查找列表中的最小值/最大值,这对我来说似乎很简单且充分优化.以上代码是否比简单的线性搜索更好？在这种情况下与perl有什么关系？谢谢！

解决方法

O()没有说算法需要多长时间.例如,在其他条件相同的情况下,我总是在以下两个中选择算法2：

>算法1：O(2 * N 1000天)= O(N)
>算法2：O(5 * N 100 ms)= O(N log N)

O()指定当输入的大小增加时算法采用比例的时间. (好吧,它可以用于任何资源,而不仅仅是时间.)由于前面两个答案只是用O()来谈,所以它们没用.

如果你想知道哪种算法对于给定大小的输入更好的算法有多快,你需要对它们进行基准测试.

在这种情况下,看起来List::Util的分钟总是明显更好.

$perl x.pl 10
           Rate  sort LUmin
sort  1438165/s    --  -72%
LUmin 5210584/s  262%    --

$perl x.pl 100
           Rate  sort LUmin
sort   129073/s    --  -91%
LUmin 1485473/s 1051%    --

$perl x.pl 1000
          Rate  sort LUmin
sort    6382/s    --  -97%
LUmin 199698/s 3029%    --

码：

use strict;
use warnings;

use Benchmark  qw( cmpthese );
use List::Util qw( min );

my %tests = (
   'sort'  => 'my $x = ( sort { $a <=> $b } @n )[0];','LUmin' => 'my $x = min @n;',);

$_ = 'use strict; use warnings; our @n; ' . $_
   for values %tests;

local our @n = map rand,1..( $ARGV[0] // 10 );
cmpthese(-3,%tests);

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!