使用内置数据结构和算法        

        当你实现非常小的的Python程序时，你可能会看到由你的代码的算法复杂性而造成的减速。 这个通常不是Python语言本身速度的造成，这更有可能是因为没有为您的问题使用最好的算法和数据结构。幸运的是Python标准库有许多内置的算法和数据结构可以使用。除了速度，使用这些常用的算法和数据结构可以让你的生活更轻松。 你可能想使用的一些更有力的工具，这是一个棘手的问题。 避免重新实现常用功能将会节省您的时间。

        Double-ended Queue（双端队列）

        deque类是在collections模块中，它是一个double-ended队列。从deque队列开始或者结尾，插入或者删除会花费相同的时间。这个使其成为先进先出（FIFO）队列的理想选择。

fifo = deque()fifo.append(1) # Producerx = fifo.popleft() # Consumer

内置List也可以实现有序队列，如fifo。但内置List从列表头部的插入或删除项，花费时间是线性的，这比常数慢得多。

        Ordered Dictionary（有序字典）

        标准字典是无序的。 这意味着具有相同的键和值的dict可以有不同的迭代次序。 这种行为有一个令人惊讶的副产品就是实现字典的快速哈希表。

a = {}a['foo'] = 1a['bar'] = 2# Randomly populate ‘b’ to cause hash conflictswhile True:z = randint(99, 1013)b = {}for i in range(z):b[i] = ib['foo'] = 1b['bar'] = 2for i in range(z):del b[i]if str(b) != str(a):breakprint(a)print(b)print('Equal?', a == b)>>>{'foo': 1, 'bar': 2}{'bar': 2, 'foo': 1}Equal? True

        collections模块中的OrderedDict类是一种特殊类型的字典，它跟踪其键的插入顺序。 迭代键OrderedDict具有可预测的行为。 这可以大大简化测试和调试通过使所有代码确定性。

a = OrderedDict()a['foo'] = 1a['bar'] = 2b = OrderedDict()b['foo'] = 'red'b['bar'] = 'blue'for value1, value2 in zip(a.values(), b.values()):print(value1, value2)>>>1 red2 blue

        Default Dictionary

        字典对记账和跟踪统计非常有用。内建的字典类型是不能假设任何键已经存在。 这使得它做一些简单的事情时显得笨拙，如增加一个存储在字典中的计数器。

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

collections模块中的defaultdict类简化了当key不存在时自动存储默认值。 所有你需要做的是提供每次键丢失时将返回默认值的函数。 在这里例如，int内置函数返回0现在，递增计数器是

简单。int()->0

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

        Heap Queue

   关于这里，heap这种数据结构的介绍有一个简单的blog可以去看一下http://blog.csdn.net/minxihou/article/details/51857518 堆是用于维护优先级队列的有用数据结构。 heapq模块提供了在标准list类型中创建堆的功能使用函数heappush，heappop和nsmallest等函数。任何优先级的项可以按任何顺序插入堆中。

a = []heappush(a, 5)heappush(a, 3)heappush(a, 7)heappush(a, 4)

总是先移除最高优先级(lowest number)的项.

print(heappop(a), heappop(a), heappop(a), heappop(a))>>>3 4 5 7

生成的list在heapq之外很容易使用。 访问堆的0索引将总是返回最小的项。

a = []heappush(a, 5)heappush(a, 3)heappush(a, 7)heappush(a, 4)assert a[0] == nsmallest(1, a)[0] == 3

list的sort方法保持不变。

print('Before:', a)a.sort()print('After:' , a)>>>Before: [3, 4, 7, 5]After: [3, 4, 5, 7]

        Bisection

        调用index方法查找列表中的项需要花费与list长度成线性比例的时间。

x = list(range(10**6))i = x.index(991234)

使用bisect模块的方法，如：bisect_left,是使用二分查找的方法。它返回的索引是插入点值插入序列。

i = bisect_left(x, 991234)

二分搜索的复杂度是对数的。 这意味着使用bisect搜索100万个项的list的速度是使用线性索引方式搜索的14倍。It’s way faster!

        Iterator Tools

        tertools内置模块包含大量有用与迭代器相关的函数。不是所有这些都在Python 2中可用，但它们可以轻松地使用通过查看模块中记录的simple recipes。 请参阅help（itertools）获得更多详细信息。 itertools中的函数主要分为三类：     Linking iterators together         •chain：将多个迭代器组合成一个顺序迭代器。         •cycle：一直重复迭代器的项。         •tee：将单个迭代器拆分为多个并行迭代器。         •zip_longest：内置zip函数的变体，当迭代的几个对象长度不同的时候有更好的表现。     Filtering items from an iterator         •islice：通过数字索引切片迭代器，而不进行复制。         •takewhile：当断言函数返回Ture时返回迭代器中的项。         •dropwhile：当断言函数第一次为False时，返回迭代器中的项。         •filterfalse：当断言函数第一次为False时，返回迭代器中所有的项。 与内置函数filter作用相反。     Combinations of items from iterators（组合迭代器中的项）         •product：返回迭代器中项的笛卡尔乘积，是一种很好的替代深层嵌套列表推导的方法。         •permutations：返回长度为N的有序排列迭代器。         •combination：返回长度为N的，用迭代器中未重复项所组成的无序组合。 在itertools模块中有更多的功能和recipes可用不能在这里一一提及。 每当你发现自己处理一些棘手的迭代代码，itertools文档是值得再次查看，看看是否有你想要的东西。

        Things to Remember

        1、使用Python的内置模块用于算法和数据结构。   

        2、不要自己重新实现此功能。