9

名前がすべてを物語っています。一般的にほとんどソートされたデータに最適なソートであるため、挿入ソートが最適であると思います。しかし、私はデータについてより多くのことを知っているので、他の種類のデータが見られる可能性があります。したがって、その他の関連情報は次のとおりです。

1）これは時間データです。つまり、データの順序付けに効果的なハッシュを作成できると思われます。2) 一度にすべてのデータが存在するわけではありません。代わりに、単一のベクトル、または数十または数百のベクトルを含むレコードを読み取ります。5 秒のウィンドウ内で常に出力したい。したがって、データを挿入するときに並べ替えを行う並べ替えがより良いオプションになる可能性があります。3) メモリは大きな問題ではありませんが、CPU 速度はシステムのボトルネックになる可能性があるためです。

これらの条件を考えると、挿入ソートに加えて検討する価値のあるアルゴリズムを誰かが提案できますか? また、「ほとんどソート」を定義して、適切なソートオプションを決定するにはどうすればよいですか? つまり、データをどのように見て、「これは思ったほどソートされていないか、挿入ソートはもはや最良の選択肢ではない」と判断したということです。プロセスの複雑さを考慮した記事へのリンクは、データが並べ替えられた程度に関連する複雑さをより適切に定義します。

ありがとう

編集：情報をありがとうございました。今のところ、簡単な挿入またはマージ ソート (事前に作成した方) を使用します。ただし、最適化フェーズに近づいたら、他の方法をいくつか試します (実装にはより多くの労力がかかるため)。助けてくれてありがとう

4

6 に答える 6

3

あなたが提案したオプション（2）を採用することができます - 要素を挿入しながらデータを並べ替えます。

データを維持するために、昇順で並べ替えられたスキップ リストを使用します。

  • 新しいメインディッシュが到着したら、最後の要素よりも大きいかどうかを確認します (簡単かつ迅速)。これらのケースでは、スキップ リストは平均で 2 つのノードを追加する必要があり、これらのケースではO(1)平均になります。
  • 要素が最後の要素よりも大きくない場合は、それを標準の挿入操作としてスキップ リストに追加しますO(logn)。

このアプローチにより、順不同で挿入された要素の数であるO(n+klogn)アルゴリズムが得られます。k

于 2012-06-13T14:17:53.710 に答える
2

問題が発生した場合の最良のケースと典型的な最悪のケースで得られる自然なバージョンを実装する場合、マージソートを投入します。挿入すると、最悪の場合と最良の場合が得られます。O(N)O(N log N)O(N^2)O(N)

于 2012-06-13T14:12:47.930 に答える
2

n時間内にk要素がずれているサイズのリストを並べ替えることができますO(n + k lg k)。

参照: http://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of- elements-say-up-to-to-to-tal-of-the-total-whose-position-are-known/answer/Mark-Gordon-6?share=1

基本的な考え方は次のとおりです。

  • 配列の要素を反復処理し、増加するサブシーケンスを構築します (現在の要素がサブシーケンスの最後の要素以上の場合は、サブシーケンスの最後に追加します。それ以外の場合は、現在の要素と最後の要素の両方を破棄しますサブシーケンスの）。これにはO(n)時間がかかります。
  • 2k要素は場違いなので、破棄するのはk要素だけです。
  • マージソートやヒープソートなどのソートアルゴリズムを使用して、破棄された2k要素をソートします。O(k lg k)
  • これで、2 つの並べ替えられたリストができました。O(n)マージソートのマージ ステップと同じように、時間内にリストをマージします。

全体的な時間の複雑さ =O(n + k lg k)

全体的なスペースの複雑さ =O(n)

(これは、宇宙でO(1)マージできる場合は宇宙で実行するように変更できますがO(1)、決して簡単なことではありません)

于 2014-10-31T00:27:54.060 に答える
1

問題を完全に理解していなくても、データの大部分はすでにソートされていると主張しているため、 Timsortは問題に合う可能性があります。

于 2012-06-13T22:01:46.137 に答える
0

ほとんどがソートされたデータをソートするように特別に設計された、多くの適応ソートアルゴリズムがあります。日付を格納しているという事実を無視して、最悪の場合の O(n log n) 時間と最良の場合の O(n) で合理的にソートされたデータをソートできるアルゴリズムとして、 smoothsortまたはデカルト ツリー ソートを検討することをお勧めします。時間。Smoothsort には、挿入ソートのように O(1) スペースしか必要としないという利点もあります。

すべてが日付であり、したがって整数に変換できるという事実を利用して、中央値 3 のピボット選択を使用してバイナリ クイックソート (MSD 基数ソート) を検討することをお勧めします。このアルゴリズムは、最高の O(n log n) パフォーマンスを備えていますが、定数係数が非常に低いため、非常に競争力があります。最悪のケースは O(n log U) です。ここで、U は各日付のビット数 (おそらく 64) であり、それほど悪くはありません。

お役に立てれば！

于 2012-06-13T16:43:11.200 に答える
0

OS または C ライブラリがマージソート関数を提供している場合、O(N) 時間で実行される、指定されたデータが (任意の方向に) 部分的に順序付けられている場合を既に処理している可能性が非常に高くなります。

それ以外の場合は、お気に入りの BSD オペレーティング システムから利用可能なマージソートをコピーするだけです。

于 2012-06-13T16:50:07.950 に答える