2026-11-03
refill_ms.cpp
#include <algorithm>
#include <iostream>
long tokens = 1;
long last_ms = 0;
bool take(long now_ms) {
tokens = std::min(1L, tokens + (now_ms - last_ms) / 1000);
last_ms = now_ms;
if (tokens == 0)
return false;
--tokens;
return true;
}
int main() {
for (long t = 0; t <= 3500; t += 700)
std::cout << take(t);
std::cout << '\n';
}
トークンを最大1つまでため、1秒(1000 ミリ秒)に1つずつ補充し、要求1回ごとに1つ使わせて流量を抑えるつもりのプログラムです。時刻 0 ミリ秒から 700 ミリ秒ごとに 3500 ミリ秒まで6回 take を呼び、通ったら 1、断られたら 0 を表示します。本来は 1000、2000、3000 ミリ秒に補充されたトークンで要求が通り、101101 を表示するはずが、いまは最初の1回のあと1度も通らず、100000 を表示します。
Answer
Wrong
tokens = std::min(1L, tokens + (now_ms - last_ms) / 1000);
last_ms = now_ms;
(now_ms - last_ms) / 1000 は整数の割り算なので、1000 ミリ秒に満たない経過時間は 0 個の補充になります。そのすぐあとに last_ms = now_ms; で前回の時刻を今に進めるので、補充に数えなかった 700 ミリ秒は捨てられます。時刻 700 の呼び出しは 700 ミリ秒を捨て、時刻 1400 の呼び出しも、前回の 700 からの 700 ミリ秒を 0 個と数えて捨てます。要求が 1000 ミリ秒より短い間隔で来るかぎり、経過時間は毎回 700 ミリ秒から積み上がらず、トークンは二度と補充されません。
切り捨てだけなら端数が少し遅れるだけで、時刻を進めるだけなら補充の量は正しく数えられます。2つが同じ呼び出しで重なったとき、捨てた端数が次の呼び出しに持ち越されなくなります。割り算を切り上げに変えると、700 ミリ秒ごとに1つ補充されて 111111 となり、今度は1秒に1つの制限を超えて通してしまいます。
Right
long refill = (now_ms - last_ms) / 1000;
tokens = std::min(1L, tokens + refill);
last_ms += refill * 1000;
last_ms は、補充に数えた時間の分だけ、つまり refill * 1000 ミリ秒だけ進めます。数えなかった端数は now_ms - last_ms に残り、次の呼び出しの経過時間に加わります。時刻 1400 では 1400 ミリ秒から1つ補充して last_ms を 1000 にし、時刻 2100 では 1000 からの 1100 ミリ秒でまた1つ補充します。時刻 2800 では 2000 からの 800 ミリ秒で補充は無く、時刻 3500 で 3000 の分が補充されるので、101101 になります。
トークンが上限の1つにたまっているときも last_ms は同じだけ進むので、使われなかった時間の分が後からまとめて補充されることはありません。last_ms と now_ms の差はいつも 1000 ミリ秒未満に保たれます。