Python中的bisect模块

Python 小记 2019-02-06 1772 字 44 浏览 点赞

前言

bisect模块在Python的官方库中属于小众,源码也不多,加上注释也没能超过100行。当你希望维护的列表总是有序时,bisect模块可能是不错的选择。

insort

bisect.insort()函数接受四个参数:

  • a:一个有序列表
  • x:需要插入的元素
  • lo:默认值为0(该参数不能小于0)
  • hi:默认值为列表的长(len(a)

使用:

In [2]: lyst = [5, 1, 8, 2, 9]

In [3]: lyst.sort()  # 对列表排序

In [4]: lyst
Out[4]: [1, 2, 5, 8, 9]

In [5]: bisect.insort(lyst, 3)  # 在lyst中有序的插入3

In [6]: lyst
Out[6]: [1, 2, 3, 5, 8, 9]

bisect模块中有关插入操作的方法有两个,一个是insort_left(),一个是insort_right()insort()方法是insort_right()方法的缩写。

区别在于,当将要插入的元素已经存在在列表中,insort_left()方法会把元素插入到存在元素的左边,而insort_right()方法会把元素插入到存在元素的右边。

bisect

bisect.bisect()类似bisect.insort()方法,不过bisect()不做插入操作,而是返回如果插入,那么插入位置的值。

In [0]: lyst = [5, 1, 8, 2, 9]

In [1]: lyst.sort()

In [2]: bisect.bisect(lyst, 4)
Out[2]: 2

In [3]: lyst
Out[3]: [1, 2, 5, 8, 9]

bisect.bisect()bisect.bisect_right()的缩写,另一个方法是bisect.bisect_left()

二分查找

bisect模块中的方法基于二分查找法实现,虽然代码不多,但效率很不错。需要注意的是,如果想在自己封装的对象里使用bisect模块中的方法,需要支持insert()操作。

以下是insort的源码(bisect类似):

def insort_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

def insort_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)

感谢



本文由 Guan 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论