名前¶
sort - perl pragma to control sort() behaviour
sort - sort() の振る舞いを制御するための perl プラグマ
概要¶
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
}説明¶
With the sort pragma you can control the behaviour of the builtin sort() function.
sort プラグマを使って、組み込みの sort() 関数の振る舞いを 制御できます。
In Perl versions 5.6 and earlier the quicksort algorithm was used to implement sort(), 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.
Perl バージョン 5.6 以前では、sort() の実装にクイックソートアルゴリズムが 使われますが、Perl 5.8 では、マージソートアルゴリズムも利用可能となりました; 主に最悪のケースの O(N log N) の振る舞いを保証するためです: クイックソートの最悪のケースは O(N**2) です。 Perl 5.8 以降では、大きな配列をソートする前にシャッフルすることで、 二次の振る舞いに対して防御しています。
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
安定ソート(stable sort)は、同じ値を比較する場合に、元の入力の順番を 保存します。 マージソートは安定していますが、クィックソートは違います。 安定性は比較して同じになるものが他の方法で区別できる場合にのみ意味が あります。 これは、単純な数値とレキシカルなソートは安定性からのメリットは ないということです; 同じ要素は区別できないからです。 しかし、以下のような比較は
{ substr($a, 0, 3) cmp substr($b, 0, 3) }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.
安定性は影響します; 最初の 3 文字での比較が同じでも引き続く文字列を元に 区別できるからです。 Perl 5.8 以降では、クィックソートも安定化されていますが、そうするには オーバーヘッドが加わるので、その意味がある場合にのみ行われます。
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 sort() 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 _ 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
最良のアルゴリズムは多くのことに依存します。 平均的には、マージソースはクイックソートより比較回数が少ないので、 複雑な比較ルーチンが使われるときにはよりよいです。 マージソートは既に存在する順序についても優れているので、複数のソートされた 配列に対して sort() を使うときにも好まれます。 一方、小さい配列や、値の種類が少なく、同じ値が何度も現れる配列では しばしばクイックソートの方が速いです。 このプログラムでアルゴリズム選択を矯正できますが、これは荒っぽく 感じられるので、_ で始まる副プラグマは Perl 5.8 以降では主張しません。 デフォルトのアルゴリズムはマージソートなので、明示的に求めていなくても 安定しています。 しかし、デフォルトソートの安定性は後のバージョンでは変わる可能性のある 副作用です。 安定性が重要なら、以下のように指定します
use sort 'stable';The no sort pragma doesn't forbid what follows, it just leaves the choice open. Thus, after
no sort プラグマはその後のものを 禁止 せず、選択を解放したままです。 従って、以下のようにした後、
no sort qw(_mergesort stable);a mergesort, which happens to be stable, will be employed anyway. Note that
たまたま安定しているマージソートが適用されます。 注意点として
no sort "_quicksort";
no sort "_mergesort";have exactly the same effect, leaving the choice of sort algorithm open.
というのも全く同じ効果を持ち、ソートアルゴリズムの選択を解放したままです。
CAVEATS¶
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 eval() to change the behaviour:
Perl 5.10 から、このプラグマはレキシカルスコープを持ち、コンパイル時に 効果を持ちます。 以前のバージョンではこの効果はグローバルで、実行時に効果を持ちます; 文書ではこの振る舞いを変えるのに eval() を使うことを推奨しています:
{ 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
}Such code no longer has the desired effect, for two reasons. Firstly, the use of eval() means that the sorting algorithm is not changed until runtime, by which time it's too late to have any effect. Secondly, sort::current is also called at run-time, when in fact the compile-time value of sort::current is the one that matters.
このようなコードは、二つの理由によってもはや望んでいる効果を持ちません。 最初に、eval() の使用はソートアルゴリズムが実行時まで変更されないと いうことなので、今では効果を持つには遅すぎます。 次に、sort::current も実行時に呼び出されるので、実際にはコンパイル時の sort::current の値が使われることになります。
So now this code would be written:
従って、以下のようなコードになります:
{ 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;
}