Perl Language
並べ替え
サーチ…
前書き
物のリストをソートするために、Perlには驚くことにsort
と呼ばれる関数が1つしかありません。数字、任意の数のエンコーディングの文字列、ネストされたデータ構造またはオブジェクトなど、あらゆる種類の項目をソートするのに十分な柔軟性があります。しかし、その柔軟性のために、その使用のために学ぶべきかなりのトリックとイディオムがあります。
構文
- 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;