4

QuickSorts (Single Pivot、3-way、および Dual Pivot) のパフォーマンスを大まかにベンチマークしようとしています。

質問 1 : 3 分割の実装で何かが足りないのではないかと心配しています。ランダムな入力 (1000 万) の数値に対して数回実行すると、単一のピボットのパフォーマンスが常に向上することがわかりました (ただし、1000 万の数値では約 100 ミリ秒の差があります)。

3 ウェイの全体的な目的は、重複キーでの 0 (n^2) パフォーマンスではないことを理解しています。これは、重複入力に対して実行すると非常に明白です。しかし、重複データを処理するために、わずかなペナルティが 3-way にかかるというのは本当ですか? それとも私の実装が悪いですか？

重複データ:

  • Quick Sort Basic : 888 ミリ秒
  • クイック ソート 3 ウェイ: 522 ミリ秒
  • クイック ソート デュアル ピボット: 482 ミリ秒

ランダムデータ:

  • クイックソート基本: 1677 ミリ秒
  • クイックソート 3 ウェイ: 1717 ミリ秒
  • クイック ソート デュアル ピボット: 1595 ミリ秒

質問2 ：

デュアル ピボットの実装 (以下のリンク) は、重複を適切に処理しません。実行には 0(n^2) 時間がかかります。早送りする良い方法はありますか？ピボットが等しいかどうかを確認し、pivot2 と異なるまで、pivot1 をインクリメントできることがわかりました。これは公正な実装ですか？

else if (pivot1==pivot2){
        while (pivot1==pivot2 && lowIndex<highIndex){
            lowIndex++; 
            pivot1=input[lowIndex];
        }
    }

実装リンク:

ルートフォルダー: https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick

QuickSort (単一ピボット) : https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java

QuickSort (3 ウェイ パーティション) : https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java

QuickSort (デュアル ピボット) : https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java

テストケース: https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java

4

1 に答える 1

0

まず第一に、コンストラクターの suffle を取り除き、正しい比較を行います。

第 2 に、基本バージョンでは、QuickSortBasic.java のように、両側で適切な候補が見つかった場合にのみ切り替えを行うため、動作は期待どおりです。

    while (true){

        while (less(input[++i], input[pivotIndex])){
            if (i==highIndex) break;
        }

        while (less (input[pivotIndex], input[--j])){
            if (j==lowIndex) break;
        }

        if (i>=j) break;

        exchange(input, i, j);

    }

一方、3way バージョンでは、要素がピボットと等しくない限り、つまり、QuickSort3Way.java で切り替えを行っています。

    while (i<=gt){


        if (less(input[i],pivotValue)){
            exchange(input, i++, lt++);
        }
        else if (less (pivotValue, input[i])){
            exchange(input, i, gt--);
        }
        else{
            i++;
        }


    }
于 2013-06-13T07:45:00.277 に答える