6.21 比較とソート

Function: compare obj1 obj2

一般的な比較手続きです。obj1がobj2より小さければ-1を、 等しければ0を、大きければ1を返します。obj1とobj2が 比較できない場合はエラーとなります。

いくつかの組み込み型は「自然な」比較順を用いて比較されます。 他の組み込み型は通常比較不可能です。Schemeで定義されたクラスについては、 この手続きはジェネリックファンクションobject-compareを 呼び出します。

Generic Function: object-compare obj1 obj2

このジェネリックファンクションを特殊化することで compare手続きをユーザ定義クラスに対して動作するように拡張できます。

Function: sort seq &optional cmpfn

Function: sort! seq &optional cmpfn

シーケンスseq(リストかベクタ)の要素を昇順にソートし、 ソートされたシーケンスを返します。 sort!は、オリジナルのシーケンスを破壊的に再利用します。 ソート順はcmpfnで指定されます。cmpfnはseqのふたつの要素を 引数に取り、最初の要素が厳密に2番目の要素より先行するものの場合は #tを返す手続きです。

sort!の後でseqが必ずしもソート済みのシーケンスを 指すとは限らないことに注意してください。 seqがリストの場合、オリジナルのリストの最初のペアが ソート済みリストでも最初に来るとは限りません。 常にsort!の戻り値を使うようにしてください。

(sort '(("Chopin" "Frederic") ("Liszt" "Franz") ("Alkan" "Charles-Valentin")) (lambda (x y) (string<? (car x) (car y)))) ⇒ (("Alkan" "Charles-Valentin") ("Chopin" "Frederic") ("Liszt" "Franz"))

cmpfnが省略された場合はcompare手続きが どちらの要素がより「小さい」かを判定するのに使われます。

現在の実装では、cmpfnが省略された場合は クィックソートとヒープソートを使い、 cmpfnが与えられた場合はマージソートを使っています。 これは将来変更されるかもしれません。

なお、オブジェクトをひとつづつ集合に追加しつつ、常にソートされた 状態に保ちたい場合は、treemapの使用を考えても良いでしょう (ツリーマップ参照)。

Function: stable-sort seq &optional cmpfn

Function: stable-sort! seq &optional cmpfn

安定ソートアルゴリズム(現時点ではマージソート)を使って、並び seq (リストまたはベクタ)をソートします。ソート順は cmpfn で指定します。 cmpfn は list のふたつの要素を引数として取る関数で、 厳密に、最初の引数が第二の引数の前にくるものである場合に #t を返します。

Function: sort-by seq key &optional cmpfn

Function: sort-by! seq key &optional cmpfn

Function: stable-sort-by seq key &optional cmpfn

Function: stable-sort-by! seq key &optional cmpfn

keyをシーケンスseqの各要素に適用して得られる値の比較をもとに seqをソートします。(stable-sort-by seq key cmp)は次のコードと 同じ結果を返します:

(stable-sort seq (lambda (a b) (cmp (key a) (key b))))

よりコンパクトに書けるという以外に、 sort-by族の手続きはkey手続きをたかだかseqの要素数 しか呼び出さないという性質があります。上記のstable-sortを 使った例では、keyはseqの要素数をnとする時 nlogn 回以上呼び出される可能性があります。 したがって、sort-by族はkey手続きが比較的高価な場合に 威力を発揮します。

トレードオフは空間です。sort-by族はあらかじめ比較対象となる 値を計算しておくために、seqの要素数に比例した余分なメモリを 必要とします。

This document was generated by Shiro Kawai on November, 22 2009 using texi2html 1.78.