当前位置:编程学习 > python >>

python模块介绍- bisect-有序列表

python模块介绍- bisect
 
 
 
#承接软件自动化实施与培训等gtalk:ouyangchongwu#gmail.com qq 37391319 博客:http://blog.csdn.net/oychw
#版权所有,转载刊登请来函联系
# 深圳测试自动化python项目接单群113938272深圳会计软件测试兼职 6089740
#深圳地摊群 66250781武冈洞口城步新宁乡情群49494279
#自动化测试和python群组: http://groups.google.com/group/automation_testing_python
#参考资料:《The Python Standard Library by Example 2011》
2.4 bisect –维护有序列表
目的:不需要每次调用sort的方式维护有序列表。
bisect模块实现了一个算法用于插入元素到有序列表。在一些情况下,这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是二分法的意思,这里使用二分法来排序,bisect的源代码是二分法排序的样板。这个模块的代码不到100行。
2.4.1 插入
 
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):
    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一样支持关键字参数,建议如下处理:
>>> 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)
 
 
补充:Web开发 , Python ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,