我可以使用一些伪代码,或者更好的 Python。我正在尝试为 Python IRC 机器人实现一个限速队列,它可以部分工作,但是如果有人触发的消息少于限制(例如,速率限制是每 8 秒 5 条消息,而这个人只触发 4 条),并且下一次触发超过 8 秒(例如,16 秒后),机器人发送消息,但队列已满,机器人等待 8 秒,即使由于 8 秒的时间已经过去,不需要它。
最佳答案
这里是 simplest algorithm ,如果您只想在消息到达过快时丢弃消息(而不是排队,这是有道理的,因为队列可能会变得任意大):
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;
此解决方案中没有数据结构、计时器等,它运行良好 :) 看到这一点,“津贴”最多以每秒 5/8 个单位的速度增长,即每八秒最多五个单位。转发的每条消息都会扣除一个单位,因此每 8 秒发送的消息不能超过 5 条。
注意 rate
应该是一个整数,即没有非零小数部分,否则算法将无法正常工作(实际速率不会是 rate/per
)。例如。 速率=0.5; per=1.0;
不起作用,因为 allowance
永远不会增长到 1.0。但是 rate=1.0; per=2.0;
工作正常。
https://stackoverflow.com/questions/667508/