亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

為什么在相同的 Python 代碼中 List 比 Dict 快?

為什么在相同的 Python 代碼中 List 比 Dict 快?

江戶川亂折騰 2021-09-25 10:10:23
我寫了一個關于動態規劃的函數。遞歸公式為T(n) = T(0) * T(n-1) + T(1) * T(n-2) + … + T(n-1) * T(0)如您所見, 的值T(n)取決于 的值T(0) … T(n-1)。在這個問題中,我需要存儲T(0) … T(n-1)來計算T(n)。但哪種數據結構最好?假設我們已經完成了計算T(0) … T(5)。我們需要計算T(6)我們可以將 T 存儲在以下結構中:T = [1,1,2,5,14,42,0]T = {0:1,1:1,2:2,3:5,4:14,5:42,6:0}我的答案是dict首先,因為獲取的時間復雜度T(k)是O(1)。但是經過測試list和dict。測試結果表明list比 快dict。 為什么???我n = 1000用來測試程序。import timeitdef test(n, T):    T[0] = 1    # calculate T[i]    # we need to calculate T[0]-> T[n-1] at first.    for i in range(1,n+1):         for j in range(i):            T[i] += T[j]*T[i-1-j]    return T[n]# initial list TT_1 = [0]*1001 # initial dict TT_2 = {} for i in range(1001):    T_2[i] = 0t = timeit.timeit(stmt="test(1000,T_1)",setup="from __main__ import test,T_1;",number=10)print("store T with list, total time is:",t)t = timeit.timeit(stmt="test(1000,T_2)",setup="from __main__ import test,T_2;",number=10)print("store T with dict, total time is:",t)運行結果如下:用list存儲T,總時間為:6.454328614287078用dict存儲T,總時間為:6.761199993081391謝謝你的幫助。
查看完整描述

2 回答

?
慕姐8265434

TA貢獻1813條經驗 獲得超2個贊

字典使用散列來查找增加了一些開銷的值。還存在沖突的可能性,這需要更多的性能來解決。

長答案:

Hashing:
Dictionary 被實現為一個 hashtable,它是一種內部將值存儲在數組中的數據結構。它通過將鍵傳遞給散列函數來確定要使用的索引。散列函數將產生一個內部數組范圍內的值。這是一種通過鍵而不是索引來查找項目的相對快速的方法。但是由于每次都需要運行這個散列函數,它仍然比直接通過索引查找要慢。

碰撞:
字典在大多數情況下不能完全避免碰撞。內部數組既可以實現為鏈表數組,也可以使用其他技術來解決沖突。如果數據集變化緩慢,或者從不變化,則可以避免沖突;為給定的數據集創建一個完美的哈希函數。沒有適用于所有數據集的通用完美哈希函數,這是不可能的。因此,諸如 Python 中提供的通用字典必須實現沖突解決。

哪種數據結構更好?這取決于您的數據是如何映射的。

如果您可以將它映射到具有很少間隙的連續整數鍵(例如 0、1、2、3、4、5 等...),那么數組(python 中的列表)可能是最佳選擇。

如果您的數據集具有非整數鍵,則字典是最佳選擇。這就是它的設計目的。

如果您有大間隔的整數鍵,與列表相比,字典將節省大量內存,因為列表必須包含大量浪費的索引。


查看完整回答
反對 回復 2021-09-25
  • 2 回答
  • 0 關注
  • 317 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號