スリーウェイクイックソートでより高いパフォーマンスが必要

Question

私は現在、3つのパーティションのクイックソートを実装しようとしています。以下のコードは正常に動作しますが、十分に十分な時間稼働しません。私はデータ構造、アルゴリズム、そして一般的な "深みのある"プログラミングに新しいので、時間をかけずに動作させるためにそれを試してみるという試みはほとんど無意味です。 （メモリのパフォーマンスは問題ありません）

私の直感はピボットを変更することですが、3方向のクイックソートではないと心配しています。

#include <iostream> 
#include <vector> 
#include <cstdlib> 

using std::vector; 
using std::swap; 


int partition3(vector<int> &a, int l, int r) { 

    int x = a[l]; 
    int j = l; 
    int k = r; 
    int i = l+1; 

    while (i <= k) { 
     if (a[i] < x) { 
      swap(a[i],a[j]); 
      j++; 
      i++; 
     } 
     else if(a[i] > x) { 
      swap(a[i],a[k]); 
      k--; 
     } 
     else { 
      i++; 
     } 
    } 

    return j; 
} 

void randomized_quick_sort(vector<int> &a, int l, int r) { 

    if (l >= r) { 
     return; 
    } 

    int k = l + rand() % (r - l + 1); 
    swap(a[l], a[k]); 

    while (l < r) { 
     int m = partition3(a, l, r); 
     if ((m-l) < (r-m)) { 
      randomized_quick_sort(a, l, m - 1); 
      l = m + 1; 
     } 
     else { 
      randomized_quick_sort(a, m + 1, r); 
      r = m - 1; 
     } 
    } 
} 

int main() { 
    int n; 
    std::cin >> n; 
    vector<int> a(n); 
    for (size_t i = 0; i < a.size(); ++i) { 
     std::cin >> a[i]; 
    } 
    randomized_quick_sort(a, 0, a.size() - 1); 
    for (size_t i = 0; i < a.size(); ++i) { 
     std::cout << a[i] << ' '; 
    } 
} 

Answer 1

ソートは現実世界では非常に複雑な問題です。例えば、C++標準ライブラリの実装によって提供されるものなど、いくつかの効率的な実装を見てみましょう。

ただ、いくつかの注意、...の議論を見て、記事を読んで、ウェブも見てみよう

1. 乱数生成は、（比較的）高価であり、それはクイックソート大幅に遅くなることができます。 （ただし、何らかのデータに対しても逆のことができます）
2. 整数除算は（比較的）非常に高価で、乱数生成以上の可能性があります。
3. 純粋なクイックソートは、実際にはめったに使用されません。典型的には、再帰呼び出しは非常に小さい区画（閾値は通常8〜16の間のどこかに設定されます）では非効率的であるため、挿入ソートと組み合わされます。
4. クイックソートのワーストケースの複雑さを防ぐには、通常、再帰のレベルがチェックされ、しきい値（2 x log_2（n））を超える場合、残りのデータは別のアルゴリズム（通常はヒープソート）で保存されます。

等...

UPDATE

つ以上の思考：

マルチコア/マルチコア環境で

、並列アルゴリズムおそらくあなたのための最高のスピードアップを提供します。しかし、並列クイックソートを設計することは簡単です。複雑さの大部分は、効率的なパラレル・パーティショニングとロード・バランシングにあります。 LibstdC++ Parallel Modeには素晴らしいOpenMP実装があります。または、私のAQソート：https://github.com/DanielLangr/AQsortをチェックすることもできます。

quicksortをより効率的にするには、テールコール除去/最適化を使用します。これは、必要なコールスタックスペースを大幅に削減します。

Answer 2

ここでは、実際のコードを見ています。

アルゴリズムを維持したい場合は、それを高速化する最も良い方法は、反復から反復に変更することです。それは巨大な後押しではありませんが、それが助けになるでしょう、それぞれの呼び出しは避けるのが良いオーバーヘッドです。手動でスワップすることも良い選択です。

余分なメモリ割り当てを避けるためにある程度の速度を得ることができるので、できる限り多くの変数を再利用するようにしてください。