首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >什么是好的速率限制算法?

什么是好的速率限制算法?
EN

Stack Overflow用户
提问于 2009-03-20 19:02:28
回答 9查看 105.6K关注 0票数 172

我可以使用一些伪代码,或者更好的Python。我正在尝试为Python IRC机器人实现一个速率限制队列,它部分工作,但是如果有人触发的消息少于限制(例如,速率限制是每8秒5条消息,而人只触发4条),并且下一个触发器超过8秒(例如,16秒后),机器人发送消息,但是队列变满,机器人等待8秒,即使由于8秒周期已经过去而不需要它。

EN

回答 9

Stack Overflow用户

回答已采纳

发布于 2009-03-20 23:15:27

这里是simplest algorithm,如果您只想在消息到达太快时丢弃它们(而不是对它们进行排队,这是有意义的,因为队列可能会变得任意大):

代码语言:javascript
复制
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;运行得很好。

票数 259
EN

Stack Overflow用户

发布于 2009-03-20 19:51:44

在你的入队函数之前使用这个装饰符@RateLimited(ratepersec)。

基本上,这会检查自上次以来是否经过了1/rate秒,如果没有,则等待剩余时间,否则不等待。这实际上将您限制为速率/秒。装饰器可以应用于任何你想要的速率限制的函数。

在您的示例中,如果您希望每8秒最多发送5条消息,请在sendToQueue函数之前使用@RateLimited(0.625)。

代码语言:javascript
复制
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)
票数 52
EN

Stack Overflow用户

发布于 2011-06-21 01:39:35

为了阻塞处理,直到可以发送消息,从而使更多的消息排队,antti的漂亮解决方案也可以像这样修改:

代码语言:javascript
复制
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。

票数 12
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/667508

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档