データの集計、たとえば配列でトップkクエリを計算する最適な方法を見つけようとしています。以前は、配列全体を実行し、サイズ k のヒープまたはバランスの取れたバイナリ ツリーを維持し、それを利用して上位 k 値を計算するのが最善の方法だと考えていました。ここで、さらに高速に実行されると思われる選択アルゴリズムに出くわしました。選択アルゴリズムの仕組みと実装方法は理解していますが、O(n) での実行方法について少し混乱しています。O(n) で実行するには、非常に幸運である必要があると思います。ランダムなピボット ポイントを選択し、その周りで分割し続けると、k 番目のインデックスに出くわす前に、基本的に配列のほぼ全体をソートすることになる可能性が非常に高くなります。ランダムなピボットを選択しないなどの最適化はありますか? または、ほとんどの場合、ヒープ/ツリーメソッドを維持するだけで十分ですか。
1 に答える
1
あなたが話しているのは、Hoareの選択アルゴリズムとも呼ばれるquickselectです。
平均的なケースのパフォーマンスがO(n)ありますが、最悪のケースのパフォーマンスは.O(n2)
クイックソートと同様に、クイック選択は平均的なパフォーマンスが優れていますが、選択されたピボットに敏感です。適切なピボットが選択された場合、つまり検索セットを特定の割合で一貫して減少させるピボットが選択された場合、検索セットのサイズは指数関数的に減少し、帰納法 (または等比級数の合計) によって、各ステップが線形であり、パフォーマンスが線形であることがわかります。全体の時間はこれの定数倍です (検索セットがどれだけ速く減少するかによって異なります)。ただし、毎回 1 つの要素だけ減少するなど、不適切なピボットが一貫して選択される場合、最悪の場合のパフォーマンスは 2 次になります。
O(n2)
ピボットの選択に関して:
最も簡単な解決策は、ランダムなピボットを選択することです。これにより、ほぼ一定の線形時間が得られます。決定論的には、3 の中央値のピボット戦略 (クイックソートなど) を使用できます。これは、現実の世界で一般的であるように、部分的に並べ替えられたデータに対して線形のパフォーマンスをもたらします。ただし、不自然なシーケンスは依然として最悪の場合の複雑さを引き起こす可能性があります。David Musser は、その戦略に対する攻撃を可能にする「中央値 3 キラー」シーケンスについて説明しています。これは、彼のintroselectアルゴリズムの 1 つの動機でした。
より洗練されたピボット戦略を使用することで、最悪の場合でも線形パフォーマンスを保証できます。これは、中央値アルゴリズムの中央値で行われます。ただし、ピボットの計算のオーバーヘッドが高いため、これは一般的に実際には使用されません。フォールバックとして基本的なクイック選択を中央値の中央値と組み合わせて、高速な平均ケースのパフォーマンスと線形の最悪のケースのパフォーマンスの両方を得ることができます。これは introselect で行われます。
（ウィキペディアより引用）
O(n)したがって、ランダムなピボットでパフォーマンスが得られる可能性はかなり高いですが、kが小さくてn大きい場合、または可能性が低い場合はO(n log k)、サイズkヒープまたは BST を使用したソリューションがこれよりも優れている可能性があります。
n(1) 正確な実装、(2) それが実行されるマシン、(3) の正確なサイズ、kそして最後に (4) 実際のデータに依存します。 . ほとんどの場合、このO(n log k)ソリューションで十分です。
于 2014-01-17T01:20:21.243 に答える