Python 中l(wèi)ist ,set,dict的大規(guī)模查找效率對比詳解
很多時候我們可能要頻繁的進行元素的find 或in操作,本人一直天真的以為python的list做了hash,通過紅黑樹來高效查找···直到今天我真正來測試它和set,dict的查找效率時,才發(fā)現(xiàn)自已想太多了?。。?!
先看代碼:
__author__ = 'jmh081701' import numpy import time l=[] sl=set() dl=dict() r=numpy.random.randint(0,10000000,100000) for i in range(0,100000): l.append(r[i]) sl.add(r[i]) dl.setdefault(r[i],1) #生成3種數(shù)據(jù)結構供查找,常規(guī)的list,集合sl,字典dl.里面的元素都是隨機生成的,為什么要隨機生成元素?這是防止某些結構對有序數(shù)據(jù)的偏向導致測試效果不客觀。 start=time.clock() for i in range(100000): t=i in sl end=time.clock() print("set:",end-start) #計算通過set來查找的效率 start=time.clock() for i in range(100000): t=i in dl end=time.clock() print("dict:",end-start) #計算通過dict的效率 start=time.clock() for i in range(100000): t=i in l end=time.clock() print("list:",end-start) #計算通過list的效率
結果:
set: 0.01762632617301519 dict: 0.021149536796960248 ······ ··· ··
呵呵呵呵···list等了20分鐘都沒出結果。
所以···結果一覽無余啊。
查找效率:set>dict>list
單次查詢中:看來list 就是O(n)的;而set做了去重,本質應該一顆紅黑樹(猜測,STL就是紅黑樹),復雜度O(logn);dict類似對key進行了hash,然后再對hash生成一個紅黑樹進行查找,其查找復雜其實是O(logn),并不是所謂的O(1)。O(1)只是理想的實現(xiàn),實際上很多hash的實現(xiàn)是進行了離散化的。dict比set多了一步hash的過程,so 它比set慢,不過差別不大。
so,如果是要頻繁的查找,請使用set吧!
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
selenium設置瀏覽器為headless無頭模式(Chrome和Firefox)
這篇文章主要介紹了selenium設置瀏覽器為headless無頭模式(Chrome和Firefox),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-01-01Python getattr()函數(shù)使用方法代碼實例
這篇文章主要介紹了Python getattr()函數(shù)使用方法代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08Python selenium爬取微博數(shù)據(jù)代碼實例
這篇文章主要介紹了Python selenium爬取微博數(shù)據(jù)代碼實例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05