2

これで、式ができました。y=0.5*a+0.7*b+0.4*cここで、0<a,b,c<1。たとえば、の値のリストテーブルがあるとしますa,b,c。

(a,   b,   c)
---------------
(0.9, 0.4, 0.6)
(0.5, 0.8, 0.4)
(0.7, 0.4, 0.8)
(0.9, 0.2, 0.1)
...

k=3の上位値をすばやく見つける方法はありますyか？

強引な方法は(a,b,c)、計算のためにのすべてのタプルを列挙yし、次にyのk個の最大値を見つけることですが、タプルの数が多い場合、この方法はあまり効率的ではないようです。したがって、他の方法は大歓迎です！

4

3 に答える 3

2

すべてのタプルをウォークオーバーします。読みながら、式を評価し、上位3つの値の配列を維持します。

それよりも賢くしようとすることの問題は、タプルのリストが膨大な場合、プログラムが費やす時間はそれを読むだけで完全に支配され、賢さがあなたをそれから抜け出すことができないということです。式を評価し、配列を上位3つの値で最新の状態に保つことのオーバーヘッドは完全に取るに足らないものであり、読み取り部分にいくつかの指示があります。

（ヒープのようなより凝ったものではなく、配列に上位の値を保持することをお勧めする理由について：k = 3の場合、実行に重要な数の命令を使用するもの、または実行するのに十分なメモリを必要とするものの一定のオーバーヘッド常にキャッシュヒットが発生するわけではなく、データ構造が提供する漸近的な利点を上回ります。）

于 2013-03-26T03:34:59.093 に答える
2

QuickSelectを使用すると、平均してO（n）の複雑さが得られます。

  1. N個の要素があり、y = f（a、b、c）であると仮定して、（a、b、c）のそれぞれについて長さNの配列Yを計算します（Yに（a、b、c）にインデックスを追加します）バックリファレンスについては、後で必要になります）。
  2. YでQuickSelectを使用して、（Nk）次の統計を取得し、結果のYを取得します。要素Y[Nk-1]からY[N-1]は、k個の最大要素になります。
  3. Y[Nk-1]をY[N-1]にソートして、結果を取得します。
于 2013-03-26T03:38:20.787 に答える
1

何をするかに関係なく、テーブル内の各タプルを通過する必要があるため、これは少なくともO(n)操作になります。上位3つの値についてのみ、サイズ3の配列とif必要なチェックをハードコーディングできます。

O(n)したがって、少なくとも1回はテーブル全体を確認する必要があることを考えると、この状況よりもうまくいくことはありません。

于 2013-03-26T03:37:26.377 に答える