正文前的扯淡

Python作为一门动态语言被许多人诟病速度慢。这虽然是事实，但是作为一个开发应该问问自己是否在代码中使用了合适的数据结构和算法。举个基本的例子：Python内置的数据类型list和tuple的数据结构是线性表，对线性表做一些插入操作时间复杂度显然比链表要高。那么，Python有没有给我们提供链表这样的数据结构呢？显然是有的...Python的标准库里内置了各种算法和数据结构供开发使用，使用这些标准库可以大大简化编程工作，下面我们来看一些常用的数据结构和算法。

双向队列

库：collections模块中的deque类
介绍：这是一种数据结构是链表的双向队列，从该队列的头部或尾部插入或者删除一个元素，时间复杂度是O(1).
用途：可以用来表示先进先出的队列(FIFO).

有序字典

库：collections模块中的OrderedDict类
介绍：一种特殊的字典，能够按照键的插入顺序保留键值对在字典中的次序。
用途：Python默认提供的dict是没有顺序的，如果在拥有相同键值对的两个dict上面迭代，可能就会出现不同的迭代顺序，让我们看个例子：

d = {}
d['a'] = 'A'
d['b'] = 'B'
d['c'] = 'C'
d['d'] = 'D'
d['e'] = 'E'
for k, v in d.items():
    print k, v
在Python2环境下，输出结果如下：
a A
c C
b B
e E
d D

之所以出现这样的现象，是因为它是由快速哈希表实现的。
在OrderedDict上面根据键来迭代，其行为是确定的。这种确定的行为，可以极大简化测试与调试工作。使用示例如下：

from collections import OrderedDict
In [8]: a = OrderedDict()

In [9]: a['foo'] = 1

In [10]: a['bar'] = 2

In [11]: b = OrderedDict()

In [12]: b['foo'] = 'red'

In [13]: b['bar'] = 'blue'

In [14]: for v1, v2 in zip(a.values(), b.values()):
    ...:     print v1, v2

1 red
2 blue

有默认值的字典

库：collections模块中的defaultdict类
介绍：带有计数器功能的字典
用途：Python默认的字典可以用来保存并记录一些统计数据。但是，由于字典里面未必有我们要查询的那个键，当使用字典保存计数器的时候，就必须要用稍微麻烦一些的方式，才能实现简单的功能。
比如，如果我们要实现一个计数器，需要这样做：

stats = {}
key = 'my_counter'
if key not in stats:
   stats[key] = 0
stats[key] += 1

但是有了默认值字典，我们直接这样做就可以：

from collections import defaultdict
stats = defaultdict(int)
stats['my_counter'] += 1

如果字典中没有待访问的键，那么defaultdict就会把某个默认值和这个键自动关联起来。所以，我们只需要提供返回默认值的函数即可，字典中会用该函数为每一个默认的键指定默认值(本例中，我们是用int函数来创建字典的，这使该字典能够以0作为默认值)。

堆队列

库：heapq
介绍：一种适合实现优先级队列的数据结构
用途：从1亿个数里面找出最大或最小的100个数
(不了解堆的实现方式的读者可以看这篇文章:堆排序的Python实现(附详细过程图和讲解))

import heapq
nums = [randint(1, 1000) for x in range(100)]
print heapq.nlargest(3, nums)
print heapq.nsmallest(3, nums)

二分查找

库：bisect
介绍：一种高效的二分折半搜索算法
用途：在List上用Index来查找某个元素，所消耗的时间会与列表长度呈线性比例。而bisect提供的bisect_left等函数，使用了二分折半搜索算法，能够在排序之后的元素中查找某个值，由bisect_left函数所返回的索引，表示待搜索的值在序列中的插入点。

import bisect
x = list(range(10**6))
i = x.index(999969)
i = bisect.bisect_left(x, 991234)

二分查找法的复杂度是对数级别的。也就是说，用bisect搜索100,000个元素的列表，与用index搜索14个元素的列表用的时间差不多。