Perl Language
並べ替え

前書き

構文

• SUBNAME LISTを並べ替える
• ソートブロックリスト
• ソートリスト

基本レキシカルソート

@sorted = sort @list;

@sorted = sort { $a cmp $b } @list;

sub compare { $a cmp $b }
@sorted = sort compare @list;

上記の3つの例はまったく同じことをしています。コンパレータ関数やブロックを指定しないと、 sortはそのリストを字句的にsortしたいと仮定します。これは通常、データを予測可能な順序で必要とし、言語上の正確さに気にしない場合に必要な形式です。

sortは、 @list内の項目のペアをコンパレータ関数に@listます。コンパレータ関数は、どの項目が大きいかをsortします。 cmp演算子は文字列に対してこれを行い、 <=>は数値に対して同じことを行います。コンパレータはかなり頻繁に呼び出され、平均n * log（ n ）回、 nはソートされる要素の数であるので、高速であることが重要です。これは、適切な関数パラメータではなく、ブロックまたは関数と比較する要素を渡すために、 sortが事前定義されたパッケージグローバル変数（ $aおよび$b ）を使用する理由です。

あなたがいる場合use locale 、 cmp例えば、考慮にロケール固有の照合順序を取ることがソートされますÅのようなAデンマーク語ロケールではなく後にZ 、英語またはドイツ語1アンダー。ただし、複雑なUnicodeソートルールは考慮されていません。また、オーダーを制御することもありません。たとえば、電話帳は辞書とは異なる方法でソートされることがよくあります。そのような場合は、 Unicode::Collate 、特にUnicode::Collate::Localeモジュールが推奨されます。

数値ソート

@sorted = sort { $a <=> $b } @list;

$aと$bを<=>演算子と比較すると、それらが数値で比較され、デフォルトではテキストではなく比較されます。

逆ソート

@sorted = sort { $b <=> $a } @list;
@sorted = reverse sort { $a <=> $b } @list;

降順でソート項目は単に交換することによって達成することができる$aと$b比較器ブロックに。しかし、若干遅いにもかかわらず、別のreverse明快さを好む人もいます。

Schwartzian変換

これはおそらく、アイテムのソート順が高価な関数に依存するPerlの関数型プログラミング機能を利用したソート最適化の最も有名な例です。

# What you would usually do
@sorted = sort { slow($a) <=> slow($b) } @list;

# What you do to make it faster
@sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, slow($_) ] }
@list;

最初の例の問題は、コンパレータが非常に頻繁に呼び出され、遅い関数を繰り返し使用して値を再計算することです。典型的な例は、ファイル名をファイルサイズでソートすることです。

use File::stat;
@sorted = sort { stat($a)->size <=> stat($b)->size } glob "*";

これは動作しますが、せいぜい比較ごとに2つのシステムコールのオーバーヘッドが発生します。最悪の場合、1回の比較で2回ディスクに移動しなければならず、そのディスクは惑星。

Randall Schwartzのトリックを入力してください。

Schwartzian Transformは基本的に@listを3つの関数、bottom-to-topを@listて@listます。最初のmapは、各項目を元の項目の2要素リストと低速関数の結果をソートキーとして返します。最後に、各要素に対してslow() 1回だけ呼び出しました。次のsortは、リストを見てソートキーにアクセスするだけです。ソートキーは気にしませんが、ソートされた順序で元の要素のみが必要なので、最後のmapは@sortから受け取ったソートされたリストから2つの要素のリストをスローし、最初のメンバーのリストを返します。

大文字と小文字の区別なし

sort無視する従来の手法では、文字列をlcまたはucに渡して比較します。

@sorted = sort { lc($a) cmp lc($b) } @list;

これはPerl 5のすべてのバージョンで動作し、英語では十分です。 ucまたはlcどちらを使用するかは関係ありません。ただし、ギリシャ語やトルコ語のように、大文字と小文字の間に1対1の対応がないため、 ucまたはlcどちらを使用するかによって結果が異なるため、問題が発生します。したがって、Perl 5.16以降では、この問題を回避するfcという大文字小文字の区別関数があるため、現代の多言語ソートではこれを使用する必要があります。

@sorted = sort { fc($a) cmp fc($b) } @list;