21

昨日、クイックソートの実装に取り​​組んでいましたが、マージソート (これも実装しました) よりも実行時間が速いことを期待して実行しました。私は2つを実行しました.100要素未満の小さなデータセットではクイックソートの方が高速でしたが(動作することを確認しました)、マージソートはかなり迅速なアルゴリズムになりました. クイックソートはほとんどの場合、マージソートよりも「速い」と教えられていました。このトピックについてはいくつかの議論があることを理解していますが、少なくともこれよりも近いと予想していました。10000 要素を超えるデータ セットの場合、マージソートは 4 倍以上高速でした。これは予想されることですか、それともクイックソート コードにエラーがありますか?

マージソート:

public static void mergeSort(int[ ] e)
{
    if (e.length <= 1) return;
    int[] first = new int[e.length/2];
    int[] second = new int[e.length - first.length];
    System.arraycopy(e, 0, first, 0, first.length);
    System.arraycopy(e, first.length, second, 0, second.length);
    mergeSort(first);
    mergeSort(second);
    System.arraycopy(merge(first, second), 0, e, 0, e.length);
}

private static int[] merge(int[] first, int[] second) {
    int iFirst = 0;
    int iSecond = 0;
    int iCombined = 0;

    int[] combined = new int[first.length + second.length];
    while(iFirst < first.length && iSecond < second.length) {
        if (first[iFirst] > second[iSecond]) {
            combined[iCombined++] = second[iSecond++];
        }
        else combined[iCombined++] = first[iFirst++];
    }
    for(; iFirst < first.length; iFirst++) {
        combined[iCombined++] = first[iFirst];
    }
    for(; iSecond < second.length; iSecond++) {
        combined[iCombined++] = second[iSecond];
    }
    return combined;
}

クイックソート:

public static void quicksort(int[] a, int first, int last) {
    if (first >= last) return;

    int partitionIndex = partition(a, first, last);
    quicksort(a, first, partitionIndex - 1);
    quicksort(a, partitionIndex + 1, last);
}

public static int partition(int[] x, int first, int last) {
    int left = first;
    int right = last;
    int pivot = x[first];
    int pivotIdx = first;

    while(left <= right) {
        while(left < x.length && x[left] <= pivot) left++;
        while(right >= 0 && x[right] > pivot) right--;
        if (left <= right) {
            int temp = x[left];
            x[left] = x[right];
            x[right] = temp;
        }
    }
    pivotIdx = right;
    x[first] = x[right];
    x[pivotIdx] = pivot;
    return pivotIdx;
}
4

15 に答える 15

10

私は実際に C で「リンク リスト比較ソート デモ プログラム」を作成し、同様の結論に達しました (ほとんどの場合、マージソートはクイック ソートに勝るということです)。ピボット値の選択は怪物要素であることに注意してください。私の最初のバージョンでは、ピボットとしてランダム ノードを使用していました。2 つの (ランダム) ノードの平均を取るように少し改良すると、1000000 レコードの実行時間になりました。 4 分超から 10 秒未満になり、mergesort と同等になりました。

マージソートとクイックソートは同じ大きな O の最良のケース (n*log(n)) を持ち、人々が主張しようとするかもしれないにもかかわらず、大きな O は実際には反復回数に関するものであり、比較回数に関するものではありません。この2 つの間に生じる可能性のある最大の違いは、常にクイックソートの不利益であり、すでに大部分がソートされているか、多数のタイを含むリストが含まれます (クイックソートがマージソートよりも優れている場合、その差はそれほど大きくありません)。すごい)。これは、同点または既にソートされたセグメントが、マージソートによって直接合理化されるためです。2 つの分割されたリストがマージのために戻ってきたとき、1 つのリストに小さい値がすべて含まれている場合、左側のすべての値が一度に 1 つずつ右側の最初の要素と比較されます。内部指図)比較を行う必要があり、右側は単純に最後まで繰り返されます。つまり、反復回数は一定のままですが、比較回数は半分になります。実際の時間について話し、文字列をソートしている場合、コストがかかるのは比較です。

ピボット値が慎重に決定されない場合、同点とクイックソートで既にソートされたセグメントは、リストの不均衡に簡単につながる可能性があり、不均衡なリスト (たとえば、右側に 1 つ、左側に 10 個) が速度低下の原因です。したがって、ランダム化されたリストと同様に、既にソートされたリストでもクイックソートを実行できる場合は、ピボットを見つけるための優れた方法があります。

