C++でヒットカウンターを設計する方法：過去5分間のヒット数を効率的に記録・取得

本記事では、過去5分間（300秒）に受け取ったヒット数を記録・集計するヒットカウンターをC++で設計する方法を解説します。

このシステムでは、秒単位のタイムスタンプを引数として受け取る関数を使用します。呼び出しは必ず時系列順に行われ、タイムスタンプは単調増加すると仮定します。また、最初のタイムスタンプは1から始まるものとします。

なお、複数のヒットがほぼ同じタイミングで到着する可能性がある点にも注意が必要です。

ヒットの記録には hit() 関数を、直近5分間のヒット数の取得には getHits() 関数を使用します。

アルゴリズム（解決手順）

以下の手順で問題を解決します。

• サイズ300の配列 time を定義します（各インデックスに、その位置で最後にヒットがあったタイムスタンプを保持）。
• サイズ300の配列 hits を定義します（各インデックスのヒット回数を保持）。
• hit(timestamp) 関数を定義します。
  • idx = timestamp mod 300 を計算します。
  • time[idx] が timestamp と等しくない場合：
    time[idx] = timestamp、hits[idx] = 1 に設定します（新しい秒なのでカウントをリセット）。
  • それ以外の場合：hits[idx] を1増やします（同じ秒内の追加ヒット）。
• getHits(timestamp) 関数を定義します。
  • ret = 0 で初期化します。
  • i = 0 から 299 までループし、timestamp − time[i] < 300 を満たす場合に ret += hits[i] を行います。
  • ret を返します。

仕組みのポイント

5分間は300秒であるため、配列サイズを300とし、タイムスタンプを300で割った余りをインデックスとして使うことで、メモリ使用量を常に一定に保てます。hit() は O(1)、getHits() は最大300要素の走査で済むため、実質的に O(1) の高速な処理が可能です。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class HitCounter {
public:
    vector<int> time;
    vector<int> hits;
    HitCounter(){
        time = vector<int>(300);
        hits = vector<int>(300);
    }
    void hit(int timestamp){
        int idx = timestamp % 300;
        if (time[idx] != timestamp) {
            time[idx] = timestamp;
            hits[idx] = 1;
        }
        else {
            hits[idx] += 1;
        }
    }
    int getHits(int timestamp){
        int ret = 0;
        for (int i = 0; i < 300; i++) {
            if (timestamp - time[i] < 300) {
                ret += hits[i];
            }
        }
        return ret;
    }
};
main(){
    HitCounter ob;
    ob.hit(1);
    ob.hit(2);
    ob.hit(3);
    cout << (ob.getHits(4)) << endl;
    ob.hit(300);
    cout << (ob.getHits(300)) << endl;
    cout << (ob.getHits(301));
}

入力

ob.hit(1);
ob.hit(2);
ob.hit(3);
ob.getHits(4);
ob.hit(300);
ob.getHits(300);
ob.getHits(301);

出力

3
4
3

実行結果の解説

タイムスタンプ1、2、3でヒットを記録した後、getHits(4) を呼び出すと、直近5分以内のヒットは3件なので「3」が出力されます。

次にタイムスタンプ300でヒットを追加し、getHits(300) を呼び出すと合計4件となるため「4」が出力されます。

最後に getHits(301) を呼び出すと、タイムスタンプ1のヒットは範囲外（301 − 1 = 300 ≥ 300）となるため除外され、「3」が出力されます。