Javaの組み込みソートアルゴリズムをどうやって克服したか

Java 8 では、組み込みのソート アルゴリズムが大幅に最適化されました。整数やその他のプリミティブ型の場合、Arrays.sort() はデュアルピボットクイックソート、マージソート、およびヒューリスティック挿入ソートの組み合わせを使用します。このアルゴリズムは非常に強力であり、多くの状況で使用できます。より大きな配列では、より多くのバリアントがサポートされます。急いで書いたソートアルゴリズムを Java に付属のアルゴリズムと比較して、同等かどうかを確認しました。これらの実験には特殊なケースに対する治療が含まれます。

まず、古典的なクイックソートアルゴリズムを作成しました。このアルゴリズムは、サンプルの平均を計算して配列全体の中心点を推定し、それを初期ピボットとして使用します。

クイックソートを適切に改善するために、Java からいくつかのアイデアを借用しました。変更されたアルゴリズムは、小さな配列をソートするときに挿入ソートを直接呼び出します。この場合、私のソート アルゴリズムと Java のソート アルゴリズムは同じ実行時間を達成できます。 Wild らは、ソートする配列に重複が多数ある場合、標準クイック ソートの方がデュアル ピボット クイック ソートよりも高速になると指摘しました。バイトレベルまたはアセンブリレベルの分析と最適化は試みませんでした。ほとんどの問題において、私のバージョンのオプティマイザーは、Java システム プログラムほど優れていません。

私はずっと、頭の中にあった「Bleedsort」というシンプルなソート アルゴリズムをテストしたいと思っていました。これは、サンプルサンプリング方式によりソート対象となる配列の分布を推定し、推定結果に応じてデータを対応する一時配列に分散し（図1参照）、初期配列を書き換える分散アルゴリズムです。これは前処理プロセスであり、その後、他のソート アルゴリズムが適用されて個別にソートされます。テストでは、私が作成したクイックソートのバージョンを使用しました。マージ ソートは高度に構造化された配列で広く使用されているため、マージ ソートを使用すると、より良い結果が得られます。計算を簡単にするために、均一分布のデータのみをテストしました。

ブリードソートでは、同じデータを見つけるたびにそれを右側に配置するため、このアルゴリズムは、比較的一貫性のある配列をソートする場合のパフォーマンスが低下します。したがって、ソートされた配列に対してサンプル推定を実行し、重複が多い場合はブリードソート アルゴリズムを使用しないようにする必要があります。

ブリードソート アルゴリズムは、メモリ領域の使用量の点ではマージ ソート (クイック ソート) に匹敵しないことは明らかであり、一時配列は元の配列の約 4 倍の大きさになります。同時に、Flashsort などの他の分散ソート アルゴリズムも、この点でははるかに優れたパフォーマンスを発揮します。

図1 ブリードソートの例

ベンチマークとしてJMHを使用しました。 簡単にするために、テストには整数配列を使用します。私のアルゴリズムは、1000.000 から 10.000.0000 程度の均一に分散された配列に対して最高のパフォーマンスを発揮します。私が書いたクイック ソート アルゴリズムは、ある程度 Java 組み込みアルゴリズムほど優れているわけではありませんが、私の前処理プロセスはこれらの欠点をうまく補っています (クイック ソートを呼び出すブリードソートは 87 ミリ秒、Java 組み込みアルゴリズムは 105 ミリ秒、938 ミリ秒、1.144 秒)

ベンチマーク モード Cnt スコア エラー単位修正

MyBenchmark._1e6U サンプル 8512 0.024 ± 0.001 s/op

MyBenchmark._1e7U サンプル 985 0.236 ± 0.001 s/op

私は以下の正しいベンチマーク配列を生成した。

MyBench.int1e6UQuickSort サンプル 1641 0.131 ± 0.001 s/op 0.107 ± 0.002

MyBench.int1e6UBleedSort サンプル 2410 0.087 ± 0.001 s/op 0.063 ± 0.002

MyBench.int1e6UJavaSort サンプル 1978 0.105 ± 0.001 s/op 0.081 ± 0.002

MyBench.int1e7UQuickSort サンプル 200 1.483 ± 0.014 s/op 1.459 ± 0.015

MyBench.int1e7UBleedSort サンプル 373 0.938 ± 0.009 s/op 0.914 ± 0.010

MyBench.int1e7UJavaSort サンプル 200 1.144 ± 0.009 s/op 1.120 ± 0.010

したがって、特別な最適化を行わない私のアルゴリズム プログラムは、これらのデータ セット上の Java ネイティブ アルゴリズムよりも約 10 ～ 15% 高速になります。

私のアルゴリズムは、10% または 1% のランダム重複を含む 1000,000 項目の均等に増加するデータセットで良好に機能します。

ベンチマーク モード Cnt スコア エラー単位修正

._1e6Iwf010 サンプル 20705 9.701 ± 0.033 ms/op