興味があれば、デモ プログラムは次のような出力を生成します。

[root~/C] ./a.out -1 3 
Using "", 0 records
Primary Criteria offset=128

Command (h for help, Q to quit): N
How many records? 4000000
New list is 562500.00 kb

Command (h for help, Q to quit): m

Mergesorting..............3999999 function calls
123539969 Iterations     Comparison calls: 82696100
Elapsed time: 0 min 9 sec


Command (h for help, Q to quit): S
Shuffled.

Command (h for help, Q to quit): q

Quicksorting..............4000000 function calls
190179315 Iterations     Comparison calls: 100817020
Elapsed time: 0 min 23 sec

クレイジーカラーなしのAltho。このページの半分くらいのところに、私によるそれについての詳細があります。

ps。どちらの並べ替えも、リンクされたリストで余分なメモリを必要としません。

于 2009-01-31T01:29:43.833 に答える
4

Mergesort は、RAM に収まる限り、ランダム配列ベースのデータに対しては非常に遅くなります。議論されているのを見るのは初めてです。

  • 最短の部分配列を最初にソートします。
  • 5 ~ 25 要素以下の挿入ソートに切り替えます
  • 通常のピボット選択を行う

長さ 2 と 3 の配列を分割して qsort しようとするため、qsort は非常に遅くなります。

于 2009-12-10T00:18:26.860 に答える
3

比較的小さな配列サイズに対するクイックソートの利点の 1 つは、ハードウェア実装の成果物にすぎません。

配列では、クイックソートはその場で実行できます。つまり、メモリの同じ領域から読み書きを行っているということです。一方、マージソートは通常、新しいバッファを割り当てる必要があるため、メモリ アクセスがより分散されます。実装例では、これらの動作の両方を確認できます。

その結果、比較的小さなデータセットの場合、クイックソートはキャッシュ ヒットを取得する可能性が高くなるため、ほとんどのハードウェアでより高速に実行される傾向があります。

あなたの実験が確認したように、Mergesort は、リンクされたリストのような大規模なデータ セットやその他のデータ構造に対して依然としてかなり優れたソリューションです。

于 2009-01-31T01:11:40.203 に答える
3

以前 SO で議論されました: "なぜクイックソートはマージソートよりも優れているのですか? "

于 2009-01-31T00:26:30.870 に答える
2

マージソートの最悪のケースはクイックソートの平均的なケースであるため、適切な実装がない場合、マージソートは全体的に高速になります。クイックソートを高速に動作させるには、平均以下のケースを回避する必要があります。より良いピボットを選択すると (中央値が 3 の場合に役立ちます)、違いがわかります。

于 2009-01-31T00:57:38.093 に答える
2

このウィキペディアの記事に基づいて、結果が期待されます。

于 2009-01-31T00:27:18.623 に答える
1

たとえばCを使用してメモリに直接アクセスすることで、MergesortよりもQuicksortのパフォーマンスを向上させることができると想像できます。

もう1つの理由は、マージソートをインプレースソートとして実装するのが難しいため、より多くのメモリが必要になることです。

特に実装では、ピボットの選択を改善できます。適切なピボットを見つけるためのさまざまなアルゴリズムがあります。

ウィキペディアで見られるように、クイックソートはさまざまな方法で実装できます。

于 2009-01-31T00:36:08.120 に答える
1

(1)C qsort()で使用されるqsortアルゴリズムがあり、追加のメモリを必要としません。これはおそらくHoareによって発明されました。これにより、Cでqsort()が高速になります。

(2)qsortを実行する前にデータをランダム化すると、ほとんどの場合、データが高速化されます。

(3)ピボットの中央値データを選択すると、データが速くなる可能性があります。

于 2009-01-31T01:39:10.863 に答える
1

同様のテストを実行したところ、純粋なクイック ソート (ピボットをランダムに選択) は、大きな配列のマージ ソートよりもはるかに遅いことが判明しました。

最初、中間、および最後の要素の中央値としてピボットを選択すると、クイック ソートのパフォーマンスが向上しましたが、大きな配列 (> 100000 要素) では、クイック ソートはマージ ソートよりも明らかに劣っていました。

