performance - アレイ管理の時間計算量 (アルゴリズム)

Question

私は、整数の束 (y) を取り、x 個の最大の整数を順番に返す必要があるプログラムに取り組んでいます。このコードはできるだけ高速にする必要がありますが、現時点では最適なアルゴリズムを持っているとは思いません。

これまでの私のアプローチ/アルゴリズムは、既に入力されている整数 (高から低) のソートされたリストを作成し、各項目が入ってくると処理することです。最初の x 項目については、ソートされた整数の配列を維持します。新しいアイテムが入るたびに、バイナリソートを使用して配置する場所を見つけます。(最初の x 個のアイテムを取り込んですばやく並べ替えることも考えていますが、これがより速いかどうかはわかりません)最大の整数の既にソートされたリスト (新しい整数がリストの末尾の整数より大きいかどうかを確認することによって) であり、大きい場合は、バイナリ検索を介してソートされたリストに追加し、末尾の整数を削除します。リスト。

どうすればこれを高速化できるか、またはおそらくこれよりも高速なまったく新しいアプローチについて誰かアドバイスがあればと思っていました。ありがとう。

Answer 1

これは部分的な並べ替えです:

最速の実装は、下位/上位k要素を含む範囲でのみ再帰するクイックソートです。

C++では、単に使用できますstd::partial_sort

Answer 2

ソート順で上位 N 個のアイテムは必要ないようです。このため、これを線形時間で解くことができます。

線形時間選択を使用して、N 番目に大きい配列要素を見つけます。それとそれより大きいすべての配列要素を返します。

Answer 3

ヒープ順序付けされたツリー データ構造を使用して整数を格納する場合、新しい整数の挿入には lg N 回の比較しか必要なく、最大値の削除には 2 lg N 回の比較しか必要ありません。したがって、y項目を挿入するのに必要なのは比較だけであり、最上位の項目y lg Nを削除するのに必要なのは比較だけです。ウィキペディアのエントリには、さまざまな実装への参照があります。x2x lg N

Answer 4

これはトップ N ソートと呼ばれます。これは非常にシンプルで効率的なスキームです。派手なデータ構造は必要ありません。

1. 最高の x 要素のリストを保持します (最初は空です)
2. x * 10入力を項目のチャンクに分割します
3. チャンクごとに、これまでに x 個の最高のアイテムの記憶済みリストを追加し、並べ替えます (例: クイック 並べ替え)。
4. x 最高の項目を保持します。それらは新しい記憶されたリストを形成します
5. すべてのチャンクが処理されるまで 3 に進む
6. 記憶されたリストが最終結果になります

これはO(N)アイテムの数であり、プリミティブとして通常のクイック ソートのみが必要です。