14

整数キーの配列をソートしています。

データに関する情報:

  • 配列の長さは 1176 要素です
  • キーは 750 000 から 135 000 000 の間です。0も可能
  • 多くの重複があり、すべての配列には 48 から 100 の異なるキーしかありませんが、全範囲のどの値がそれらになるかを予測することは不可能です
  • 多くの長いソートされたサブシーケンスがあり、ほとんどの配列は 33 から 80 のソートされたサブシーケンスで構成されています
  • 最小要素は 0 です。0 の数は予測可能であり、配列ごとに約 150 という非常に狭い範囲です。

私がこれまでに試したこと：

  1. stdlib.h qsort ;

    これは遅いです。現在、私の関数は実行ごとにソートに 0.6 秒を費やしています。stdlib.h qsort では 1.0 秒です。これは std::sort と同じパフォーマンスです

  2. ティムソート;

    私はこれを試しました: https://github.com/swenson/sortとこれ: http://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17 ; どちらも stdlib qsort よりも大幅に遅かった

  3. http://www.ucw.cz/libucw/ ;

    クイックソートと挿入ソートの組み合わせは、これまでのところ私のデータでは最速です。さまざまな設定を試し、中央の要素 (3 の中央値ではない) としてピボットし、28 要素のサブ配列 (デフォルトでは 8 ではない) で始まる挿入ソートで最高のパフォーマンスが得られました

  4. シェルソート;

    この記事からのギャップのある単純な実装: http://en.wikipedia.org/wiki/Shellsort ; 標準ライブラリqsortより遅いですが、まともでした

私の考えでは、qsort は多くのスワップを行い、並べ替えられたサブシーケンスを台無しにする (つまり、逆にする) ため、データの構造を利用して改善する方法があるはずですが、残念ながらこれまでのところすべての試行が失敗しています。
それがどのような種類のデータであるかに興味がある場合、それらは、前のボードで既にソートされているさまざまなボードで評価されたポーカー ハンドのセットです (ソートされたサブシーケンスはここから来ます)。

関数は C です。私は Visual Studio 2010 を使用しています。何かアイデアはありますか?

サンプル データ: http://pastebin.com/kKUdnU3N
サンプル フル実行 (1176 ソート): https://dl.dropbox.com/u/86311885/out.zip

4

8 に答える 8

7

最初に配列を通過して数値をグループ化し、重複を取り除くとどうなるでしょうか。各数値は、数値がキーであり、出現回数が値であるハッシュテーブルに入れることができます。したがって、750 000 という数字が配列に 57 回出現する場合、ハッシュテーブルは key=750000 を保持します。値=57。次に、はるかに小さいハッシュテーブルをキーで並べ替えることができます。これは、100 要素未満の長さにする必要があります。

これにより、配列を介して 1 つのパスを作成し、はるかに小さいハッシュテーブル キー リストを介して別のパスを作成するだけで済みます。これにより、スワップと比較のほとんどを回避できます。

于 2012-06-19T02:26:40.423 に答える
5

この投稿から見たこのアニメーションをチェックできます

あなたの問題は、3ウェイパーティションのクイックソートとシェルソートが非常に高速な「いくつかのユニークな」カテゴリに分類されると思います。

アップデート：

私はsorting-algorithms.comの擬似コードに基づいていくつかの並べ替えアルゴリズムを実装し、OPによって提供されたサンプルデータでそれらを実行しました。楽しみのためだけに：

挿入0.154秒

シェル0.031s

クイックソート0.018s

基数0.017s

3方向クイックソート0.013秒

于 2012-06-19T02:32:08.123 に答える
2

ソートされたサブシーケンスを利用するアルゴリズムがあります。これは、NaturalMergeSortと呼ばれるMergeSortの変形です。Cでの実装の良い例を見つけることはできませんが、最初から実装するのはそれほど難しくはありません。基本的には次のようになります。

  1. サブシーケンスのインデックスと長さの2つのintを含む構造体が必要です。これらの構造体の新しい配列（またはおそらくリンクリスト）を作成します。
  2. 配列全体を1回繰り返し、値が前の値よりも小さくなるたびに、新しいサブシーケンスの開始になるため、新しい構造体を作成してサブシーケンスの位置を割り当て、前のサブシーケンスの長さを割り当てます-前の構造体へのシーケンス。
  3. 構造体を繰り返し処理し、ペアでそれらに対してマージ操作を実行します。
  4. すべてがマージされるまで、手順3を繰り返します。

