3.Heapq
heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表，并且置入了堆的相关规则。
堆是一种树形的数据结构，树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识，在这种结构中，元素N的子节点的序号为2*N+1和2*N+2(下标始于0)。简单来说，这个模块中的所有函数都假设序列是有序的，所以序列中的第一个元素(seq[0])是最小的，序列的其他部分构成一个二叉树，并且seq[i]节点的子节点分别为seq[2*i+1]以及seq[2*i+2]。当对序列进行修改时，相关函数总是确保子节点大于等于父节点。
import heapq
heap = []
for value in [20, 10, 30, 50, 40]:
heapq.heappush(heap, value)
while heap:
print heapq.heappop(heap)
heapq模块有两个函数nlargest()和nsmallest()，顾名思义，让我们来看看它们的用法。
import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]
两个函数也能够通过一个键参数使用更为复杂的数据结构，例如：
import heapq
portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
print cheap
# [{'price': 16.35, 'name': 'YHOO', 'shares': 45},
# {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]
print expensive
# [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME',
# 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]
来看看如何实现一个根据给定优先级进行排序，并且每次pop操作都返回优先级最高的元素的队列例子。
import heapq
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)
print q.pop() # Item('bar')
print q.pop() # Item('spam')
print q.pop() # Item('foo')
print q.pop() # Item('grok')
4. Bisect
bisect模块能够提供保持list元素序列的支持。它使用了二分法完成大部分的工作。它在向一个list插入元素的同时维持list是有序的。在某些情况下，这比重复的对一个list进行排序更为高效，并且对于一个较大的list来说，对每步操作维持其有序也比对其排序要高效。
假设你有一个range集合：
a = [(0, 100), (150, 220), (500, 1000)]
如果我想添加一个range (250, 400)，我可能会这么做：
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
我们可以使用bisect()函数来寻找插入点：
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399, 450))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
print bisect.bisect(a, (550, 1200)) # 5
bisect(sequence, item) => index 返回元素应该的插入点，但序列并不被修改。
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399, 450))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
print bisect.bisect(a, (550, 1200)) # 5
bisect.insort_right(a, (550, 1200))
print a # [(0, 100), (150, 220), (250, 400), (399, 450), (500, 1000), (550, 1200)]
新元素被插入到第5的位置。
5. Weakref
weakref模块能够帮助我们创建Python引用，却不会阻止对象的销毁操作。这一节包含了weak reference的基本用法，并且引入一个代理类。
在开始之前，我们需要明白什么是strong reference。strong reference是一个对对象的引用次数、生命周期以及销毁时机产生影响的指针。strong reference如你所见，就是当你将一个对象赋值给一个变量的时候产生的：
>>> a = [1,2,3]
>>> b = a
在这种情况下，这个列表有两个strong reference，分别是a和b。在这两个引用都被释放之前，这个list不会被销毁。
class Foo(object):
def __init__(self):
self.obj = None
print 'created'
def __del__(self):
print 'destroyed'
def show(self):
print self.obj
def store(self, obj):
self.obj = obj
a = Foo() # created
b = a
del a
del b # destroyed
Weak reference则是对对象的引用计数器不会产生影响。当一个对象存在weak reference时，并不会影响对象的撤销。这就说，如果一个对象仅剩下weak reference，那么它将会被销毁。
你可以使用weakref.ref函数来创建对象的weak reference。这个函数调用需要将一个strong reference作为第一个参数传给函数，并且返回一个weak reference。
>>> import weakref
>>> a = Foo()
created
>>> b = weakref.ref(a)
>>> b
一个临时的strong reference可以从weak reference中创建，即是下例中的b()：
>>> a == b()
True
>>> b().show()
None
请注意当我们删除strong reference的时候，对象将立即被销毁。
>>> del a
destroyed
如果试图在对象被摧毁之后通过weak reference使用对象，则会返回None：
>>> b() is None
True
若是使用weakref.proxy，就能提供相对于weakref.ref更透明的可选操作。同样是使用一个strong reference作为第一个参数并且返回一个weak reference，proxy更像是一个strong reference，但当对象不存在时会抛出异常。
>>> a = Foo()
created
>>> b = weakref.proxy(a)
>>> b.store('fish')
>>> b.show()
fish
>>> del a
destroyed
>>> b.show()
Traceback (most recent call last):
File "", line 1, in ?
ReferenceError: weakly-referenced object no longer exists
完整的例子：
引用计数器是由Python的垃圾回收器使用的，当一个对象的应用计数器变为0，则其将会被垃圾回收器回收。
最好将weak reference用于开销较大的对象，或避免循环引用(虽然垃圾回收器经常干这种事情)。
import weakref
import gc
class MyObject(object):
def my_method(self):
print 'my_method was called!'
obj = MyObject()
r = weakref.ref(obj)
gc.collect()
assert r() is obj #r() allows you to access the object referenced: it's there.
obj = 1 #Let's change what obj references to
gc.collect()
assert r() is None #There is no object left: it was gc'ed.
提示：只有library模块中定义的class instances、functions、methods、sets、frozen sets、files、generators、type objects和certain object types(例如sockets、arrays和regular expression patterns)支持weakref。内建函数以及大部分内建类型如lists、dictionaries、strings和numbers则不支持。
