Question

在解决性能问题的时候，如果已经到了非改代码不可的情况，考虑到Python中的查找、排序常用算法都已经优化到极点（虽然对sort()使用key参数比使用cmp参数有更高的性能仍然值得一提），那么首先应当想到的是使用不同的数据结构优化性能。

首先来看最常用的数据结构——list，它的内存管理类似C++的std::vector，即先预分配一定数量的“车位”，当预分配的内存用完时，又继续往里插入元素，就会启动新一轮的内存分配。list对象会根据内存增长算法申请一块更大的内存，然后将原有的所有元素拷贝过去，销毁之前的内存，再插入新元素。当删除元素时，也是类似，删除后发现已用空间比预分配空间的一半还少时，list会另外申请一块小内存，再做一次元素拷贝，然后销毁原有的大内存。可见，如果list对象经常有元素数量的“巨变”，比如膨胀、收缩得很频繁，那么应当考虑使用deque。

deque就是双端队列，同时具备栈和队列的特性，能够提供在两端插入和删除时复杂度为O(1)的操作。相对于list，它最大的优势在于内存管理方面。如果不熟悉C++的std::deque，那么可以把deque想象为多个list连在一起（仅为比喻，非精确描述），“像火车一样，每一节车厢可以载客”，它的每一个“list”也可以存储多个元素。它的优势在插入时，已有空间已经用完，那么它会申请一个“车厢”来容纳新的元素，并将其与已有的其他“车厢”串接起来，从而避免元素拷贝；在删除元素时也类似，某个“车厢”空了，就“丢弃”掉，无需移动元素。所以当出现元素数量“巨变”时，它的性能比list要好上许多倍。

对于list这种序列容器来说，除了pop(0)和insert(0，v)这种插入操作非常耗时之外，查找一元素是否在其中，也是O(n)的线性复杂度。在C语言中，标准库函数bsearch()能够通过二分查找算法在有序队列中快速查找是否存在某一元素。在Python中，对保持list对象有序以及在有序队列中查找元素有非常好的支持，这是通过标准库bisect来实现的。

bisect并没有实现一种新的“数据结构”，其实它是用来维护“有序列表”的一组函数，可以兼容所有能够随机存取的序列容器，比如list。它可使在有序列表中查找某一元素变得非常简单。

def index(a, x):
  i = bisect_left(a, x)
  if i != len(a) and a[i] == x:
    return i
  raise ValueError

保持列表有序需要付出额外的维护工作，但如果业务需要在元素较多的列表中频繁查找某些元素是否存在或者需要频繁地有序访问这些元素，使用bisect则相当值得。

对于序列容器，除了插入、删除、查找之外，还有一种很常见的需求是就获取其中的极大值或极小值元素，比如在查找最短路径的A*算法中就需要在Open表中快速找到预估值最小的元素。这时候，可以使用heapq模块。类似bisect，heapq也是维护列表的一组函数，其中最先接触的必然是heapify()，它的作用是把一个序列容器转化为一个堆。

>>> import heapq
>>> import random
>>> alist = [random.randint(0, 100) for i in xrange(10)]
>>> alist
[59, 62, 38, 18, 26, 92, 9, 57, 52, 97]
>>> heapq.heapify(alist)
>>> alist
[9, 18, 38, 52, 26, 92, 59, 57, 62, 97]

可以看到转化为堆后，alist的第一个元素alist[0]是整个列表中最小的元素，heapq将保证这一点，从而保证从列表中获取最小值元素的时间复杂度是O(1)。

>>> heapq.heappop(alist)
9
>>> alist
[18, 26, 38, 52, 97, 92, 59, 57, 62]

除了通过heapify()函数将一个列表转换为堆之外，也可以通过heappush()、heappop()函数插入、删除元素，针对常见的先插入新元素再获取最小元素、先获取最小元素再插入新元素的需求，还有heappushpop(heap，item)和heapreplace(heap,item)函数可以快速完成。从上例可以看出，每次元素增减之后序列的变化都很大，可以想象维护堆结构需要付出许多额外计算，所以千万不要“提前优化”乱用heapq，以免带来性能问题。

除此之前，heapq还有3个通用函数值得介绍，其中merge()能够把多个有序列表归并为一个有序列表（返回迭代器，不占用内存），而nlargest()和nsmallest()类似于C++中的std::nth_element()，能够返回无序列表中最大或最小的n个元素，并且性能比sorted(iterable,key=key)[:n]要高。

除了对容器的操作可能会出现性能问题外，容器中存储的元素也有很大的优化空间，这是因为在很多业务中，容器存储的元素往往是同一类型的，比如都是整数，而且整数的取值范围也确定，那么就可以使用array优化程序性能。

array实例化的时候需要指定其存储的元素类型，如'c'，表示存储的每个人元素都相当于C语言中的char类型，占用内存大小为1字节。

>>> import array
>>> a = array.array('c', 'string')
>>> a
array('c', 'string')
>>> a[0] = 'c'
>>> print a
array('c', 'ctring')

从上例可以看出，array对象与str不同，它是可变对象，可以随意修改某一元素的值。不过它最大的优势在于更小的内容占用。

>>> import sys
>>> a
array('c', 'ctring')
>>> sys.getsizeof(a)
62L
>>> l = list('cstring')
>>> sys.getsizeof(l)
152

看，内存占用只有使用了list的40%左右，这个优化效果在元素数量巨大的时候会更加明显。此外，还有性能方面的提升。

>>> t = timeit.Timer("''.join(a)", "a = list('cstring')")
>>> t.timeit()
0.21462702751159668
>>> t = timeit.Timer("a.tostring()", "import array;a=array.array('c','cstring')")
>>> t.timeit()
0.1419069766998291

从容器到字符串的转变可以看出array的性能提升是比较大的，但也不能认为array在什么方面都有更好的性能。

>>> t = timeit.Timer("a.reverse()", "import array;a=array.array('c', 'cstring')")
>>> t.timeit()
0.15056395530700684
>>> t = timeit.Timer("a.reverse()", "a = list('cstring')")
>>> t.timeit()
0.08988785743713379

看，在这里list的性能要好些。所以性能优化一定要根据profiler的剖析结果来进行，经验往往靠不住，这和“不要提前优化”一样是性能优化的基本原则。