マージ操作は、マージソートのマージ操作と同じです。各サブシーケンスの開始へのポインタがあります。小さい方がサブシーケンスの先頭にあるはずなので、まだ移動していない場合はそこに移動し、移動元のサブシーケンスのポインタを進めます。完全にソートされるまで、2つのサブシーケンスのマージを続けます。

これをOleskiの回答と組み合わせて、各ノードに値が含まれ、サブシーケンス内の行に値が出現する回数を含む一種のリンクリストを作成できる場合があります。次に、マージするときに、同等の値が見つかった場合は、それらのカーディナリティを加算して、1回の加算で複数の同一の値を一度にマージします。この潜在的な最適化のためにハッシュを作成する必要はありません。

于 2012-06-19T04:59:16.693 に答える
2

基数ソートまたはバケットソートは、整数に対して効率的であるため、進むべき道のようです。

基数ソートの効率は、桁数が k 以下の n 個のキーに対して O(k·n) です。ときどき k が定数として提示されると、すべて O(n·log(n)) である最良の比較ベースの並べ替えアルゴリズムよりも (n が十分に大きい場合) 基数並べ替えがより適切になります。バケットの並べ替えは、n 個のキーと k 個のバケットに対して O(N*k) です。

基数ソートの定数 (K) 係数になる場合があります。私のJava実験から。また、基数はソートされた要素ではあまり公平ではないことに注意してください。

100k 整数:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.075   0.025   0.025
Quicksort           0.027   0.014   0.015
Heap sort           0.056   0.03    0.03
Counting sort       0.022   0.002   0.004
Radix sort          0.047   0.018   0.016

500k の整数:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.286   0.099   0.084
Quicksort           0.151   0.051   0.057
Heap sort           0.277   0.134   0.098
Counting sort       0.046   0.012   0.01
Radix sort          0.152   0.088   0.079

1M 整数:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.623   0.18    0.165
Quicksort           0.272   0.085   0.084
Heap sort           0.662   0.286   0.207
Counting sort       0.066   0.022   0.016
Radix sort          0.241   0.2     0.164

10M の整数:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          7.086   2.133   1.946
Quicksort           4.148   0.88    0.895
Heap sort           11.396  3.283   2.503
Counting sort       0.638   0.181   0.129
Radix sort          2.856   2.909   3.901

定数がクイックソートよりも基数ソートを優先し始めるのは、500kアイテムのようです。

于 2012-06-19T02:50:29.220 に答える
1

ハッシュテーブルを作成し、配列を割り当てます。入力配列の各項目について、その項目がハッシュテーブルにあるかどうかを確認します。はいの場合、その値をインクリメントします。そうでない場合は、値1のハッシュテーブルに挿入し、配列に追加します。

配列を並べ替えます。配列内のアイテムごとに、ハッシュテーブル内のカウントと同じ回数だけそのアイテムを出力に書き込みます。フィン。

編集：並べ替える必要のある各配列のハッシュテーブルをクリアして再利用できます。

于 2012-06-19T02:33:03.503 に答える
0

私は、各ノードで数値とそれが発生する回数を保存するという特別なトリックを使用して、手作業でコーディングされたqsortを試してみます。もう一度表示されたら、カウントを増やします。

ソートされたサブシーケンスが一連の悪いピボットを与えないように、常に配列の中央からピボットを取ります。

于 2012-06-19T02:31:34.000 に答える
0

並べ替えられた実行を考えると、配列全体が並べ替えられるまで、それらの実行を大きな並べ替えられた実行にまとめるために、インプレース マージを使用することが 1 つの合理的な可能性になります。関数が C インターフェイスのみを必要とする場合 (C 自体で作成する必要はありません)、std::inplace_mergeC++ 標準ライブラリの をextern "C"使用できますが、リンケージ仕様を使用して関数を作成すると、C から使用できるようになります。

于 2012-06-19T05:26:12.263 に答える