我寫了一個關于動態(tài)規(guī)劃的函數(shù)。遞歸公式為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)。但哪種數(shù)據(jù)結(jié)構(gòu)最好？假設我們已經(jīng)完成了計算T(0) … T(5)。我們需要計算T(6)我們可以將 T 存儲在以下結(jié)構(gòu)中：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)。但是經(jīng)過測試list和dict。測試結(jié)果表明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)運行結(jié)果如下：用list存儲T，總時間為：6.454328614287078用dict存儲T，總時間為：6.761199993081391謝謝你的幫助。
2 回答
慕姐8265434
TA貢獻1813條經(jīng)驗 獲得超2個贊
字典使用散列來查找增加了一些開銷的值。還存在沖突的可能性，這需要更多的性能來解決。
長答案：
Hashing：
Dictionary 被實現(xiàn)為一個 hashtable，它是一種內(nèi)部將值存儲在數(shù)組中的數(shù)據(jù)結(jié)構(gòu)。它通過將鍵傳遞給散列函數(shù)來確定要使用的索引。散列函數(shù)將產(chǎn)生一個內(nèi)部數(shù)組范圍內(nèi)的值。這是一種通過鍵而不是索引來查找項目的相對快速的方法。但是由于每次都需要運行這個散列函數(shù)，它仍然比直接通過索引查找要慢。
碰撞：
字典在大多數(shù)情況下不能完全避免碰撞。內(nèi)部數(shù)組既可以實現(xiàn)為鏈表數(shù)組，也可以使用其他技術(shù)來解決沖突。如果數(shù)據(jù)集變化緩慢，或者從不變化，則可以避免沖突；為給定的數(shù)據(jù)集創(chuàng)建一個完美的哈希函數(shù)。沒有適用于所有數(shù)據(jù)集的通用完美哈希函數(shù)，這是不可能的。因此，諸如 Python 中提供的通用字典必須實現(xiàn)沖突解決。
哪種數(shù)據(jù)結(jié)構(gòu)更好？這取決于您的數(shù)據(jù)是如何映射的。
如果您可以將它映射到具有很少間隙的連續(xù)整數(shù)鍵（例如 0、1、2、3、4、5 等...），那么數(shù)組（python 中的列表）可能是最佳選擇。
如果您的數(shù)據(jù)集具有非整數(shù)鍵，則字典是最佳選擇。這就是它的設計目的。
如果您有大間隔的整數(shù)鍵，與列表相比，字典將節(jié)省大量內(nèi)存，因為列表必須包含大量浪費的索引。
添加回答
舉報
0/150
提交
取消