python库
Source
Edit
History

维护有序数组的模块bisect

文章目录
  1. 1. 以排序顺序插入
  2. 2. 处理重复
  3. 3. 参考资料

bisect 模块，用于维护有序列表。实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。

以排序顺序插入

看下面的例子，insort()用于按排序顺序将项目插入列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import bisect

# A series of random numbers
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)
    
# output
# 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()，在现有值之前插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import bisect

# A series of random numbers
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

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

# Use bisect_left and 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)
    
# output
# 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]

当使用 bisect_left() 和 insort_right() 操作相同的数据时，结果是相同的排序列表，但插入位置对于重复值是不同的。

参考资料