Python中bisect的使用方法

心已赠人 2022-11-15 15:55 156阅读 0赞

Python中列表（list）的实现其实是一个数组，当要查找某一个元素的时候时间复杂度是O(n)，使用list.index()方法，但是随着数据量的上升，list.index()的性能也逐步下降，所以我们需要使用bisect模块来进行二分查找，前提我们的列表是一个有序的列表。

**递归二分查找和循环二分查找**

def binary_search_recursion(lst, val, start, end):
        if start > end:
            return None
        mid = (start + end) // 2
        if lst[mid] < val:
            return binary_search_recursion(lst, val, mid + 1, end)
        if lst[mid] > val:
            return binary_search_recursion(lst, val, start, mid - 1)
        return mid
      
    def binary_search_loop(lst, val):
        start, end = 0, len(lst) - 1
        while start <= end:
            mid = (start + end) // 2
            if lst[mid] < val:
                start = mid + 1
            elif lst[mid] > val:
                end = mid - 1
            else:
                return mid
        return None

为了比对一下两者的性能，我们使用timeit模块来测试两个方法执行，timeit模块的timeit方法默认会对需要测试的函数执行1000000，然后返回执行的时间。

''' 遇到问题没人解答？小编创建了一个Python学习交流QQ群：531509025 寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！ '''
    >>> import random
    >>> from random import randint
    >>> from random import choice
    >>> random.seed(5)
    >>> lst = [randint(1, 100) for _ in range(500000)]
    >>> lst.sort()
    >>> val = choice(lst)
    >>> val
    6
    >>> def test_recursion():
    ...     return binary_search_recursion(lst, val, 0, len(lst) - 1)
    ...
    >>> def test_loop():
    ...     return binary_search_loop(lst, val)
    ...
    >>> import timeit
    >>> t1 = timeit.timeit("test_recursion()", setup="from __main__ import test_recursion")
    >>> t1
    3.9838006450511045
    >>> t2 = timeit.timeit("test_loop()", setup="from __main__ import test_loop")
    >>> t2
    2.749765167240339

可以看到，循环二分查找比递归二分查找性能要来的好些。现在，我们先用bisect的二分查找测试一下性能

**用bisect来搜索**

>>> import bisect
    >>> def binary_search_bisect(lst, val):
    ...     i = bisect.bisect(lst, val)
    ...     if i != len(lst) and lst[i] == val:
    ...         return i
    ...     return None
    ...
    >>> def test_bisect():
    ...     return binary_search_bisect(lst, val)
    ...
    >>> t3 = timeit.timeit("test_bisect()", setup="from __main__ import test_bisect")
    >>> t3
    1.3453236258177412

对比之前，我们可以看到用bisect模块的二分查找的性能比循环二分查找快一倍。再来对比一下，如果用Python原生的list.index()的性能

''' 遇到问题没人解答？小编创建了一个Python学习交流QQ群：531509025 寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！ '''
    >>> def test_index():
    ...     return lst.index(val)
    ...
    >>> t4 = timeit.timeit("test_index()", setup="from __main__ import test_index")
    >>> t4
    518.1656223725007

可以看到，如果用Python原生的list.index()执行1000000，需要500秒，相比之前的二分查找，性能简直慢到恐怖

**用bisect.insort插入新元素**

排序很耗时，因此在得到一个有序序列之后，我们最好能够保持它的有序。bisect.insort就是为这个而存在的

insort(seq, item)把变量item插入到序列seq中，并能保持seq的升序顺序

import random
    from random import randint
    import bisect
     
    lst = []
    SIZE = 10
    random.seed(5)
    for _ in range(SIZE):
        item = randint(1, SIZE)
        bisect.insort(lst, item)
        print('%2d ->' % item, lst)

输出：

10 -> [10]
     5 -> [5, 10]
     6 -> [5, 6, 10]
     9 -> [5, 6, 9, 10]
     1 -> [1, 5, 6, 9, 10]
     8 -> [1, 5, 6, 8, 9, 10]
     4 -> [1, 4, 5, 6, 8, 9, 10]
     1 -> [1, 1, 4, 5, 6, 8, 9, 10]
     3 -> [1, 1, 3, 4, 5, 6, 8, 9, 10]
     2 -> [1, 1, 2, 3, 4, 5, 6, 8, 9, 10]