1

ソートされた double のセットがあるとします。

{ 0.124, 4.567, 12.3 }

コードの別の部分によってゼロ以外の正の double が作成され、ソートされたままこのセットに挿入する必要があります。たとえば、作成された double が の7.56場合、最終結果は次のようになります。

{ 0.124, 4.567, 7.56, 12.3 }

私のコードでは、この「double を作成してソート済みセットに挿入する」プロセスが何度も繰り返されます。おそらく50万回から100万回。合計でいくつの double が正確に作成されるかはわかりませんが、上限はわかっています。

試み

私の素朴な最初のアプローチは、長さ = 上限の配列を作成し、それをゼロで埋めてから、最初の double のセットを追加することでした (「追加」= 0 値のエントリを double に置き換えます)。double が作成されるたびに、それを配列に追加して挿入ソートを実行します。これは、順序付けられた配列のソートに適しています。

質問

500k から 100 万の挿入スロットを実行すると、深刻なパフォーマンスの問題になると感じています。(または私は間違っていますか?) C でこれを行うためのより効率的なデータ構造やアルゴリズムはありますか?

編集：

セットをソートしたままにしておく理由は、「double を作成してソート済みセットに挿入する」プロセスのたびに、そのセット内の最小の要素を検索できるようにする必要があるためです (そして、それを 0 に置き換えて削除する可能性があります)。 ）。これを行う最善の方法は、セットをソートしておくことだと思いました。

しかし、そうでない場合、おそらく代替手段はありますか?

4

2 に答える 2

6

やりたいことはすべての反復で最小要素を引き出すことだけなので、代わりにmin-heapを使用してください。それらを実装して、O(1)の挿入、O(1)の find-min、および O(1)のキーの減少操作を行うことができます (ただし、最小要素の削除には常に O(log n) の時間がかかることに注意してください)。あなたがしていることについては、ヒープはかなり高速になります。

于 2012-09-26T17:23:26.940 に答える
3

挿入ソートを実行する代わりに、バイナリ検索を使用して挿入ポイントを見つけ、そこに値を挿入することができます。しかし、これは時間がかかります。大量のデータを何度もシフトする必要がある可能性があるためです (ランダムなデータが必要なものとは逆にソートされた場合に何が起こるかを考えてみてください。タイミングは になりますO(N^2))。

最速のアプローチは、最初に挿入してから、すべてを一度にソートすることです。これが不可能な場合は、配列をRB-Treeなどの自己均衡型の順序付きツリー構造に置き換えることを検討してください。

于 2012-09-26T17:11:25.153 に答える