常に HTTP リクエストを取得するサーバーがあるとします。あなたの上司はいくつかの統計を必要としており、任意の時点で最後の 1 分間のヒット数を計算するように求めています。
これを達成するために、どのアルゴリズムとデータ構造を使用しますか?
質問する
4545 次
2 に答える
7
循環バッファを使用します。
組み込みの陳腐化を伴う現在の統計を保持する必要がある場合は常に、リング バッファーが適しています。あなたの場合、循環バッファーの前に新しいパケットを挿入し、バッファーに今から 1 分前のポインターを保持するか、要求時にバイナリ検索を実行することで、最後の 1 分間の要求の数を簡単に保持できます。 .
于 2012-07-28T12:44:43.203 に答える
1
追加専用ファイルがディスク上の対応する動的配列です。各ヒットを配列に追加するだけで、時間順にソートされます。追加には償却定数時間がかかります。バイナリ検索 (または補間検索) を実行して、最後の 1 分間の開始点を見つけ、O(lg n ) (または (O(lg lg n ))) 時間で最後まで合計することができます。
または、バイナリ検索の代わりに最後から線形スキャンを実行します。これは、ファイルが非常に大きくなり、最後の分だけが必要な場合に高速になります。最後の 1 分間の予想されるヒット数が時間に依存しない場合、これには一定の時間しかかかりません (ただし、逆方向に回転するディスク上のファイルの読み取りは遅くなる可能性があります)。
古いデータをすべて格納するスペースがない場合は、deque を使用することをお勧めします。deque の適切な実装は、C++ や Python などの標準ライブラリで利用できます。
于 2012-07-28T12:34:42.327 に答える