＊＊＊＊＊　クイックソート開発　の　概要　＊＊＊＊＊ 1997年に当時の fj.sources にqsort(クイックソート)の ベンチマークテストの依頼を掲載しました。 その結果(http://ww51.tiki.ne.jp/~srr-cake/qsort/qs6qs7-rslt.txt) ※１、 自作のqsort(qs6,qs7)の性能はともかく、コンパイラ付属のqsortの中に まともな性能が出ないqsortが多数存在することが判明しました。 今回、より高速な qsort (qs9) を開発しました。 １．各ファイルの概略 qs9e17.c : 新しく開発したqsort。 mm88c.c : スワップ関数。8バイト整数対応。1回の繰り返しで8回swapする。 main_prog.c : 比較回数・代入回数・処理時間などを計測して表示するプログラム。 benchmark.sh : ベンチマークテストを行うシェルスクリプト。 　　　　　　　 コンパイルオプション -DDEBUG を指定すれば、要素の代入回数を測定できる。 ２．qs6 qs7 qs8 qs9 の概要 qsortにもいろいろな方式がある。 配列を２つに分割するキー値を持つ要素を分割要素と呼ぶ。 以下の例では、先頭の(5)が分割要素に選ばれたものとする。 各qsortは矢印左の配列を矢印右のようにする。「|」は分割した位置を示している。 ２．１．処理の概要 従来型 565238 → 532|568 2番目の(5)が右に移動している。「(5)不移動」の実装は異常事態を招く。（※１） ｑｓ６ 565238 → 5352|68 従来型は2つの(5)が左右に別れるが、qs6では必ず片方に集める。次に 235|5|68 とする。 ｑｓ７ 565238 → 55|32|68 すべての(5)を一旦左右に集める。普通は左右両方に(5)がくる。 次に 32|55|68 とする。 ｑｓ８ ｑｓ６とｑｓ７の混合処理を導入して、多くのケースで高速となるようにした。 ｑｓ９ 565238 → 23|55|68 分割要素と同じキー値を持つ要素を中央に集める。移動できなくなった後に工夫あり。 ２．２．各qsortの特徴 従来型 少し遅い。異常事態を起こす間違った実装が過去にいくつもあった。（※１） ｑｓ６ 要素の比較回数が多く、移動回数が少ない。平均するとｑｓ７と同じか少し速い。 ｑｓ７ 要素の比較回数が少なく、移動回数が多い。キーが２値(男女など)の場合、要素の移動回数が激増する。 ｑｓ８ 下記のパラメータの設定をしなくても、既定値で十分な性能が出る。 qsortでは、要素数・要素サイズ・比較関数の重さ・キー値の分布ごとに、最適なqsortは異なる。 要素数・要素サイズは、ソートの開始時点で確定するのでアルゴリズムで対応可能である。 しかし、比較関数の重さ・キー値の分布は、不明なままソートを実行することになる。 ｑｓ８ではソート対象の性質が分かっていれば、qsort()を呼び出す前に下記のパラメータを設定して 対処することが可能である。（または、適当なパラメータを多数試して、その結果で設定） ｑｓ９ ほとんどの場合、比較回数・移動回数が最小となる。 ２．３．大域変数パラメータ _QS_MID1 配列の長さが n<=_QS_MID1(既定値140) のときに３点処理を行う。 _QS_MID2 配列の長さが n<=_QS_MID2(既定値900) のときに９点処理を行う。それ以外は２７点処理。 _QS_MID3 今回は使用しない。（ｑｓ８で使用） _QS_MVR mm88c.cのswapで size%4==0 && size>_QS_MVR(既定値116) なら８バイト整数でswapを行う。 　　ｑｓ８では 　　　　比較関数　が重たいときはqs7が有利なので、_QS_MID3 を大きくして、qs7 を増やすと良い。 　　　　要素サイズが大きいときはqs6が有利なので、_QS_MID2=0にして、qs6 を増やすと良い。 　　　　キーに重複がない(社員番号など)場合 と キーが２値(男女など)の場合は 　　　　比較関数・要素サイズと無関係に、qs6が有利なので、qs6 だけでソートすると良い。 　　　　隠しコマンドとして、_QS_MID3==100000000 の設定で、全てqs7処理となる。 　　　　また、_QS_MID2==0 && _QS_MID3==0 の設定で、全てqs6処理となる ３．ベンチマークテストを行うプログラム　main_prog.c main_prog.c は clock()関数を用いて実行時間を測定する。 簡易版の「ソートの正しさ検査」を行っている。正式な「ソートの正しさ検査」は別に実施している。 main_prog.c は次のパラメータを指定して実行する。 引数１　キー値の種類を指定する 0:定数 -1:昇順 -2:降順 -3:同値なし乱数 1:乱数 d>=2:乱数%d 引数２　配列の要素の個数 引数３　配列の要素の大きさ(byte数)（4以上かつ4の倍数であること）（qs自体は1byte単位で指定可能） 引数４　ソートの繰り返し回数（繰り返し毎に配列の要素のキー値は異なる） 引数５　_QS_MID1 の値 引数６　_QS_MID2 の値　（main_prog.cでは_QS_MVR==116は変更できない） 引数７　_QS_MID3 の値 引数８　比較関数の重たさを調整する数値。大きいほど比較関数が重たくなる。 main_prog.c 1回の実行で、実行結果を1行出力する。1行は14項目ある。例と意味を次に示す。 qs9e17 d=-3 e=10000 s=8 10 R10000 M300:300:8:0: 　プログラム名 キー値の種類 要素の個数 大きさ 配列の大きさ/M 繰り返し回数　引数５〜８の値 c=130260 1302608733 a=65855 658555016 i=196115 T=19.06 191 　平均比較回数 全比較回数 平均代入回数 全代入回数 比較＋代入 処理秒数 平均処理時間(10μ秒単位) これをstdoutに出力する。（前半の７つと最後の１つはstderrにも出力する） ４．開発時の性能測定の方法(main_prog.cの引数) キー値の種類　：引数１を [ -3 10000 1000 300 100 30 10 3 2 ] の９通りで実施。 要素数　　　　：引数２を 10000 固定で実施。（1000などでも測定したが、大きな差はなかった。） 要素の大きさ　：引数３を [ 8 20 40 100 200 500 1000 ] の７通りで実施。 繰り返し回数　：引数４を調整して、main_prog.cの１回の実行が３０〜５０秒で終了するようにした。 比較関数の重さ：引数８を [ 0 2 4 ] の３通りで実施。 　修正を重ねた数百種類のクイックソートのプログラムを、 　上記の、１８９（＝９ｘ７ｘ３）通り のパラメータで実行した。 ５．その他 mm88c.cでは、sizeが4の倍数・8の倍数のとき、各々に合った高速化を行っている。 1の倍数のときの高速化も同じ方法で可能であるが、 　１）必要性が少ない　２）コードが大きくなり過ぎる ために、mm88c.cでは1の倍数のときの高速化を行っていない。 ben_sample.txtでもわるように、８バイト整数がハードウェアで処理できるシステム(64bitモード)において、 コンパイラ付属の多くのqsortにおいて、配列の要素のsizeが4の倍数(20byteなど)のとき、 かなり遅くなる。ダミーを加えてsizeを24byteにすれば速くなる。 しかし、これでは4byte(配列全体の2割)の領域が無駄になる。 mm88c.cは、20byteのままで高速に動作するよう工夫されている。