您好,登錄后才能下訂單哦!
本篇文章為大家展示了Python中字典和列表性能的對比分析,內容簡明扼要并且容易理解,絕對能使你眼前一亮,通過這篇文章的詳細介紹希望你能有所收獲。
前面我們了解了 “大O表示法” 以及對不同的算法的評估,下面來討論下 Python 兩種內置數據類型有關的各種操作的大O數量級:列表 list 和字典dict。
這是 Python 中兩種非常重要的數據類型,后面會用來實現各種數據結構,通過運行試驗來估計其各種操作運行時間數量級。
對比 list 和 dict 操作如下:
List列表數據類型常用操作性能:
最常用的是:按索引取值和賦值(v=a[i],a[i]=v),由于列表的隨機訪問特性,這兩個操作執行時間與列表大小無關,均為O(1)。
另一個是列表增長,可以選擇 append() 和 “+”:lst.append(v),執行時間是O(1);lst= lst+ [v],執行時間是O(n+k),其中 k 是被加的列表長度,選擇哪個方法來操作列表,也決定了程序的性能。
測試 4 種生成 n 個整數列表的方法:
創建一個 Timer 對象,指定需要反復運行的語句和只需要運行一次的"安裝語句"。
然后調用這個對象的 timeit 方法,指定反復運行多少次。
# Timer(stmt="pass", setup="pass") # 這邊只介紹兩個參數 # stmt:statement的縮寫,就是要測試的語句,要執行的對象 # setup:導入被執行的對象(就和run代碼前,需要導入包一個道理) 在主程序命名空間中 導入 time1 = Timer("test1()", "from __main__ import test1") print("concat:{} seconds".format(time1.timeit(1000))) time2 = Timer("test2()", "from __main__ import test2") print("append:{} seconds".format(time2.timeit(1000))) time3 = Timer("test3()", "from __main__ import test3") print("comprehension:{} seconds".format(time3.timeit(1000))) time4 = Timer("test4()", "from __main__ import test4") print("list range:{} seconds".format(time4.timeit(1000))
結果如下:
可以看到,4種方法運行時間差別挺大的,列表連接(concat)最慢,List range最快,速度相差近 100 倍。append要比 concat 快得多。另外,我們注意到列表推導式速度大約是 append 兩倍的樣子。
總結列表基本操作的大 O 數量級:
我們注意到 pop 這個操作,pop()是從列表末尾移除元素,時間復雜度為O(1);pop(i)從列表中部移除元素,時間復雜度為O(n)。
原因在于 Python 所選擇的實現方法,從中部移除元素的話,要把移除元素后面的元素,全部向前挪位復制一遍,這個看起來有點笨拙
但這種實現方法能夠保證列表按索引取值和賦值的操作很快,達到O(1)。這也算是一種對常用和不常用操作的折中方案。
list.pop()的計時試驗,通過改變列表的大小來測試兩個操作的增長趨勢:
import timeit pop_first = timeit.Timer("x.pop(0)", "from __main__ import x") pop_end = timeit.Timer("x.pop()", "from __main__ import x") print("pop(0) pop()") y_1 = [] y_2 = [] for i in range(1000000, 10000001, 1000000): x = list(range(i)) p_e = pop_end.timeit(number=1000) x = list(range(i)) p_f = pop_first.timeit(number=1000) print("{:.6f} {:.6f}".format(p_f, p_e)) y_1.append(p_f) y_2.append(p_e)
結果如下:
將試驗結果可視化,可以看出增長趨勢:pop()是平坦的常數,pop(0)是線性增長的趨勢。
字典與列表不同,是根據鍵值(key)找到數據項,而列表是根據索引(index)。最常用的取值和賦值,其性能均為O(1)。另一個重要操作contains(in)是判斷字典中是否存在某個鍵值(key),這個性能也是O(1)。
做一個性能測試試驗來驗證 list 中檢索一個值,以及 dict 中檢索一個值的用時對比,生成包含連續值的 list 和包含連續鍵值 key 的
dict,用隨機數來檢驗操作符 in 的耗時。
import timeit import random y_1 = [] y_2 = [] print("lst_time dict_time") for i in range(10000, 1000001, 25000): t = timeit.Timer("random.randrange(%d) in x" % i, "from __main__ import random, x") x = list(range(i)) lst_time = t.timeit(number=1000) x = {j: 'k' for j in range(i)} dict_time = t.timeit(number=1000) print("{:.6f} {:.6f}".format(lst_time, dict_time)) y_1.append(lst_time) y_2.append(dict_time)
結果如下:
可見字典的執行時間與規模無關,是常數。
而列表的執行時間則會隨著列表的規模加大而線性上升。
上述內容就是Python中字典和列表性能的對比分析,你們學到知識或技能了嗎?如果還想學到更多技能或者豐富自己的知識儲備,歡迎關注億速云行業資訊頻道。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。