优先级队列

前言

这两天在看python cook这本书学习到了一个heapq类,它的底层会将给的容器参数进行堆排序放到一个列表中;并提供了一个优先级队列.我觉得后面做并发可以用来做请求的削峰所以在此记录一下.

heapq类的特性

# 定义一个无序的列表
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
# 引入heapq类,并将nums转化为一个heapq对象
import heapq
heap = list(nums)
heapq.heapify(heap)
print(heap) # [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]

堆数据结构最重要的特征是 heap[0] 永远是最小的元素。并且剩余的元素可以很
容易的通过调用 heapq.heappop() 方法得到，该方法会先将第一个元素弹出来，然后
用下一个最小的元素来取代被弹出元素（这种操作时间复杂度仅仅是 O(log N)， N 是
堆大小）

# 从heap中获取一个元素
print(heapq.heappop(heap)) # -4
print(heap)# [1,2, 23, 7, 2, 18, 23, 42, 37, 8]

通过heappop方法取出最小的元素后,依据堆排序特性heap[0]还是最小的元素.

# 定义一个元素为序列的deapq对象
tuples = []
heapq.heappush(tuples, (1, "a", "a"))
heapq.heappush(tuples, (2,"b","a"))
heapq.heappush(tuples, (2,"a","a"))
print(tuples) # [(1,"a","a"), (2,"b","a")),(2,"a","a")]
print(heapq.heappop(tuples)) # (1, "a", "a")
print(tuples) # [(2,"a","a"), (2,"b","a"))]

这里使用了先创建一个空的列表，然后使用heappush方法写入值生成deapq对象.
其中的元素是元组对象,同样的在heappop执行之后序列进行了一次排序，这里在元组第一个元素相同的情况下对比了第二个元素。这就是heap针对元素为序列时的排序规则

优先级队列

import heapq
# 优先级队列类
class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0
  def push(self, item, priority):
    # 最高优先级是5,加负号将其放到队头.
    # 元组的第二个元素是当前元素的在队列中的下标,优先级相同先入队的先执行,
    # 同时也避免撞到不能进行比较的对象报错.
    heapq.heappush(self._queue, (-priority, self._index, item))
    self._index += 1
  def pop(self):
    return heapq.heappop(self._queue)[-1]

#测试元素类
class Item:
  def __init__(self, name):
    self.name = name
  def __repr__(self):
    return 'Item({!r})'.format(self.name)

if __name__ == "__main__":
  q = PriorityQueue()
  q.push(Item('foo'), 1)
  q.push(Item('bar'), 5)
  q.push(Item('spam'), 4)
  q.push(Item('grok'), 1)
  q.pop() #Item('bar')
  q.pop() #Item('spam')
  q.pop() #Item('foo')
  q.pop() #Item('grok')

写在后面

当前仅完成了一个优先级的队列模型暂时还不能用于并发削峰有几个问题需要解决.
1.在请求分发到多个线程时必须要保证他们使用同一个优先级队列削峰这个时候就要考虑线程同步，需要加锁或信号量方案解决
2.数据的事务管理和请求的上下文管理
后面做完调研再来补充