python bisect模块维护有序列表的简单示例

bisect –维护有序列表

目的：不需要每次调用sort的方式维护有序列表。

bisect模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是二分法的意思，这里使用二分法来排序，bisect的源代码是二分法排序的样板。这个模块的代码不到100行。

插入

# @param python模块介绍- bisect模块维护有序列表
# @author 编程之家 52php.cn|www.www.52php.cn 

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

# End www.52php.cn

执行结果：

#./bisect_example.py

New Pos Contents

--- --- --------

14 0[14]

85 1[14,85]

77 1[14,77,85]

26 1[14,26,85]

50 2[14,50,85]

45 2[14,45,85]

66 4[14,66,85]

79 6[14,79,85]

10 0[10,14,85]

3 0[3,10,85]

84 9[3,84,85]

44 4[3,44,85]

77 9[3,85]

1 0[1,3,85]

Bisect模块提供的函数有：

bisect.bisect_left(a,x,lo=0,hi=len(a)) :

查找在有序列表a中插入x的index。lo和hi用于指定列表的区间，默认是使用整个列表。如果x已经存在，在其左边插入。返回值为index。

bisect.bisect_right(a,hi=len(a))

bisect.bisect(a,hi=len(a))

这2个和bisect_left类似，但如果x已经存在，在其右边插入。

bisect.insort_left(a,hi=len(a))

在有序列表a中插入x。和a.insert(bisect.bisect_left(a,lo,hi),x) 的效果相同。

bisect.insort_right(a,hi=len(a))

bisect.insort(a,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,89,90,100]]

['F','A','C','B','A']

Bisect不像sort一样支持关键字参数，建议如下处理：

# @param python模块介绍- bisect模块维护有序列表
# @author 编程之家 52php.cn|www.www.52php.cn 

>>> 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)

# End www.52php.cn

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!