PyMOTW: bisect =================== .. currentmodule:: bisect * 模块： bisect * 目的： 维持一个有序列表, 当每次增加一个元素到列表时无需调用sort过程. * python版本： 1.4+ 描述 ---- bisect模块实现了一个算法, 用于向一个有序列表中插入一个元素. 这比重复排序一个列表, 或重构一个很大的有序列表要高效的多. 示例 ----- 使用 ``bisect.insort()`` 的简单示例, 插入元素到一个有序列表中. .. code-block:: python import bisect import random # Use a constant seed to ensure that we see # the same pseudo-random numbers each time # we run the loop. random.seed(1) # Generate 20 random numbers and # insert them into a list in sorted # order. l = [] for i in range(1, 20): r = random.randint(1, 100) position = bisect.bisect(l, r) bisect.insort(l, r) print '%2d %2d' % (r, position), l 上述脚本的输出如下: :: 14 0 [14] 85 1 [14, 85] 77 1 [14, 77, 85] 26 1 [14, 26, 77, 85] 50 2 [14, 26, 50, 77, 85] 45 2 [14, 26, 45, 50, 77, 85] 66 4 [14, 26, 45, 50, 66, 77, 85] 79 6 [14, 26, 45, 50, 66, 77, 79, 85] 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85] 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85] 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85] 44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85] 77 9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85] 1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85] 45 7 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85] 73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85] 23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85] 95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95] 91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95] 第一列显示了新的随机数, 第二列显示了数被插入到列表中的位置. 最后是当前排序列表中的元素. 这是一个很简单的示例，我们处理的速度由于列表规模小以及每次只需排序一次, 变的非常快速. 但对于一个很长的list, 利用这种方法能得到时间和内存上的节省. 你可能会注意到上述结果中存在一些重复值(45和77). bisect模块提供了2种方法来处理重复, 新值可以插入到已经存在值的左边或者右边. 对应的是insort_right()函数, 可以将值插入已有值的后面(右边), insort_left()函数可以插入到之前(左边). 如果我们使用bisect_left()和bisect_right()来处理同样的数据, 那么最后获得的list是相同的, 只是中间插入的位置会有不同. .. code-block:: python # Reset the seed random.seed(1) # Use bisect_left and insort_left. l = [] for i in range(1, 20): r = random.randint(1, 100) position = bisect.bisect_left(l, r) bisect.insort_left(l, r) print '%2d %2d' % (r, position), l :: 14 0 [14] 85 1 [14, 85] 77 1 [14, 77, 85] 26 1 [14, 26, 77, 85] 50 2 [14, 26, 50, 77, 85] 45 2 [14, 26, 45, 50, 77, 85] 66 4 [14, 26, 45, 50, 66, 77, 85] 79 6 [14, 26, 45, 50, 66, 77, 79, 85] 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85] 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85] 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85] 44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85] 77 8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85] 1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85] 45 6 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85] 73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85] 23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85] 95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95] 91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95] 除了python实现外, 还有一个更快的c实现, 如果c版本存在, 那么 ``import bisect`` 模块时会自动调用c版本而不是调用python版本. 参考 ----- * `Insertion Sort `_