=encoding euc-jp =head1 NAME =begin original sort - perl pragma to control sort() behaviour =end original sort - sort() の振る舞いを制御するための perl プラグマ =head1 SYNOPSIS use sort 'stable'; # guarantee stability use sort '_quicksort'; # use a quicksort algorithm use sort '_mergesort'; # use a mergesort algorithm use sort 'defaults'; # revert to default behavior no sort 'stable'; # stability not important use sort '_qsort'; # alias for quicksort my $current; BEGIN { $current = sort::current(); # identify prevailing algorithm } =head1 DESCRIPTION =begin original With the C pragma you can control the behaviour of the builtin C function. =end original C プラグマを使って、組み込みの C 関数の振る舞いを 制御できます。 =begin original In Perl versions 5.6 and earlier the quicksort algorithm was used to implement C, but in Perl 5.8 a mergesort algorithm was also made available, mainly to guarantee worst case O(N log N) behaviour: the worst case of quicksort is O(N**2). In Perl 5.8 and later, quicksort defends against quadratic behaviour by shuffling large arrays before sorting. =end original Perl バージョン 5.6 以前では、C の実装にクイックソートアルゴリズムが 使われますが、Perl 5.8 では、マージソートアルゴリズムも利用可能となりました; 主に最悪のケースの O(N log N) の振る舞いを保証するためです: クイックソートの最悪のケースは O(N**2) です。 Perl 5.8 以降では、大きな配列をソートする前にシャッフルすることで、 二次の振る舞いに対して防御しています。 =begin original A stable sort means that for records that compare equal, the original input ordering is preserved. Mergesort is stable, quicksort is not. Stability will matter only if elements that compare equal can be distinguished in some other way. That means that simple numerical and lexical sorts do not profit from stability, since equal elements are indistinguishable. However, with a comparison such as =end original 安定ソート(stable sort)は、同じ値を比較する場合に、元の入力の順番を 保存します。 マージソートは安定していますが、クィックソートは違います。 安定性は比較して同じになるものが他の方法で区別できる場合にのみ意味が あります。 これは、単純な数値とレキシカルなソートは安定性からのメリットは ないということです; 同じ要素は区別できないからです。 しかし、以下のような比較は { substr($a, 0, 3) cmp substr($b, 0, 3) } =begin original stability might matter because elements that compare equal on the first 3 characters may be distinguished based on subsequent characters. In Perl 5.8 and later, quicksort can be stabilized, but doing so will add overhead, so it should only be done if it matters. =end original 安定性は影響します; 最初の 3 文字での比較が同じでも引き続く文字列を元に 区別できるからです。 Perl 5.8 以降では、クィックソートも安定化されていますが、そうするには オーバーヘッドが加わるので、その意味がある場合にのみ行われます。 =begin original The best algorithm depends on many things. On average, mergesort does fewer comparisons than quicksort, so it may be better when complicated comparison routines are used. Mergesort also takes advantage of pre-existing order, so it would be favored for using C to merge several sorted arrays. On the other hand, quicksort is often faster for small arrays, and on arrays of a few distinct values, repeated many times. You can force the choice of algorithm with this pragma, but this feels heavy-handed, so the subpragmas beginning with a C<_> may not persist beyond Perl 5.8. The default algorithm is mergesort, which will be stable even if you do not explicitly demand it. But the stability of the default sort is a side-effect that could change in later versions. If stability is important, be sure to say so with a =end original 最良のアルゴリズムは多くのことに依存します。 平均的には、マージソースはクイックソートより比較回数が少ないので、 複雑な比較ルーチンが使われるときにはよりよいです。 マージソートは既に存在する順序についても優れているので、複数のソートされた 配列に対して C を使うときにも好まれます。 一方、小さい配列や、値の種類が少なく、同じ値が何度も現れる配列では しばしばクイックソートの方が速いです。 このプログラムでアルゴリズム選択を矯正できますが、これは荒っぽく 感じられるので、C<_> で始まる副プラグマは Perl 5.8 以降では主張しません。 デフォルトのアルゴリズムはマージソートなので、明示的に求めていなくても 安定しています。 しかし、デフォルトソートの安定性は後のバージョンでは変わる可能性のある 副作用です。 安定性が重要なら、以下のように指定します use sort 'stable'; =begin original The C pragma doesn't I what follows, it just leaves the choice open. Thus, after =end original C プラグマはその後のものを I<禁止> せず、選択を解放したままです。 従って、以下のようにした後、 no sort qw(_mergesort stable); =begin original a mergesort, which happens to be stable, will be employed anyway. Note that =end original たまたま安定しているマージソートが適用されます。 注意点として no sort "_quicksort"; no sort "_mergesort"; =begin original have exactly the same effect, leaving the choice of sort algorithm open. =end original というのも全く同じ効果を持ち、ソートアルゴリズムの選択を解放したままです。 =head1 CAVEATS =begin original As of Perl 5.10, this pragma is lexically scoped and takes effect at compile time. In earlier versions its effect was global and took effect at run-time; the documentation suggested using C to change the behaviour: =end original Perl 5.10 から、このプラグマはレキシカルスコープを持ち、コンパイル時に 効果を持ちます。 以前のバージョンではこの効果はグローバルで、実行時に効果を持ちます; 文書ではこの振る舞いを変えるのに C を使うことを推奨しています: { eval 'use sort qw(defaults _quicksort)'; # force quicksort eval 'no sort "stable"'; # stability not wanted print sort::current . "\n"; @a = sort @b; eval 'use sort "defaults"'; # clean up, for others } { eval 'use sort qw(defaults stable)'; # force stability print sort::current . "\n"; @c = sort @d; eval 'use sort "defaults"'; # clean up, for others } =begin original Such code no longer has the desired effect, for two reasons. Firstly, the use of C means that the sorting algorithm is not changed until runtime, by which time it's too late to have any effect. Secondly, C is also called at run-time, when in fact the compile-time value of C is the one that matters. =end original このようなコードは、二つの理由によってもはや望んでいる効果を持ちません。 最初に、C の使用はソートアルゴリズムが実行時まで変更されないと いうことなので、今では効果を持つには遅すぎます。 次に、C も実行時に呼び出されるので、実際にはコンパイル時の C の値が使われることになります。 =begin original So now this code would be written: =end original 従って、以下のようなコードになります: { use sort qw(defaults _quicksort); # force quicksort no sort "stable"; # stability not wanted my $current; BEGIN { $current = print sort::current; } print "$current\n"; @a = sort @b; # Pragmas go out of scope at the end of the block } { use sort qw(defaults stable); # force stability my $current; BEGIN { $current = print sort::current; } print "$current\n"; @c = sort @d; } =begin meta Translate: SHIRAKATA Kentaro Status: completed =end meta =cut