python模块： bisect模块维护有序列表

墨蓝 2024-03-30 10:07 34阅读 0赞

[bisect][] –维护有序列表

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

bisect模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是[二分法][Link 2]的意思，这里使用二分法来排序，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 rin 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)

来源：[https://www.weidianyuedu.com][https_www.weidianyuedu.com]

[bisect]: https://so.csdn.net/so/search?q=bisect&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E6%9C%89%E5%BA%8F%E5%88%97%E8%A1%A8&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%88%86%E6%B3%95&spm=1001.2101.3001.7020
[https_www.weidianyuedu.com]: https://www.weidianyuedu.com