Python3.12教程 Python简介 Python环境搭建 pip的安装和使用 virtualenv 虚拟环境 代码编辑器 帮助文档 编译器与解释器 “Hello World！” 基础知识 基础语法 变量与常量 运算符 输入输出 数据类型 数字类型 布尔类型 列表 元组 字符串 字典 bytes 集合set 流程控制 顺序执行 条件判断 循环控制 函数 函数基础 参数类型 变量作用域 range()函数 递归函数 匿名函数 推导式 迭代器 生成器 装饰器 内置函数 文件读写 面向对象编程 类和实例 封装、继承和多态 成员保护和访问限制 @property装饰器 特殊成员和魔法方法 reflect反射 异常处理 调试和测试 模块与包 常用标准库 os sys subprocess random bisect hashlib queue fileinput shutil zipfile tarfile getpass json pickle shelve time datetime timeit logging 正则表达式 正则表达式语法 re模块 网络编程 socket编程 socketserver编程 多线程与多进程 多线程threading 生产者消费者模式 线程池 多进程multiprocess 协程与异步IO

bisect

阅读: 20427     评论：1

bisect模块实现了二分查找和插入算法

这个模块短小精干，简单易用，并且可以用C重写。

我们可以看一下bisect模块的源码。

"""Bisection algorithms."""

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)

insort = insort_right   # backward compatibility

def bisect_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
    return lo

bisect = bisect_right   # backward compatibility

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)


def bisect_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
    return lo

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

这可能是Python初学者少有的能快速看懂的标准库源代码。整个模块去掉注释语句，就这么多行代码。

bisect = bisect_right这一行其实就是个alias，用于向后兼容。

最后的try、except语句为我们提供了用C语言重写算法的钩子。

方法介绍

bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：

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

定位x在序列a中的插入点，并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中，那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。

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

和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。

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

等同于bisect_right()。

注意，前面这三个方法都是获取插入位置，也就是列表的某个下标的，并不实际插入。但下面三个方法实际插入元素，没有返回值。

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

将x插入有序序列a内，并保持有序状态。相当于a.insert(bisect.bisect_left(a, x, lo, hi), x)。碰到相同的元素则插入到元素的左边。这个操作通常是 O(log n) 的时间复杂度。

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

同上，只不过碰到相同的元素则插入到元素的右边。

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

等同于insort_right()。

实例展示：

import bisect

x = 200
list1 = [1, 3, 6, 24, 55, 78, 454, 555, 1234, 6900]
ret = bisect.bisect(list1, x)
print("返回值： ", ret)
print("list1 = ", list1)

#------------------------------
运行结果：
返回值：  6
list1 =  [1, 3, 6, 24, 55, 78, 454, 555, 1234, 6900]

##########################################################
import bisect

x = 200
list1 = [1, 3, 6, 24, 55, 78, 454, 555, 1234, 6900]
ret = bisect.insort(list1, x)
print("返回值： ", ret)
print("list1 = ", list1)

#------------------------------------------
运行结果：
返回值：  None
list1 =  [1, 3, 6, 24, 55, 78, 200, 454, 555, 1234, 6900]

下面是一个bisect和random配合的例子：

import bisect
import random

random.seed(1)

print('New  Pos Contents')
print('---  --- --------')

l = []
for i in range(1, 15):
    r = random.randint(1, 100)
    position = bisect.bisect(l, r)
    bisect.insort(l, r)
    print('%3d  %3d' % (r, position), l)

#------------------------------------------
打印结果：
New  Pos Contents
---  --- --------
 18    0 [18]
 73    1 [18, 73]
 98    2 [18, 73, 98]
  9    0 [9, 18, 73, 98]
 33    2 [9, 18, 33, 73, 98]
 16    1 [9, 16, 18, 33, 73, 98]
 64    4 [9, 16, 18, 33, 64, 73, 98]
 98    7 [9, 16, 18, 33, 64, 73, 98, 98]
 58    4 [9, 16, 18, 33, 58, 64, 73, 98, 98]
 61    5 [9, 16, 18, 33, 58, 61, 64, 73, 98, 98]
 84    8 [9, 16, 18, 33, 58, 61, 64, 73, 84, 98, 98]
 49    4 [9, 16, 18, 33, 49, 58, 61, 64, 73, 84, 98, 98]
 27    3 [9, 16, 18, 27, 33, 49, 58, 61, 64, 73, 84, 98, 98]
 13    1 [9, 13, 16, 18, 27, 33, 49, 58, 61, 64, 73, 84, 98, 98]

下面的5个例子是利用bisect模块实现通用的列表元素查询方法：

def index(a, x):
    '定位最左边的值等于x的元素的下标'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    '获取最靠右的值小于x的元素'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    '获取最靠右的值小于等于x的元素'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    '获取最靠左边的值大于x的元素'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    '获取最靠左边的值大于或等于x的元素'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

下面是一个利用bisect自动由百分制成绩转换为ABCD等级的方法：90 以上是‘A’, 80 -89 是‘B’, 

>>> 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']

另外一个例子

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: 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)
 random hashlib 

评论总数： 1

点击登录后方可评论

https://blog.csdn.net/lovetaozibaby/article/details/122970099


By   Aodami    On   2022年9月15日 10:33   回复