Rate limiter （请求速率限制问题）

http://blog.gssxgss.me/not-a-simple-problem-rate-limiting/

The solution is Token Bucket.
Token Bucket is a bucket which has a fixed capacity. We put tokens into the token with a fixed rate. When a request comes, if there is no token in the bucket, the request will be denied. Otherwise, the request will be approved and the number of tokens in the bucket decrease by one.


static class TokenBucket {

  private final int capacity;
  private final int tokensPerSeconds;
  private int tokens = 0;
  private long timestamp = System.currentTimeMillis();

  public TokenBucket(int tokensPerUnit, TimeUnit unit) {
    //set capacity and rate
    capacity = tokensPerSeconds = (int) (tokensPerUnit / unit.toSeconds(1L));
  }

  public boolean take() {
    //calc the # of tokens added into bucket since last request time
    long now = System.currentTimeMillis();
    tokens += (int) ((now - timestamp) * tokensPerSeconds / 1000);
 
    //cannot overflow the capacity
    if (tokens > capacity) tokens = capacity;
 
    //if no token, won't reply to the request
    if (tokens < 1) return false;
    //if having enough token, reply
    else{
         timestamp = now;
         tokens--;
         return true;
    }
  }

}

public static void main(String[] args) throws InterruptedException {
  TokenBucket bucket = new TokenBucket(250, TimeUnit.MINUTES);
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
  Thread.sleep(1000L);
  for (int i = 0; i < 5; i++) {
    System.out.println(bucket.take());
  }
}

Introduction to basic collections in Python

In this post, we will introduce operations of basic collections (list, array, stack, dequeue, queue, priority queue (heap), set and dictionary) in Python.

-------------------------------------------------------------------------------------------------------

list,array,stack

初始化        

    []

    [1,"a","cde"]

    array         [0]*5     ----> generate [0,0,0,0,0]

    fake matrix        [[0]*5]*6 

                        ----> generate [0]5*6    ----->但是又一个问题：[0]*5生成了一个list，是一个引用，这个引用*6，即会产生六个相同的引用，改变其中任意一个，会相应的改变其他5个。因而这个方法并不适合残生matrix

    matrix        list comprehension: ＊＊＊＊＊是一个创建新list的操作＊＊＊＊＊

        pattern: 生成一个新的值＋for循环

        e.g., [0]*5 for i in range(6)

增    

    增一个元素：    append(elem)

                insert(index, elelm)

    增加一整个collection中的元素    x=y+z (y,z are lists) or y.extend(z)

删

    pop():删除最后一个元素

    pop(index): 删除第i个元素

    remove(elem): 删除第一个elem

查

    if elem in list:查是否有

    list.index(elem):返回elem的index

    list.count(elem):返回elem的个数

    list[-1], list[3:]

改

    list[index] = A: 改某一个特定的index的元素

    list = [1,2,3]

    list1 = [10 if elem==2 else elem for elem in list]

    list comprehension: 

        轻量级循环，压缩for if else

copy

    y = x 拷贝，如果改变y中的元素，也会改变x中的元素

    y = x[:] 拷贝，如果改变y中immutable的元素，不会改变x中对应的immutable的元素。但是如果改变y中mutable的元素，也会改变x中mutable的元素

reoder:

    sort

        针对tuple的情况：

            list.sort(key=lambda x:x[1]) lambda是函数入口，reverse默认是False，从小到大

        e.g.,

            list = [('a',1), ('b',3), ('c',2)]

            list.sort(key=lambda x:x[1], reverse=True)

        针对self-define class, 传入cmp function

        e.g.,

            def cmp(x1, x2):

                ......

            list.sort(cmp)

    reverse

global的方法

    sorted(list)

    max(list)

    min(list)

    len(list)

    sum(list)

Iterable and Iterator

Iteratble and Iterator 都有 __iter__ 方法。该方法会在for循环中指向下一个元素

Iterator 有next方法

String, List, Tuple, Dictionary 都是Iterable的

-------------------------------------------------------------------------------------------------------

dequeue

初始化

    from collections import deque

    x = deque([])

增

    入队一个元素

    x.append(elem): append the element into the queue

    x.appendleft(elem): prepend the element

删

    出队一个元素    

    x.pop(): pop the last element

    x.popleft(): pop the first element

查

    查top元素

    x[0]

    x[-1]

改

    不存在

list不能同时实现 O(1)的pop() 和 O(1)的append(elem)

因为如果是用     insert(0, elem)和pop(), insert 是O(n)  

            append(elem), pop(0), pop(0) 是O(n)

-------------------------------------------------------------------------------------------------------

priority queue (heap)

1.heapq

初始化

    []: 如果是空，则可以直接用列表的形式

    heapq.heapify([1,2,3])，如果不为空，必须放在heapify里面

增

    heapq.heappush(heap, elem)

删

    heapq.heappop(heap)

if elem自定义了__cmp__方法，则heapq会调用__cmp__来进行排序

else if elem是一个tuple，会根据tuple的第一个元素来进行排序

默认是从小到大排序，如果想要从大到小排序，对值取负

2.Queue.PriorityQueue

-------------------------------------------------------------------------------------------------------

set

初始化

    set(Iterable)

    e.g., set([1,2,3]), set("abc") = set(['a', 'c', 'b']), set(["a":1, "b":2, "c":3]) = set(['a', 'c', 'b'])

增     add()

删     remove(): raise Exception if not exists

    discard(): won't raise Exception

查    x in set

-------------------------------------------------------------------------------------------------------

dictionary

mutable类型的变量不能作为dictionary的key值

if表达中会导致True，False的变量，如None，空字符串 “”