Java 7 のドキュメントが見つかりません。Java 6 についてしか見つけることができません。Java 6 はまだ高速またはマージされています。Arrays.sortJava 7でメソッドのドキュメントを見つける方法を知っている人はいますか?
質問する
27684 次
3 に答える
84
Java 7 は、プリミティブに Dual-Pivot Quicksort を使用し、オブジェクトに TimSort を使用します。
実装に関する注意: ソート アルゴリズムは、Vladimir Yaroslavskiy、Jon Bentley、および Joshua Bloch による Dual-Pivot Quicksort です。このアルゴリズムは、多くのデータ セットに対して O(n log(n)) のパフォーマンスを提供するため、他のクイック ソートのパフォーマンスは 2 次パフォーマンスに低下します。通常、従来の (1 ピボット) クイック ソートの実装よりも高速です。
オブジェクトのJava 7 APIドキュメントによると：
この実装は、Tim Peters の Python 用リスト ソート (TimSort) から採用されました。離散アルゴリズムに関する第 4 回 ACM-SIAM シンポジウムの議事録、pp 467-474、1993 年 1 月の Peter McIlroy の「Optimistic Sorting and Information Theoretic Complexity」の技術を使用しています。
Timsortは、"マージ ソートと挿入ソート" のハイブリッドです。
Arrays.sort JDK6の場合、これが Java 6 の場合と大きく異なるかどうかはわかりません。
Jon L. Bentley と M. Douglas McIlroy の「Engineering a Sort Function」、Software-Practice and Experience、Vol. 23(11) P.1249-1265 (1993 年 11 月)
Object[] またはコレクション (Collections.sort()) の場合、マージ ソートが使用されます。
于 2010-10-25T20:01:57.917 に答える
29
はい！...そしてまたいいえ。
概要
執筆時点 (2016 年) では、現在の Open JDK 0Arrays.sort(Object[])実装では、Tim Sort は通常、オブジェクトの配列 (つまり、友人)のソートに使用されますが、プリミティブ配列(残りのArrays.sortメソッド) には、さまざまな他のメソッドが使用されます。 .
プリミティブの場合、ヒューリスティックは、クイックソート、マージソート、カウントソート3などのさまざまなソート方法から選択します。ソートされるデータに応じて。これらの決定のほとんどは、ソートされる配列のタイプとサイズに基づいて単純に前もって行われますが、および要素の決定は、測定された配列のソート度に基づいて実際に適応されます。したがって、多くの場合、適応/イントロスペクション (TimSort または同様のマージソート) に加えて、適応/イントロスペクション (アルゴリズムを選択するためのヒューリスティック) があります!intlong
詳細
Tim Sort は、システム プロパティを trueArrays.sort(Object[] a)に設定して従来の動作を特に要求しない限り、 などのほとんどの種類のオブジェクトに使用されます。java.util.Arrays.useLegacyMergeSort
プリミティブの場合、状況はより複雑になります。少なくとも JDK 8 (バージョン1.8.0_111) では、ソートされる配列のサイズ、プリミティブ型、および配列の測定された「ソート度」に応じて、さまざまなヒュースティックが使用されます。概要は次のとおりです。
- バイト1以外のすべてのプリミティブ型では、要素数が 47 未満の配列は、挿入ソートを使用して単純にソートされます (「参考文献」を参照
DualPivotQuicksort.INSERTION_SORT_THRESHOLD)。このしきい値は、マージまたはクイックソートが使用され、サブアレイのサイズがしきい値を下回ったときに発生するサブアレイをソートするときにも使用されます。したがって、何らかの形式の挿入ソートがすべてのソートで使用され、小さな配列の場合はそれが使用される唯一のアルゴリズムです。 - プリミティブ型
byte、shortおよびcharの場合、大きな配列にはカウントソートが使用されます。これは、O(n + range)時間がかかる単純な並べ替えrangeです。並べ替えには、基になる値の配列の割り当てが含まrangeれるため、並べ替える要素の数が範囲全体のかなりの部分である場合にのみ使用されます。特に、29 要素を超えるバイト配列 (つまり、範囲の ~11%) と、3200 要素を超える short/char 配列 (範囲の ~5%) に使用されます。 - バイト配列の場合、上記の 2 つの方法のいずれかが常に使用されます。
- 挿入ソートしきい値を超える配列
intと、挿入ソートしきい値を超えてカウント ソートしきい値を下回る/配列の場合、デュアル ピボット クイックソートまたはマージ ソートの 2 つのアルゴリズムのいずれかを使用できます。どちらが使用されるかは、配列の並べ替えの尺度によって異なります。入力は、昇順または降順の要素の実行に分割されます。そのような実行の数が 66 を超える場合、配列はほとんどソートされていないと見なされ、デュアル ピボット クイックソートでソートされます。それ以外の場合、配列はほとんどソートされていると見なされ、mergesort が使用されます (既に列挙された実行を開始点として使用します)。longshortchar
実行を見つけてからマージソートを使用して並べ替えるという考え方は、実際には TimSort と非常によく似ていますが、いくつかの違いがあります。したがって、少なくともいくつかのパラメーターについては、JDK は run-aware マージソートを使用していますが、パラメーターの他の多くの組み合わせについては、別のアルゴリズムを使用しており、合計で少なくとも 5 つの異なるアルゴリズムが使用されています!
根拠
対プリミティブの異なる並べ替え動作の背後にある理由Object[]は、おそらく少なくとも 2 つあります。
1) 並べ替えは安定しObject[]ている必要があります: 均等に並べ替えられるオブジェクトは、入力と同じ順序で表示されます。プリミティブ配列の場合、そのような概念は存在しません。プリミティブはその値によって完全に定義されるため、安定ソートと不安定ソートの区別はありません。これにより、プリミティブな並べ替えは、速度を優先する安定したアルゴリズムの必要性をなくすことができます。
2)任意に複雑で費用がかかる可能性があるメソッドを使用Object[]する必要があります。Object.compare()メソッドが単純な場合でも、compare()並べ替えメソッド全体をインライン化できない限り、通常はメソッド呼び出しのオーバーヘッドが発生します2。そのObject[]ため、アルゴリズムの複雑さをいくらか犠牲にしても、全体的な比較を最小限に抑える方向にバイアスがかかるのが一般的です。
一方、プリミティブ配列の並べ替えは、通常は 1 ～ 2 サイクル程度かかるプリミティブ値を直接比較するだけです。この場合、比較のコストと周囲のアルゴリズムの両方を考慮してアルゴリズムを最適化する必要があります。
0少なくとも Java 7 と Java 9 の間のバージョンの場合、もちろんこれには、Open JDK に基づいているため、Oracle の JDK も含まれます。他の実装でも同様のアプローチが使用されている可能性がありますが、私は確認していません。
1バイト配列の場合、挿入ソートのしきい値は事実上 29 要素です。これは、カウントソートが使用される下限カットオフであるためです。
2非常に大きいため、これはありそうにありません。
3カウントソートは、16 ビット以下の比較的限られた範囲の値にのみ使用されます: byte、shortまたはchar.
于 2016-12-13T19:39:22.720 に答える
21
はい、Java 7 は Arrays.sort に Timsort を使用します。ここにコミットがあります： http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79
于 2010-10-25T20:51:26.370 に答える