今天在搜python的redis sorted set实现的时候,发现了一个名叫bisect的模块。  感觉有些意思就介绍下。 

该文章写的有些乱,欢迎来喷 ! 另外文章后续不断更新中,请到原文地址查看更新。

http://xiaorui.cc/2016/03/01/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%E7%9A%84python-bisect%E6%9C%89%E5%BA%8F%E9%98%9F%E5%88%97/

大多数要把一组纯数字的列表有序化会直接进行sort()排序,然而有个场景,我们会往列表里不断的插入数据,那么怎么更好的维护列表的有序性? python中的bisect模块可以向列表中插入元素,同时维护列表的顺序。 

bisect的实现也比较简单,大致的原理是首先使用二分查找,查找应该插入的位置,然后用list的insert方法将元素插入到指定的位置。

从理论速度来说,bisect的二分查找速度要快些,但python的sort()是c写的,而bisect排序是纯python写的扩展。 

下面是python bisect的使用方法.

bisect里就四个模块:

bisect_*的函数主要是用来查找插入的位置,insort_*函数是直接将元素放入相应的位置,完成插入。
从bisect模块的实现可以看出,bisect模块中insort函数的插入实现实际上用的就是bisect函数返回的index。
bisect函数返回的index,也可以直接用在list的insert函数中作为插入位置参数。


简单说下二分查找这个算法. 

二分查找的对象是:有序数组。这点特别需要注意。要把数组排好序先。

基本步骤:

从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;
如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空,则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度:O(logn)

下面是bisect实现源码,你会发现他的实现太利索了.

没啥好总结的,用python实现了一遍二分查找算法,话说有些算法长时间不用就忘的干净。



对Python及运维开发感兴趣的朋友可以加QQ群 : 478476595 !!!
{ 2000人qq大群内有各厂大牛,常组织线上分享及沙龙,对高性能及分布式场景感兴趣同学欢迎加入该QQ群 }

另外如果大家觉得文章对你有些作用!   帮忙点击广告. 一来能刺激我写博客的欲望,二来好维护云主机的费用.
如果想赏钱,可以用微信扫描下面的二维码. 另外再次标注博客原地址  xiaorui.cc  ……   感谢!
暂无相关产品