Python中bisect的使用方法

yipeiwu_com6年前Python基础

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,然后返回执行的时间。

>>> 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()的性能

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python 搭建简单的http server,可直接post文件的实例

server: #coding=utf-8 from BaseHTTPServer import BaseHTTPRequestHandler import cgi class Po...

解决pyinstaller打包pyqt5的问题

pyinstaller打包使用pyqt5模块的时候,在win平台下,由于pyinstaller无法准确获取QT动态库文件路径,会报错导致无法打开运行程序,并提示错误信息pyinstall...

使用Python生成url短链接的方法

几乎所有的微薄都提供了缩短网址的服务,其原理就是将一个url地址按照一定的算法生成一段字符串,然后加在一个短域名后面边成了一个新的url地址,数据库中会存放这个短地址和原始的地址,当用户...

Python实现在线暴力破解邮箱账号密码功能示例【测试可用】

本文实例讲述了Python实现在线暴力破解邮箱账号密码功能。分享给大家供大家参考,具体如下: dic 字典格式如下(mail.txt) : username@gmail.com:pa...

python tornado使用流生成图片的例子

监控中,通常要使用图片更直观的看出集群的运行状况。 以下是一个简单的demo,通过rrdtool生成动态的图片。Python3, tornado. web.py templates/in...