各アイテムのカウントを保持することなく、「最も頻繁なアイテム」をカウントするアルゴリズムがあるかどうか疑問に思っていましたか? たとえば、私が検索エンジンで、最も人気のある 10 件の検索を追跡したいとします。私がやりたくないのは、カウントするにはクエリが多すぎる可能性があるため、すべてのクエリのカウンターを保持することです (そして、それらのほとんどはシングルトンになります)。これには簡単なアルゴリズムがありますか？たぶん確率的なものですか？ありがとう！
4 に答える
4
非常に多数のクエリがある場合 (おそらく検索エンジンのように)、クエリの「サンプリング」を実行できます。したがって、1 秒あたり 1,000 件のクエリを取得している可能性がありますが、1 秒あたり 1 回だけカウントし続けると、長い期間にわたって、「実際の」回答に比較的近い回答が得られます。
これは、たとえば、「サンプリング」プロファイラーがどのように機能するかです。nミリ秒ごとに、現在実行されている関数を調べます。長い時間 (数秒) をかけて、「高価な」関数についての良いアイデアを得ることができます。なぜなら、これらの関数はサンプルに頻繁に現れるからです。
それでも「カウント」を行う必要がありますが、定期的なサンプルを実行することで、すべてのクエリをカウントする代わりに、実際に保存する必要があるデータ量の上限を取得できます (たとえば、1 秒あたり最大 1 つのクエリなど)。
于 2010-05-05T06:41:09.100 に答える
2
常に最も頻繁な検索が必要な場合は、送信された各クエリを追跡する無限のカウンターを用意する必要はありません。代わりに、特定のクエリの送信量を一定期間で割った値を測定するアルゴリズムが必要です。これはかなり単純なアルゴリズムです。検索エンジンに送信された検索 (たとえば、「キャッシュ」という単語) は、リフレッシュ レートと呼ばれる一定期間保存されます (リフレッシュ レートの長さは、検索エンジンが取得するトラフィックの種類と量によって異なります)。追跡したい「上位の結果」)。リフレッシュ レートの期間が終了し、「キャッシュ」という単語の検索が持続しない場合、クエリはメモリから削除されます。「キャッシュ」という単語の検索が続く場合、アルゴリズムは「キャッシュ」という単語の検索率を追跡するだけで済みます。これを行うには、すべての検索を「leaky-counter」に保存するだけです。すべてのエントリは、クエリが削除された後の有効期限とともにカウンターにプッシュされます。アクティブなカウンターは、上位のクエリの指標です。
于 2010-05-05T20:24:40.960 に答える
0
すべてのクエリを保存すると費用がかかりますが、上位 10 件が実際に上位 10 件であることを確認する必要があります。ごまかす必要があります。
1 つのアイデアは、URL、ヒット カウンター、タイムスタンプのテーブルを、カウント、次にタイムスタンプでインデックス付けして保存することです。テーブルが任意のほぼ最大サイズに達したら、指定された日数よりも古いローエンド エントリの削除を開始します。古くて頻度の低いクエリはカウントされませんが、クエリ レートが高速であるため、上位 10 位に入る可能性が高いクエリがテーブルに含まれるはずです。
もう 1 つのアイデアは、検索クエリ用に 16 ビット (またはそれ以上) のハッシュ関数を作成することです。カウンターと URL を保持する 65536 エントリのテーブルを用意します。検索が実行されると、それぞれのテーブル エントリがインクリメントされ、必要に応じて URL が設定されます。ただし、このアプローチには大きな欠点があります。スパム ボットは、「安いバイアグラ」のようなクエリを繰り返し作成し、代わりに正当なクエリでスパム クエリ カウンタを増やし、メッセージをメイン ページに配置する可能性があります。
于 2010-05-05T06:51:17.137 に答える
0
多くの種類があるキャッシュが必要です。ウィキペディアの キャッシュ アルゴリズムと ページ置換アルゴリズムのエージングを参照してください。
于 2010-05-05T10:54:38.827 に答える