今天就跟大家聊聊有關bisect函數(shù)怎么在Python中使用,可能很多人都不太了解,為了讓大家更加了解,小編給大家總結了以下內容,希望大家根據(jù)這篇文章可以有所收獲。
創(chuàng)新互聯(lián)主營浦東網(wǎng)站建設的網(wǎng)絡公司,主營網(wǎng)站建設方案,成都app軟件開發(fā)公司,浦東h5重慶小程序開發(fā)搭建,浦東網(wǎng)站營銷推廣歡迎浦東等地區(qū)企業(yè)咨詢Python中列表(list)的實現(xiàn)其實是一個數(shù)組,當要查找某一個元素的時候時間復雜度是O(n),使用list.index()方法,但是隨著數(shù)據(jù)量的上升,list.index()的性能也逐步下降,所以我們需要使用bisect模塊來進行二分查找,前提我們的列表是一個有序的列表。
遞歸二分查找和循環(huán)二分查找
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模塊來測試兩個方法執(zhí)行,timeit模塊的timeit方法默認會對需要測試的函數(shù)執(zhí)行1000000,然后返回執(zhí)行的時間。
>>> 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
可以看到,循環(huán)二分查找比遞歸二分查找性能要來的好些?,F(xiàn)在,我們先用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模塊的二分查找的性能比循環(huán)二分查找快一倍。再來對比一下,如果用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()執(zhí)行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]
看完上述內容,你們對bisect函數(shù)怎么在Python中使用有進一步的了解嗎?如果還想了解更多知識或者相關內容,請關注創(chuàng)新互聯(lián)成都網(wǎng)站設計公司行業(yè)資訊頻道,感謝大家的支持。
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內外云服務器15元起步,三天無理由+7*72小時售后在線,公司持有idc許可證,提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢,專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應用場景需求。
當前名稱:bisect函數(shù)怎么在Python中使用-創(chuàng)新互聯(lián)
鏈接URL:http://muchs.cn/article22/cddicc.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供外貿網(wǎng)站建設、網(wǎng)站收錄、建站公司、網(wǎng)站設計公司、定制網(wǎng)站、自適應網(wǎng)站
聲明:本網(wǎng)站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經(jīng)允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內容