什么是好的限速算法?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (19)

我正在尝试为Python IRC bot实现一个速率限制队列,它部分工作,但如果有人触发的消息少于限制(例如,速率限制为每8秒5条消息,而Person只触发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;

在这个解决方案中没有数据结构、定时器等,它工作得很干净:)要看到这一点,“允许”最多以每秒5/8单位的速度增长,即最多每8秒增加5个单位。转发的每条消息都会扣除一个单元,因此每8秒不能发送超过5条消息。

请注意rate应该是整数,即不包含非零小数部分,否则算法将不能正常工作(实际速率将不正确)。rate/per)。例如:rate=0.5; per=1.0;不起作用是因为allowance永远不会增长到1.0。但rate=1.0; per=2.0;效果很好。

用户回答回答于

在函数队列之前使用这个装饰器@RateLimited(Ratepersec)。

基本上,这将检查1/费率秒是否从上次通过,如果没有,则等待其余时间,否则不会等待。这实际上限制了速率/秒。该装饰器可以应用于任何想要的功能,速率限制。

情况下,如果希望每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)

扫码关注云+社区