Pythonで直近の呼び出し回数をカウントする方法【RecentCounterクラスの実装】

問題の概要

「RecentCounter」というクラスを作成し、直近のリクエストをカウントすることを考えます。このクラスには ping(t) というメソッドが1つだけあります。引数 t はミリ秒単位の時刻を表し、このメソッドは「t の3000ミリ秒前から現在まで」に発生した ping の回数を返します。つまり、時刻が [t - 3000, t] の範囲内にある ping はすべてカウント対象となり、現在の ping も含まれます。また、ping が呼び出されるたびに、t は必ず前回より厳密に大きい値になると保証されています。

例えば、ping を4回、ping(1)、ping(100)、ping(3001)、ping(3002) の順に呼び出した場合、出力はそれぞれ 1、2、3、3 となります。

解き方のアプローチ

この問題はキュー（queue）を使うことで効率的に解決できます。手順は以下の通りです。

• クラスの初期化時に空のキューを用意する
• ping(t) メソッドを定義する
• キューが空でなく、かつ t - queue[0] > 3000 である間、キューの先頭要素を削除し続ける
• t をキューの末尾に追加する
• キューのサイズを返す

実装例

class RecentCounter:
    def __init__(self):
        self.queue = []

    def ping(self, t):
        # 3000ミリ秒より古いリクエストを先頭から削除
        while len(self.queue) and t - self.queue[0] > 3000:
            self.queue.pop(0)
        # 現在のリクエストを末尾に追加
        self.queue.append(t)
        return len(self.queue)

ob = RecentCounter()
print(ob.ping(1))
print(ob.ping(100))
print(ob.ping(3001))
print(ob.ping(3002))

入力

ob.ping(1)
ob.ping(100)
ob.ping(3001)
ob.ping(3002)

出力

1
2
3
3

処理の流れを詳しく確認

各呼び出しで何が起こっているのか、順番に見てみましょう。

• ping(1)：キューは空なので、そのまま 1 を追加。キューは [1] となり、戻り値は 1。
• ping(100)：100 - 1 = 99 ≤ 3000 なので削除は不要。100 を追加してキューは [1, 100]、戻り値は 2。
• ping(3001)：3001 - 1 = 3000 ≤ 3000 なので 1 はまだ範囲内。3001 を追加してキューは [1, 100, 3001]、戻り値は 3。
• ping(3002)：3002 - 1 = 3001 > 3000 なので 1 を削除。次に 3002 - 100 = 2902 ≤ 3000 でループ終了。キューは [100, 3001, 3002]、戻り値は 3。

パフォーマンス改善のヒント：collections.deque を使う

Python のリストで pop(0) を使うと、先頭要素を削除するたびに残りの全要素を左にずらす必要があるため、計算量は O(n) になります。代わりに collections.deque を使えば、両端での追加・削除が O(1) で行え、より効率的です。

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()

    def ping(self, t):
        while self.queue and t - self.queue[0] > 3000:
            self.queue.popleft()
        self.queue.append(t)
        return len(self.queue)

このように、単調増加する時刻の系列に対して「古いものから順に取り除く」という操作を行うスライディングウィンドウ型の問題では、キュー構造が非常に有効です。計算量は全体で O(n) に抑えられ、各要素は高々1回の追加と1回の削除しか行われません。