From: http://www.mitbbs.com/article_t/JobHunting/33166641.html

设计一个数据结构使得一个request在1秒之内只能执行50次。

面试官提示说如果要支持request limit为1million的话，用任何数据结构存timestamp
都会导致占用内存。他想要O(1)空间复杂度的解法。我想了很久都没有想到。。

发信人: robustray (robust), 信区: JobHunting
标  题: Re: 问个Google的面试题
发信站: BBS 未名空间站 (Sun Apr  3 16:03:47 2016, 美东)

这题不需要开array或者queue，只要维护counter和last seconds就可以了，确实是O(1
)的。

See: http://stackoverflow.com/questions/667508/whats-a-good-rate-limiting-algorithm about Rate Limiter.

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;


There are no datastructures, timers etc. in this solution and it works cleanly :) To see this, 'allowance' grows at speed 5/8 units per seconds at most, i.e. at most five units per eight seconds. Every message that is forwarded deducts one unit, so you can't send more than five messages per every eight seconds.

Note that rate should be an integer, i.e. without non-zero decimal part, or the algorithm won't work correctly (actual rate will not be rate/per). E.g. rate=0.5; per=1.0; does not work because allowance will never grow to 1.0. But rate=1.0; per=2.0; works fine.

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)

Guaua Rate Limiter:

- http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/util/concurrent/RateLimiter.html
- http://www.nurkiewicz.com/2012/09/ratelimiter-discovering-google-guava.html
- http://stackoverflow.com/questions/27711962/guava-s-ratelimiter-per-minutes-instead-of-seconds