我寫了一個關于動態規劃的函數。遞歸公式為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 中的列表)可能是最佳選擇。
如果您的數據集具有非整數鍵,則字典是最佳選擇。這就是它的設計目的。
如果您有大間隔的整數鍵,與列表相比,字典將節省大量內存,因為列表必須包含大量浪費的索引。
添加回答
舉報
0/150
提交
取消