すべてのリクエストが記録されているウェブサイトを維持しているとしましょう。任意の時点で過去 5 分間に行われたリクエストの数を確認する方法は?
5分間で解決策にたどり着くことができました。しかし、任意の時間間隔で汎用にする方法がわかりません。
私のアプローチ：
サイズ 300 の配列を保持します。現在のインデックスを表すポインターを配列に保持します (毎秒インクリメントします)。要求が行われるたびに、ポインターが参照している値を返すだけです。最初に配列に入力するために、すべての値が累積されます。たとえば、1 秒目に行われたリクエストの数は 3、2 秒目は 5、3 秒目は 0 です。配列は
3, 8, 8, 0...., 0 のようになり、ポインタが指している場所インデックス番号 2 へ。
(4:59 分に早送りすると、配列の内容は次のようになります) 3, 8, 8,....,180, 0
ここで、299 番目のインデックスを設定していないため、ptr はインデックス 298 を参照します。
ここで、次の 2 秒間に記録されたリクエストの数が 5 と 2 であるとします。配列は次のようになります:
3、8、8、.....、180、185 (5:00 に更新) )
(185+2-3(旧値)), 8, 8, .........., 180, 185 => 184, 8, 8, .......... ..、180、185 (5:01 に更新)
ptr は 0 番目のインデックスを参照します。したがって、現時点で、過去 5 分間に行われたリクエストの数は 184 です。
同様の行で、O(1) でいつでも値を返すことができるはずです。
しかし、ソリューションを汎用的にするにはどうすればよいでしょうか? 過去 10 分間、過去 20 分間、過去 1 分間のリクエストが見つからないなど、期間が任意の場合はどうでしょうか。セグメント ツリーを活用できると思っていましたが、1 秒ごとにすべての値を変更することになり、コストがかかりすぎます。map reduce pgm を考え出すことは、getRequestsinLastNMins() のリクエストが行われるたびに pgm をトリガーする O(N) ソリューションになります。しかし、私は O(1) でできることを探しています。