トークンバケット

溜めておいて、一気に使える

前回は回数を数えるだけでした。今回は時間を入れます。

入れ物に札を溜めておき、要求が来るたびに1枚使います。札が無ければ断ります。

札は時間とともに一定の速さで増え、入れ物の大きさまで溜まります。

# 入れ物5枚、毎秒1枚ずつ増える
# 何もしないと5枚まで溜まる

なっています。一瞬は5回まで、続けるなら毎秒1回までです。

人の使い方は均一ではありません。画面を開いた瞬間に4回、そのあとしばらく何もしない、という形です。溜められる仕組みは、その形をそのまま通します。

長い目で見ると速さは変わらない

溜めた札を使い切れば、あとは増える速さでしか使えません。

1分間で使える回数は、溜めた5枚を足しても毎秒1枚 × 60秒 + 5枚です。長く見るほど、5枚の差は小さくなります。

叩けます。だから入れ物の大きさは、一度に来てよい最大の数として決めます。

増える速さが平均の上限、入れ物の大きさが突発の上限です。2つの数字が別々の意味を持つのが、この方式の要点です。

上限で止めてから、使えるかを決める

min(a, b) は小さいほうを返します。if と else で、条件が成り立つときと成り立たないときの動きを分けられます。例えば電池の充電なら次のように書けます。

charge = 7
added = 5
charge = min(10, charge + added)
if charge >= 4:
    message = "ready"
else:
    message = "wait"
# charge は上限の10、message は "ready"

>= は以上、tokens -= cost は tokens = tokens - cost と同じです。減算した値は次の要求にも引き継がれます。

演習のひな形は時刻と費用を取り出し、経過秒から増える枚数 gained を計算します。受講者は補充後の枚数を上限で止め、費用を払えるなら札を減らして decision を決めます。結果の追加と前回時刻の更新は完成済みです。

演習

時刻つきの要求と、入れ物の大きさ・増える速さから、通すか断るかを決めます。

1. はじめは入れ物いっぱいに札がある。前の要求からの経過秒 × refill_per_second だけ札を増やす。ただし capacity を超えない
2. 経過秒は前の要求の at との差。1件目は時刻0から at までの差。拒否した要求も前回時刻として更新する
3. 札が cost 以上あれば "allowed" にして cost だけ減らす。足りなければ "blocked" にして減らさない
4. events は at の小さい順。同時刻もある。at は0以上、capacity と refill_per_second は0以上、cost は正の数。札は小数のまま保持する
5. 現在の費用は cost、補充される枚数は gained。decision に "allowed" または "blocked" を入れる。返す辞書の decisions は順番通りの判定、tokens_left は最後の残量