C++でヒットカウンターを設計する

過去5分間に受信したヒット数をカウントするヒットカウンターを設計するとします。 2番目のユニットにタイムスタンプパラメータを受け入れる関数があり、システムに対して時系列で呼び出しが行われていると想定できます（したがって、タイムスタンプは単調に増加します）。また、最も早いタイムスタンプは1から始まると想定しています。

複数のヒットがほぼ同時に到着する可能性があります。

したがって、hit（）関数を呼び出してhitし、getHits（）関数を呼び出してヒット数を取得します。

これを解決するには、次の手順に従います-

• サイズ300の配列時間を定義する

• サイズ300の配列ヒットを定義する

• 関数hit（）を定義します。これにはタイムスタンプが必要です

• idx：=タイムスタンプmod 300

• time [idx]がtimestampと等しくない場合、-

  • time [idx]：=タイムスタンプ

  • hits [idx]：=1

• それ以外の場合

  • hits [idx]：=hits [idx] + 1

• 関数getHits（）を定義します。これにはタイムスタンプが必要です

• ret：=0

• 初期化i：=0の場合、i <300の場合、更新（iを1増やします）、実行-

  • タイムスタンプ-time[i]<300の場合、-

    • ret：=ret + hits [i]

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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