bisect –维护有序列表
目的:不需要每次调用sort的方式维护有序列表。
bisect模块实现了一个算法用于插入元素到有序列表。在一些情况下,这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是二分法的意思,这里使用二分法来排序,bisect的源代码是二分法排序的样板。这个模块的代码不到100行。
插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import bisect import random # Use aconstant seed to ensure that # the samepseudo-random numbers # are usedeach time the loop is run. random.seed( 1 ) print 'New Pos Contents' print '--- --- --------' # Generaterandom numbers and # insert theminto a list in sorted # order. l = [] for i inrange( 1 , 15 ): #产生1-100的随机数 r = random.randint( 1 , 100 ) position = bisect.bisect(l, r) bisect.insort(l, r) print '%3d %3d' % (r, position), l |
执行结果:
#./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]
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]
Bisect模块提供的函数有:
bisect.bisect_left(a,x, lo=0, hi=len(a)) :
查找在有序列表a中插入x的index。lo和hi用于指定列表的区间,默认是使用整个列表。如果x已经存在,在其左边插入。返回值为index。
bisect.bisect_right(a,x, lo=0, hi=len(a))
bisect.bisect(a, x,lo=0, hi=len(a))
这2个和bisect_left类似,但如果x已经存在,在其右边插入。
bisect.insort_left(a,x, lo=0, hi=len(a))
在有序列表a中插入x。和a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。
bisect.insort_right(a,x, lo=0, hi=len(a))
bisect.insort(a, x,lo=0, hi=len(a))
和insort_left类似,但如果x已经存在,在其右边插入。
可以函数可以分2类,bisect*,用于查找index。Insort*用于实际插入。默认重复时从右边插入。实际常用的估计是insort。
标准中有个根据分数计算出评级的实例:
>>> def grade(score,breakpoints=[60, 70, 80, 90], grades=’FDCBA’):
… i = bisect(breakpoints, score)
… return grades[i]
…
>>> [grade(score)for score in [33, 99, 77, 70, 89, 90, 100]]
[‘F’, ‘A’, ‘C’,’C’, ‘B’, ‘A’, ‘A’]
Bisect不像sort一样支持关键字参数,建议如下处理:
1
2
3
4
5
6
7
8
9
10
11
|
>>> data = [( 'red' , 5 ), ( 'blue' , 1 ), ( 'yellow' , 8 ), ( 'black' , 0 )] >>> data.sort(key = lambdar: r[ 1 ]) >>> keys = [r[ 1 ] for r in data] #precomputed list of keys >>> data[bisect_left(keys, 0 )] ( 'black' , 0 ) >>> data[bisect_left(keys, 1 )] ( 'blue' , 1 ) >>> data[bisect_left(keys, 5 )] ( 'red' , 5 ) >>> data[bisect_left(keys, 8 )] ( 'yellow' , 8 ) |
暂无评论内容