什么是好的速率限制算法？
我可以使用一些伪代码，或者更好的Python。我正在尝试为Python IRC机器人实现一个速率限制队列，它部分工作，但是如果有人触发的消息少于限制(例如，速率限制是每8秒5条消息，而人只触发4条)，并且下一个触发器超过8秒(例如，16秒后)，机器人发送消息，但是队列变满，机器人等待8秒，即使由于8秒周期已经过去而不需要它。
回答 9
Stack Overflow用户
发布于 2009-03-20 23:15:27
这里是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个单位。每转发一条消息就会扣除一个单位，因此每8秒发送的消息不能超过5条。
请注意，rate应该是一个整数，即没有非零的小数部分，否则算法将无法正常工作(实际的速率不会是rate/per)。例如，因为allowance永远不会增长到1.0，所以rate=0.5; per=1.0;无法工作。但是rate=1.0; per=2.0;运行得很好。
Stack Overflow用户
发布于 2009-03-20 19:51:44
在你的入队函数之前使用这个装饰符@RateLimited(ratepersec)。
基本上，这会检查自上次以来是否经过了1/rate秒，如果没有，则等待剩余时间，否则不等待。这实际上将您限制为速率/秒。装饰器可以应用于任何你想要的速率限制的函数。
在您的示例中，如果您希望每8秒最多发送5条消息，请在sendToQueue函数之前使用@RateLimited(0.625)。
import time
def RateLimited(maxPerSecond):
minInterval = 1.0 / float(maxPerSecond)
def decorate(func):
lastTimeCalled = [0.0]
def rateLimitedFunction(*args,**kargs):
elapsed = time.clock() - lastTimeCalled[0]
leftToWait = minInterval - elapsed
if leftToWait>0:
time.sleep(leftToWait)
ret = func(*args,**kargs)
lastTimeCalled[0] = time.clock()
return ret
return rateLimitedFunction
return decorate
@RateLimited(2) # 2 per second at most
def PrintNumber(num):
print num
if __name__ == "__main__":
print "This should print 1,2,3... at about 2 per second."
for i in range(1,100):
PrintNumber(i)Stack Overflow用户
发布于 2011-06-21 01:39:35
为了阻塞处理，直到可以发送消息，从而使更多的消息排队，antti的漂亮解决方案也可以像这样修改：
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):
time.sleep( (1-allowance) * (per/rate))
forward_message();
allowance = 0.0;
else:
forward_message();
allowance -= 1.0;它只是等待，直到有足够的余量来发送消息。为了不以两倍的速率开始，容差也可以初始化为0。
https://stackoverflow.com/questions/667508
复制相似问题
腾讯云开发者