イントロソートを実装すると、大きな改善が見られました。つまり、再帰の深さが特定のしきい値を超えた場合にヒープソートにフォールバックするクイックソートです。イントロ ソートの実装は、マージ ソートの実装とほぼ同じ速さでした。もちろん、純粋なクイックソートが悪いデータにヒットした場合、ヒープソートを使用して複雑さを n log(n) に戻すため、イントロソートはもはや純粋なクイックソートではありません。興味があれば、結果を投稿できます。

于 2012-05-15T18:08:03.607 に答える
1

これは、アルゴリズムの分析と一致しています。マージソートは、すべての入力およびすべてのランタイムに対して O(nlogn) が保証されています。クイックソートは、最良の場合は O(nlogn)、平均の場合は O(nlogn) ですが、最悪の場合は O(n^2) であるため、平均的な実行は O(nlogn) と O(n^2) の間になります。

クイックソートは、オーバーヘッドが少ないため、一般的なアルゴリズムとして最適です。n の値が約 10000 程度までは速度が速く、n の任意の天文学的な値でも実行時間は長くなります。マージソートには、すべての再帰呼び出しで必要となるスタック フレームの書き込みという不幸なオーバーヘッドがあります。したがって、n の値が小さい場合、RT = cnlogn の c が非常に高くなり、好ましい一般的なソート方法ではありません。

編集: Software Monkey は矛盾を指摘しました: クイックソートは、ランダムな入力に対して平均 O(nlogn) ですが、最悪の場合は O(n^2) です。したがって、実際にはデータのエントロピーによってある程度拘束されます。または、ピボットをランダムに選択することもできます。まだ少しずれてるかもしれませんが。

于 2009-01-31T04:42:04.817 に答える
1

I think as long as data fits in memory, good merge sort implementation performs better than good quick sort implementation.

One of the most widely used implementations of qsort(), glibc qsort(), internally uses merge sort for most of the cases when data fits in memory. This merge sort allocates a temporary memory space used for merging, which adds some memory overhead, but most of the time, it outperforms its own internal quicksort implementation with good pivot selection and optimization. glibc only uses quicksort when the data and the temporary memory for merge sort cannot fit in memory.

I have measured performance of those two implementation on my machine with 2.1GHz CPU with several GB of RAM. The inputs are generated with pseudo-random generator, and each key is 32bit unsigned integer, which means a bit of more comparison cycles than integer comparison due to interface of comparison function.

For merge sort:

2 MB, time_diff 165.156000 ms, 78.752518 ns per byte
4 MB, time_diff 344.298000 ms, 82.087040 ns per byte
8 MB, time_diff 730.926000 ms, 87.133169 ns per byte
16 MB, time_diff 1541.215000 ms, 91.863573 ns per byte
32 MB, time_diff 3088.924000 ms, 92.057109 ns per byte
64 MB, time_diff 6262.868000 ms, 93.324006 ns per byte
128 MB, time_diff 12887.018000 ms, 96.015766 ns per byte
256 MB, time_diff 26731.597000 ms, 99.582959 ns per byte

For quick sort:

2 MB, time_diff 243.519000 ms, 116.118908 ns per byte
4 MB, time_diff 504.975000 ms, 120.395422 ns per byte
8 MB, time_diff 1075.276000 ms, 128.182888 ns per byte
16 MB, time_diff 2183.865000 ms, 130.168498 ns per byte
32 MB, time_diff 4343.993000 ms, 129.461080 ns per byte
64 MB, time_diff 8714.166000 ms, 129.851192 ns per byte
128 MB, time_diff 17881.344000 ms, 133.226395 ns per byte
256 MB, time_diff 36751.029000 ms, 136.908252 ns per byte

You can see that there are clear differences in performance between those two implementation and why mergesort is preferred over quicksort in such widely used qsort implementation. The main reason behind this difference seems to be because quick sort has 10-20% more comparisons than merge sort, due to uneven splitting at each step.

于 2012-11-21T22:37:22.153 に答える
0

データセットは十分にランダムでしたか? それらは部分的にソートされましたか?

それはソートの速度に影響を与える可能性があります...

QuickSort の partition() と同様に、番号がソートされている場合は、そうでないものが見つかるまでスキップします。

于 2009-01-31T00:47:06.413 に答える
0

テスト用に並べ替えるデータの種類 (既に並べ替えられたリスト、ランダム化、逆並べ替え) によって異なる場合があります。また、最初の要素を使用する代わりにランダムなピボットを選択すると、クイックソートはおそらく一般的に高速になります。

于 2009-01-31T00:48:56.707 に答える