4

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

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

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

4

3 回答 3

4

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

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

O() 指定算法所花费的时间如何随着输入大小的增加而缩放。（嗯，它可以用于任何资源，而不仅仅是时间。）由于前面的两个答案只讨论 O()，所以它们是无用的。

如果您想知道对于给定大小的输入哪种算法更好的算法，您需要对它们进行基准测试。

在这种情况下，看起来List::Utilmin总是明显更好。

$ 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);
于 2012-06-07T19:49:09.100 回答
2

你说的对。如果您不需要为任何其他目的排序数据，则简单的线性搜索是最快的。无论如何，为了完成它的工作，排序必须至少查看每个数据一次。

只有当排序后的数据对其他目的有用时——或者当我不关心运行时间、功耗、散热等时——我才会对数据进行排序以找到最小值和最大值。

现在，@SimeonVisser 是正确的。排序确实有O(n*log(n))。 这并不像许多程序员想象的那样比O(n)慢得多。 在感兴趣的实际案例中，管理排序的平衡二叉树（或其他此类结构）的开销可能与log(n)因子一样重要。所以，不必害怕分类的前景！但是，线性搜索仍然更快：您对此非常正确。

此外，@DavidO 添加了如此有见地的评论，我会用他自己的话在这里引用它：

线性搜索也是一种更容易泛化的算法。例如，对于大型数据集，线性搜索可以轻松（并且相对有效地）基于磁盘。而基于磁盘的排序变得相对昂贵，如果字段大小未标准化，则更加复杂。

于 2012-06-07T18:32:11.037 回答
0

出于显而易见的原因，线性搜索是 O( n )。排序是 O( n log n )（参见Perl 文档中的排序）。所以是的，就复杂性而言，线性搜索确实更快。这不仅适用于 Perl，也适用于任何实现这些算法的编程语言。

与许多问题一样，有多种方法可以解决它，也有多种方法可以获得列表的最小值/最大值。从概念上讲，当您只需要列表的最小值或最大值时，我会说线性搜索会更好，因为问题不需要排序。

于 2012-06-07T18:33:17.440 回答