スライド窓｜System Design入門設計判断を数字とコードで確かめる

窓を時刻に張り付ける

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

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

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

Python

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

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

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

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

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

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

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

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