[解決済み] 良いレートリミッターアルゴリズムとは？

質問

疑似コード、もしくはPythonがあればより良いのですが。 私は Python IRC ボットにレート制限キューを実装しようとしています。部分的には動作しますが、誰かが制限より少ないメッセージをトリガーし（例えば、レート制限は8秒間に5メッセージで、その人は4しかトリガーしない）、次のトリガーが8秒を超えた場合（例えば、16秒後）、ボットはメッセージを送信しますが、キューがいっぱいになり、8秒が経過したので必要ないにもかかわらずボットは8秒待機します。

解決するには？

ここで 最もシンプルなアルゴリズム もし、メッセージがあまりに早く到着したときに、単にメッセージを削除したい場合（キューに入れるのではなく、キューが恣意的に大きくなる可能性があるため、理にかなっています）。

rate = 5.0; // unit: messages
per  = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
  current = now();
  time_passed = current - last_check;
  last_check = current;
  allowance += time_passed * (rate / per);
  if (allowance > rate):
    allowance = rate; // throttle
  if (allowance < 1.0):
    discard_message();
  else:
    forward_message();
    allowance -= 1.0;

このソリューションには、データ構造、タイマーなどはなく、きれいに動作します :) これを見るために、'allowance' は最大で毎秒5/8ユニット、つまり8秒間に最大5ユニットの速度で成長する。転送されたメッセージは1個ずつ減算されるので、8秒間に5個以上のメッセージを送信することはできません。

なお rate は整数でなければなりません。つまり、小数点以下が0でないものでなければ、アルゴリズムは正しく動作しません（実際のレートは rate/per ). 例 rate=0.5; per=1.0; は機能しません。 allowance は1.0まで成長することはないでしょう。しかし rate=1.0; per=2.0; は正常に動作します。