14

grepcodeでjava.util.ArrayListのsort()メソッドのソース コードを見ていました。小さな配列 (サイズ < 7) では挿入ソートを使用し、大きな配列ではマージソートを使用しているようです。サイズが7未満の配列に対してのみ挿入ソートを使用することを考えると、それが大きな違いを生むかどうか疑問に思っていました.実行時間の違いは、最新のマシンではほとんど目立ちません。

私はコーメンでこれを読みました：

マージソートは O(n*logn) の最悪ケースの時間で実行され、挿入ソートは O(n*n) の最悪ケースの時間で実行されますが、挿入ソートの定数係数により、実際には多くのマシンで小さな問題サイズの場合は高速になります。 . したがって、部分問題が十分に小さくなったときに、マージ ソート内で挿入ソートを使用して再帰の葉を粗くすることは理にかなっています。

必要なコンポーネントのソートアルゴリズムを設計した場合、マージソートと比較して実行時間の違いが明らかになる前に、より大きなサイズ (おそらくサイズ < 100) に挿入ソートを使用することを検討します。

私の質問は、サイズ < 7 に到達する背後にある分析は何ですか?

4

3 に答える 3

16

実行時間の違いは、最新のマシンではほとんど目立ちません。

並べ替えアルゴリズム全体が再帰的であり、小さな配列の並べ替えが実質的にその再帰の基本ケースであることを認識すると、小さな配列の並べ替えにかかる時間が非常に重要になります。

7番がどのように選ばれたかについての内部情報はありません。ただし、小さな配列で競合するアルゴリズムをベンチマークし、それに基づいて最適なアルゴリズムとしきい値を選択した結果として、それが行われなかったとしたら、私は非常に驚かれることでしょう。

PS Java7はデフォルトで Timsort を使用することに注意してください。

于 2012-05-04T17:08:18.230 に答える
1

将来このスレッドにアクセスする人々のためにこれを投稿し、私自身の研究を文書化しています. 7 を選択するという謎の答えを見つけるために、この素​​晴らしいリンクに出くわしました。

Tim Peters によるアルゴリズムの説明

「minrun の計算」というタイトルのセクションを読む必要があります。

要点を説明すると、minrun は、アルゴリズムが挿入ソートの使用を開始する配列のカットオフ サイズです。したがって、配列全体をソートするためにマージ操作を実行する必要があるサイズ「minrun」のソート済み配列が常に存在します。

java.util.ArrayList.sort() では、「minrun」が 7 になるように選択されていますが、上記のドキュメントに関する私の理解が進む限り、その神話は崩壊し、2 の累乗に近く、256 未満である必要があることが示されています。および 8 以上。ドキュメントからの引用:

256 では、バイナリ挿入ソートのデータ移動コストが明らかに悪影響を及ぼし、8 では、関数呼び出し数の増加が明らかに悪影響を及ぼしています。ここでは、マージが完全にバランスが取れたものになるように、2 の累乗を選択することが重要です (次のセクションを参照)。

私が指摘しているのは、「minrun」は、TimSort のパフォーマンスを妨げることなく、64 未満の任意の 2 のべき乗 (またはほぼ 2 のべき乗) にすることができるということです。

于 2012-05-04T19:44:05.817 に答える
-1

http://en.wikipedia.org/wiki/Timsort

「Timsortは、マージソートと挿入ソートから派生したハイブリッドソートアルゴリズムであり、多くの種類の実世界のデータで適切に機能するように設計されています。このアルゴリズムは、すでに順序付けされているデータのサブセットを検索し、そのサブセットを使用してソートします。データをより効率的に。これは、特定の基準が満たされるまで、実行と呼ばれる識別されたサブセットを既存の実行とマージすることによって行われます。」

7番について：

"...また、ギャロッピングは、最初の要素が他の実行の最初の7つの要素の1つではない場合にのみ有益であることがわかります。これにより、MIN_GALLOPが7に設定されます。ギャロッピングモードの欠点を回避するために、マージ関数はmin-gallopの値を調整します。要素が現在検討中の配列（つまり、要素をしばらく連続して返している配列）からのものである場合、min-gallopの値は1つ減ります。それ以外の場合。 、値が1ずつ増加するため、ギャロッピングモードに戻ることはできません。これを行うと、ランダムデータの場合、min-gallopの値が大きくなり、ギャロッピングモードに戻ることはありません。

merge-hiを使用する場合（つまり、マージは右から左に行われる）、ギャロッピングはデータの右端、つまり最後の要素から開始する必要があります。最初からギャロッピングしても必要な結果が得られますが、必要以上に比較が行われます。したがって、ギャロッピングのアルゴリズムには、ギャロッピングを開始するインデックスを与える変数の使用が含まれます。したがって、アルゴリズムは任意のインデックスでギャロッピングモードに入り、上記のように続行できます。たとえば、1、3、7、....、（2k-1）だけオフセットされた次のインデックスでチェックします。など、現在のインデックスから。merge-hiの場合、インデックスへのオフセットは-1、-3、-7、...になります。」

于 2012-05-04T18:33:21.147 に答える