Sqsort のベンチマークテストの要領 １．Sqsort の概略 http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/qiita.txt ２．http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/ から次の５つのファイルをダウンロードする。 http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/benchmark http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/TimSort.java http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/Sqsort.c http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/MainTim.java http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/MainSqsort.java ３．benchmark を実行する。実行結果は benchmark.txt へ書き込まれる。 Sqsort.c は cpp で Sqsort.java へ変換してからコンパイルする。 　　Main*.java Sqsort.java TimSort.java は benchmark の中でコンパイル・実行される。 　　Main*.java の引数と出力の説明は、「４」を参照 。 bench-sample.txt は benchmark.txt の例です。 ４．ベンチマークテストを行うプログラム　Main＊.java Main*.java は getCurrentThreadCpuTime() を用いてCPU処理時間を測定する。 Main*.java は次のパラメータを指定して実行する。 引数１　キー値の種類 0:定数 -1:昇順 -2:降順 -3:ユニーク乱数 1:乱数 d>=2:乱数%d 引数２　ソートする配列の要素数 引数３　ソートの繰り返し回数（測定時間の精度向上のため） Main*.java 1回の実行で、実行結果を1行出力する。 同じものをSystem.errとSystem.outに出力する。各行の例と意味を次に示す。 TimSort d=-3 e=10000 R=2000 cmp=240783126 C=8.22 　プログラム名 キー値の種類 要素の個数 繰り返し回数　 比較回数 CPU処理秒数 Sqsort は java で記述したソートなので、参照型の配列をソートします。 なので、要素サイズの大小による比較は行っていません。 ★Sqsortの改良 公開した Sqsort は部分配列の長さが n<=15 なら挿入ソート、n>=16 なら３点処理 を行う。 開発過程では下記のような処理も実験している。 部分配列の長さ 対応するソートの種類 n=0 何もしない n=1 必要なら要素を複写 n=2 ： 挿入ソート n=15 ： 精密３点処理 n=50 ： ３点処理 n=220 ： ９点処理 n=880 ： ２７点処理 この改良は、Sqsortを言語Cで記述した場合や、javaの32bit環境では一定の性能を発揮する。 しかし、javaの64bit環境ではかえって遅くなるケースが多発した。 そのため、最もコンパクトな版を公開することとした。 ★使用した環境 Windows＋cygwin コンパイラ javac AdoptOpenJDK jdk-11.0.8.10-hotspot 64bit環境 java 　AdoptOpenJDK jdk-11.0.8.10-hotspot 32bit環境 java 　AdoptOpenJDK jdk-11.0.8.10-hotspot 64bit環境 java Java SE Development Kit 15　jdk-15.0.2