3.6. bisect — 维护有序列表

本节目标: 每次有数据添加到列表时维护列表的有序性但无需调用排序功能。

bisect 模块里实现了一个向列表插入元素时也会顺便排序的算法。

以排序方式插入

下面是一个使用 insort() 方法将数据以排序后的顺序插入到列表的例子。

bisect_example.py

import bisect

# 一些随机数
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

l = []
for i in values:
    position = bisect.bisect(l, i)
    bisect.insort(l, i)
    print('{:3}  {:3}'.format(i, position), l)

第一列输出表示插入的随机数是多少。第二列表示这个随机数应该在列表中插入的位置。其余的部分则是插入数据后得到的列表。

$ python3 bisect_example.py

New  Pos  Contents
---  ---  --------
 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]
 77    8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
  1    0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

这个例子比较简单，实际上，考虑到要排序的数据量，简单的创建一个列表然后进行一次排序可能要快很多。相比之下，对于长列表来说，使用这种算法能很好得节约时间和节省内存，尤其是在对比两个元素需要花费大量计算的时候。

对重复的数据的处理

从之前的结果集合中我们可以看到有一个重复的数字 77，对于重复的值， bisect 模块提供了两种方法来进行处理：你可以选择将新值插到旧值的左边，也可以插到右边。 insort() 函数实际上是 insort_right() 函数，这个函数会将新值插到旧值的右边。与它相当的函数 insort_left() 则是将值插到旧值的左边。

bisect_example2.py

import bisect

# 一些随机数
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

# 使用 bisect_left 和 insort_left 来进行后续操作。
l = []
for i in values:
    position = bisect.bisect_left(l, i)
    bisect.insort_left(l, i)
    print('{:3}  {:3}'.format(i, position), l)

同样的数据使用 bisect_left() 和 insort_left() 操作后结果并不会有什么不同，只是遇到相同的值时，插入的位置不一样。

$ python3 bisect_example2.py

New  Pos  Contents
---  ---  --------
 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]
 77    7 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
  1    0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

参考

• bisect 标准库文档
• 维基百科: 按序插入 -- 按序插入算法介绍.

本译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

原文地址：https://learnku.com/docs/pymotw/bisect-m...

译文地址：https://learnku.com/docs/pymotw/bisect-m...