スライド窓

窓を時刻に張り付ける

固定窓は、境目で2倍通るのが弱点でした。

原因は、窓が時計に固定されていることです。0秒から60秒まで、60秒から120秒まで、と決め打ちしています。

スライド窓は、窓を要求の時刻に張り付けます。いま来た要求から見て、過去60秒に何件あったかを数えます。

# いまが60秒なら、0秒より後に通った件数を数える
# 59秒の3件がまだ窓に入っている

違います。さっきの境目の例で、60秒の3件は全部断られます。

59秒の3件がまだ窓の中にいるからです。どの瞬間から見ても、過去60秒は3件までになります。

覚える量が増える

弱点もあります。固定窓は区間ごとの数字1つで済みましたが、スライド窓は通した時刻を全部覚えます。

1分60件までなら60個、1分6000件までなら6000個です。相手の数だけ倍になります。

置き場所が要ります。台が複数あるなら、その置き場所は全部の台から見える所でなければいけません。

制限のために、守る対象より壊れやすい部品を足すことになりかねません。正確さと持ち物の多さは、ここでも釣り合いです。

条件に合う値だけを新しい一覧へ移す

一覧を絞るときは、空の一覧に、条件を満たす値だけを append で追加できます。len は一覧の件数を返します。次は重さが基準より大きい荷物だけを残す例です。

weights = [1, 4, 2, 6]
heavy = []
for weight in weights:
    if weight > 3:
        heavy.append(weight)
weights = heavy
# weights は [4, 6]、len(weights) は2

> はより大きい、< はより小さいを表します。weights = heavy は絞った一覧への置き換えです。演習でも新しい一覧 active に有効な時刻だけを残し、passed を置き換えます。

窓の左端ちょうどの時刻は外します。いまが60秒、窓が60秒なら0秒は外れ、0秒より後は残ります。通した要求だけを記録し、断った要求は窓に加えません。集計と出力はひな形で渡します。

演習

時刻つきの要求と上限・窓の長さから、通すか断るかを決めます。

1. 通した時刻を覚えておく。新しい要求が来たら、at - window_seconds 以下の時刻は窓から外す
2. 窓に残っている件数が limit に達していたら "blocked"、まだなら "allowed" にして at を覚える
3. allowed と blocked には、それぞれの件数の合計を入れる
4. events は at の小さい順。同時刻もある。at と limit は0以上、window_seconds は正の数。limit が0ならすべて断る
5. now は現在時刻、cutoff は窓の左端、active は残す時刻を入れる空の一覧。passed を active に置き換え、通す場合だけ passed に now を加えて decision を "allowed" にする。decision の初期値は "blocked"