._1e6Iwf001 サンプル 148693 1.344 ± 0.003 ms/op

正しいベンチマーク配列を生成する

.int1e6Iw010ブリードソートサンプル 4159 49.377 ± 0.571 ms/op 39.68 ± 0.60

.int1e6Iw010JavaSort サンプル 3937 52.139 ± 0.229 ミリ秒/操作 42.44 ± 0.25

.int1e6Iw010クイックソートサンプル 3899 52.457 ± 0.210 ms/op 42.76 ± 0.23

10% 重複データ

.int1e6Iw001ブリードソートサンプル 6190 32.821 ± 0.219 ms/op 31.48 ± 0.22

.int1e6Iw001JavaSort サンプル 8113 24.910 ± 0.079 ミリ秒/操作 23.57 ± 0.08

.int1e6Iw001クイックソートサンプル 8653 23.367 ± 0.056 ms/op 22.02 ± 0.06

^^ 1%

ただし、このアルゴリズムは、約 10,000 件のケース (~bin(100,0.5)) のみの小さな二項分布データセットではパフォーマンスが低下します。 平均すると、これらの配列では数字 50 が 795.5 回出現し、40 の繰り返し配列の数は 108.4 回出現します。

同時に、1000.0000 オーダーの大きな配列をソートする場合、このアルゴリズムは Arrays.sort() よりも約 2 倍遅くなります。これらの配列には重複データが多数あります (たとえば、サイズ 1e6 の 1 つの配列には 450 個の異なる値しかありません)。

ベンチマーク モード Cnt スコア エラー単位修正

._1e4bin100 サンプル 152004 1.316 ± 0.001 ms/op

^^訂正します

.int1e4bin100BleedSort サンプル 148681 1.345 ± 0.001 ms/op 0.029 ± 0.002

.int1e4bin100JavaSort サンプル 150864 1.326 ± 0.001 ms/op 0.010 ± 0.002

.int1e4bin100クイックソートサンプル 146852 1.362 ± 0.001 ms/op 0.046 ± 0.002

.int1e6bin1e4BleedSort サンプル 75344 2.654 ± 0.005 ms/op -

.int1e6bin1e4JavaSort サンプル 146801 1.361 ± 0.002 ms/op -

.int1e6bin1e4QuickSort サンプル 76467 2.615 ± 0.005 ms/op -

小さな (10,000、100,000) 均一ランダム配列をソートする場合、このアルゴリズムは正常に動作しますが、体系的なアルゴリズムより優れているわけではありません。

MyBench.int1e4UBleedSort サンプル 216492 0.924 ± 0.001 ms/op 0.683 ± 0.002

MyBench.int1e4UJavaSort サンプル 253489 0.789 ± 0.001 ms/op 0.548 ± 0.002

MyBench.int1e4UQuickSort サンプル 217394 0.920 ± 0.001 ms/op 0.679 ± 0.002

MyBench.int1e5UBleedSort サンプル 18752 0.011 ± 0.001 s/op 0.009 ± 0.002

MyBench.int1e5UJavaSort サンプル 22335 0.009 ± 0.001 s/op 0.007 ± 0.002

MyBench.int1e5UQuickSort サンプル 18748 0.011 ± 0.001 s/op 0.009 ± 0.002

全体として、メモリがそれほど不足しておらず、データ セットが適度に大きい場合は、分散検索アルゴリズムを有効な補足オプションとして推奨します。

最後に、二項分布データセットbin(100, 0.5)とbin(1000, 0.5)を見てみましょう。

以下は、ランダムにサンプリングされた 100 個のデータ ポイントを含む 2 つのデータセット (R を使用して生成) です。

> rbinom(100, 100, 0.5)

[1] 43 49 51 47 49 59 40 46 46 51 50 49 49 45 50 51 50 49 53 52 45 53 48 56 45

[26] 47 55 47 53 53 56 41 47 42 51 51 46 49 49 52 46 48 49 50 48 56 54 49 53 52

[51] 54 48 45 45 50 48 54 49 52 50 48 48 49 45 54 54 50 41 53 45 51 48 53 52 52

[76] 50 53 47 55 47 60 54 52 56 45 46 54 46 38 43 53 45 62 48 52 52 52 49 52 56

> rbinom(100, 1000, 0.5)

[1] 515 481 523 519 524 516 498 473 523 514 483 496 458 506 507 491 514 489

[19] 475 489 485 507 486 523 521 492 502 500 503 501 504 482 518 506 498 525

[37] 498 491 492 479 506 499 505 497 510 479 504 510 485 488 495 519 522 490

[55] 517 511 511 488 519 508 475 521 505 493 480 498 490 492 492 476 490 506

[73] 496 505 521 518 506 509 477 483 509 493 497 501 483 502 470 515 519 509

[91] 510 496 477 508 506 481 490 511 498 476