104

クイック ソートが最速のソート アルゴリズムであることはわかっています。

JDK6collections.sortは、クイック ソートの代わりにマージ ソート アルゴリズムを使用します。ただし、Arrays.sort はクイック ソート アルゴリズムを使用します。

Collections.sort がクイックソートではなくマージソートを使用する理由は何ですか?

4

1 に答える 1

199

Josh Bloch からの可能性が高い§ :

私はこれらのメソッドを書いたので、答える資格があると思います。確かに、最適なソート アルゴリズムは 1 つではありません。マージソートと比較した場合、QuickSort には 2 つの大きな欠点があります。

  1. それは安定していません（parsifalが指摘したように）。

  2. n log n のパフォーマンスを保証するものではありません。病理学的入力では二次性能に低下する可能性があります。

プリミティブ型の安定性は問題ではありません。これは、(値) の等価性とは異なるアイデンティティの概念がないためです。また、2 次動作の可能性は、Bentely と McIlroy の実装 (またはその後のDual Pivot Quicksort )では実際には問題ではないと見なされたため、これらの QuickSort バリアントがプリミティブ ソートに使用されました。

任意のオブジェクトをソートする場合、安定性は非常に重要です。たとえば、電子メール メッセージを表すオブジェクトがあり、最初に日付で並べ替え、次に送信者で並べ替えるとします。各送信者内で日付順に並べ替えられることを期待していますが、それは並べ替えが安定している場合にのみ当てはまります。そのため、オブジェクト参照をソートするための安定したソート (マージ ソート) を提供することにしました。(技術的に言えば、複数の連続した安定した並べ替えは、並べ替えの逆順でキーの辞書式順序付けを行います。最終的な並べ替えによって、最も重要なサブキーが決定されます。)

Merge Sortが入力に関係なく n log n (時間) のパフォーマンスを保証することは、副次的な利点です。もちろん、マイナス面もあります。クイック ソートは「その場での」ソートです。log n の外部スペースのみが必要です (コール スタックを維持するため)。一方、マージ、ソートには O(n) 外部スペースが必要です。入力配列がほぼソートされている場合、TimSort バリアント (Java SE 6 で導入) が必要とするスペース (O(k)) は大幅に少なくなります。

また、以下が該当します。

オブジェクト参照をソートするために java.util.Arrays.sort および (間接的に) java.util.Collections.sort によって使用されるアルゴリズムは、「変更されたマージソート (下位サブリストの最上位の要素がより小さい場合はマージが省略される)」です。上位サブリストの最下位の要素)。」これは、O(n log n) のパフォーマンスを保証し、O(n) の余分なスペースを必要とする、かなり高速な安定した並べ替えです。当時 (Joshua Bloch によって 1997 年に書かれました)、これは良い選択でしたが、今日ではもっとうまくやることができます。

2003 年以来、Python のリストの並べ替えは、timsort と呼ばれるアルゴリズムを使用しています (Tim Peters の記述にちなんで)。これは安定した適応型の反復マージソートであり、部分的にソートされた配列で実行する場合は n log(n) よりはるかに少ない比較しか必要とせず、ランダム配列で実行する場合は従来のマージソートに匹敵するパフォーマンスを提供します。すべての適切なマージソートと同様に、timsort は安定しており、O(n log n) 時間 (最悪の場合) で実行されます。最悪の場合、timsort は n/2 オブジェクト参照用の一時記憶域を必要とします。最良の場合、一定量の少量のスペースしか必要としません。これを、n 個のオブジェクト参照に対して常に余分なスペースを必要とする現在の実装と比較してください。ほぼソートされたリストでのみ n log n を上回っています。

Timsort については、 http ://svn.python.org/projects/python/trunk/Objects/listsort.txt で詳しく説明しています。

Tim Peters のオリジナルの実装は C で書かれています。Joshua Bloch はそれを C から Java に移植し、結果として得られたコードを徹底的にテスト、ベンチマーク、および調整しました。結果のコードは、java.util.Arrays.sort のドロップイン置換です。高度に順序付けられたデータでは、このコードは現在の実装 (HotSpot サーバー VM 上) の最大 25 倍の速度で実行できます。ランダム データでは、古い実装と新しい実装の速度は同等です。非常に短いリストの場合、新しい実装は、ランダム データであっても古い実装よりも大幅に高速です (不要なデータのコピーが回避されるため)。

また、Java 7 はメソッド Arrays.Sort に Tim Sort を使用していますか?も参照してください。.

「最良」の選択肢は 1 つではありません。他の多くのことと同様に、それはトレードオフに関するものです。

于 2013-03-01T09:20:11.600 に答える