当前位置:天才代写 > tutorial > Python教程 > python模块先容- bisect模块维护有序列表

python模块先容- bisect模块维护有序列表

2017-11-03 08:00 星期五 所属: Python教程 浏览:553

bisect –维护有序列表

目标:不需要每次挪用sort的方法维护有序列表。

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

插入

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一样支持要害字参数,发起如下处理惩罚:

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

 

    关键字:

[contact-form-7 id="17097" title="form2"]天才代写-代写联系方式