4

最近、渡されたすべての引数の中で最小の数値を返す次のコードを perl で見つけました。

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

私は通常、単純な線形検索を使用して、リスト内の最小/最大を見つけます。これは、私にとって単純で適切に最適であるように思われます。上記のコードは、単純な線形検索よりも優れていますか? この場合、perl と何か関係がありますか? ありがとう！

4

3 に答える 3

4

O() は、アルゴリズムにかかる時間については何も言いません。たとえば、他の条件がすべて同じであれば、次の 2 つのアルゴリズムの中から常にアルゴリズム 2 を選択します。

  • アルゴリズム 1: O(2*N + 1000 日) = O(N)
  • アルゴリズム 2: O(5*N + 100 ms) = O(N log N)

O()は、入力のサイズが大きくなるにつれてアルゴリズムにかかる時間がどのように変化するかを指定します。(まあ、時間だけでなく、あらゆるリソースに使用できます。) 前の 2 つの回答は O() の観点からしか話していないため、役に立ちません。

特定のサイズの入力に対してどのアルゴリズムが優れているかを知りたい場合は、それらをベンチマークする必要があります。

この場合、 List::Utilの方minが常に大幅に優れているように見えます。

$ 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））があります。 これは、多くのプログラマーが想像するほど遅くはありません。関心のある実際のケースでは、ソートの平衡二分木（または他のそのような構造）を管理するオーバーヘッドは、おそらくlog（n）係数 と同じくらい重要です。だから、ソートの見通しから恐怖で縮小する必要はありません！ただし、線形検索はさらに高速です。これについては非常に正しいです。

さらに、@ DavidOは非常に洞察に満ちたコメントを追加しているので、ここで彼自身の言葉で引用します。

線形検索は、一般化するのが簡単なアルゴリズムでもあります。線形検索は、たとえば、大規模なデータセットの場合、ディスクベースで簡単に（そして比較的効率的に）実行できます。一方、ディスクベースの並べ替えを行うと比較的コストがかかり、フィールドサイズが正規化されていない場合はさらに複雑になります。

于 2012-06-07T18:32:11.037 に答える
0

明らかな理由から、線形探索はO（n ）です。ソートはO（n log n ）です（ Perlのドキュメントのソートを参照）。そうです、線形検索は複雑さの点で確かに高速です。これは、Perlだけでなく、これらのアルゴリズムを実装するすべてのプログラミング言語にも当てはまります。

多くの問題と同様に、それを解決する方法は複数あり、リストの最小/最大を取得する方法も複数あります。概念的には、問題は並べ替えを必要としないため、リストの最小値または最大値のみが必要な場合は、線形検索の方が適していると言えます。

于 2012-06-07T18:33:17.440 に答える