0

hit受信したsのパラメータをobject取得して、その頻度を表示したいと思います。そして、最も頻繁に、トップhit、objectsを持つことができます。 キーと値としてUnordered_map、最初の部分に適合します。objecthit

unordered_map<object,int>

をすばやく検索しobjectてインクリメントできますhit。しかし、並べ替えはどうですか？priority_queueトップヒットオブジェクトを持つことができます。しかし、オブジェクトのヒットを増やすのはどうですか？

4

2 に答える 2

0

最新かつ最も頻繁にアクセスされるオブジェクトが一番上に近づくようにオブジェクトを保持する splayツリーを確認することをお勧めします。これはいくつかのユーリスティックスに依存しているため、完全なソリューションの近似値が得られます。

正確な解決策を得るには、独自のバイナリ ヒープを実装し、操作のインクリメントの優先度を実装することをお勧めします。理論的には のバッキングにも同じことが使用されpriority_queueますが、優先度の変更操作はありませんが、データ構造の操作の複雑さに影響を与えることなく実行できます。

于 2013-02-09T13:48:40.070 に答える
0

オブジェクトを挿入するときに、オブジェクトのソートされたリストをヒット番号で追跡することで、なんとか解決しました。そのため、最多 N 件のトップ ヒットのリストが常に存在します。3,000,000 個のオブジェクトがあり、上位 20 個を取得したいと考えています。

私が使用した構造は次のとおりです: key_hitヒットを追跡するため (キー、文字列、つまりオブジェクト):

unordered_map<string, int> key_hit;

2 つの配列 :トップ ヒットとそれに対応するキー (オブジェクト) が含まれますhits[N]。keys[N]

idx,    hits,   keys
 0,     212,    x
 1,     200,    y
 ...
 N,     12,     z

key_idxキーとそれに対応するインデックスを保持する別のマップ:

unordered_map<string,int> key_idx;

アルゴリズム (詳細なし):

  • keyが入力されます。
  • を検索keyしkey_hit、そのヒットとインクリメントを見つけます (これは十分に高速です)。
  • の場合hit<hits[N]は、無視してください。
  • else, idx=key_idx[key], (見つからない場合は構造に追加し、既存のものを削除します。すべての詳細を記述するには長すぎます)
  • H=h[idx]++
  • 上記のエントリよりも大きいかどうかを確認しh[idx-1]<Hます。key_idxはいの場合、 、hits、の idx と idx-1 を入れ替えkeysます。

早くしてみました。でもどこまで速いかわかりません。

于 2013-02-12T12:35:22.930 に答える