Question

当处理大的列表时，有序列表比非有序列表有一定优势。例如，有序列表的元素获取时间为O(log n)。

但是有很多次，我看到有人试图实现自己的数据结构或算法去处理这样的场景。这是个糟糕的想法，没必要花时间在已经解决的问题上。

首先，Python提供了一个bisect模块，其包含了二分查找算法。非常容易使用，如示例10.5所示。

示例 10.5　bisect的用法

>>> farm = sorted(['haystack', 'needle', 'cow', 'pig'])
>>> bisect.bisect(farm, 'needle')
3
>>> bisect.bisect_left(farm, 'needle')
2
>>> bisect.bisect(farm, 'chicken')
0
>>> bisect.bisect_left(farm, 'chicken')
0
>>> bisect.bisect(farm, 'eggs')
1
>>> bisect.bisect_left(farm, 'eggs')
1

bisect函数能够在保证列表有序的情况下给出要插入的新元素的索引位置。

如果想要立即插入，可以使用bisect模块提供的insort_left``和``insort_right函数，如示例10.6所示。

示例 10.6　bisect.insort的用法

>>> farm
['cow', 'haystack', 'needle', 'pig']
>>> bisect.insort(farm, 'eggs')
>>> farm
['cow', 'eggs', 'haystack', 'needle', 'pig']
>>> bisect.insort(farm, 'turkey')
>>> farm
['cow', 'eggs', 'haystack', 'needle', 'pig', 'turkey']

可以使用这些函数创建一个一直有序的列表，如示例10.7所示。

示例 10.7　SortedList的实现

import bisect

class SortedList(list):
　　def __init__(self, iterable):
　　　　super(SortedList, self).__init__(sorted(iterable))

　　def insort(self, item):
　　　　bisect.insort(self, item)

　　def index(self, value, start=None, stop=None):
　　　　place = bisect.bisect_left(self[start:stop], value)
　　　　if start:
　　　　　　place += start
　　　　end = stop or len(self)
　　　　if place < end and self[place] == value:
　　　　　　return place
　　　　raise ValueError("%s is not in list" % value)

显然，不应该用直接的append或extend函数来追加或扩展这个列表，否则列表将不再有序。

此外还有许多Python库实现了上面代码的各种不同版本，以及更多的数据类型，如二叉树和红黑树。Python包blist（https://pypi.python.org/pypi/blist）和bintree（https://pypi.python.org/ pypi/bintrees/）就包含了用于这些目的的代码，不要开发和调试自己的版本。