Python字典vs列表，哪個更快？

我正在編寫一個歐拉問題，我碰到了問題，引發了我的好奇心。我有兩個代碼片段。一個是列出其他使用字典。Python字典vs列表，哪個更快？

使用列表：

n=100000 
num=[] 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num.append(tmp) 
      suma+=i

使用字典：

n=100000 
num={} 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num[tmp]=i 
     suma+=i

我只關心性能。爲什麼使用字典的第二個示例運行得非常快，比列表的第一個示例更快。字典的例子幾乎快了三十倍！

我使用n = 1000000測試了這兩個代碼，第一個代碼在1032秒內運行，第二個代碼在3.3秒內運行,,, amazin'！

來源

2016-08-12 froycard

你的代碼中直接從你的IDE粘貼，突出了這一切，然後按Ctrl + K – Cody

@Cody問題是不是與縮進，但事實上他將代碼塊放在列表中。我已更正待處理編輯中的格式。 – Tagc

@Tagc我沒有看到代碼，所以我只是猜測。那麼好的修復。 – Cody

在一個列表中，代碼if tmp not in num:是O（n） ~~，而它在代碼~~ 中是O（lgn）。

編輯：該詞典是基於散列，所以它比直線列表搜索快得多。感謝@ user2357112指出這一點。

來源

2016-08-12 23:54:52 citaret

所以，是這樣嗎？如果是這樣（我想知道爲什麼），這誘使我使用字典而不是列表，爲表現有關我只是想找到一種更好的方式來加快我的編碼，這只是吹了我的腦海... – froycard

這是錯誤的。字典基於散列，而不是比較。他們的查找性能不是O（log（n））。 – user2357112

@ user2357112：是的，你是對的。 – citaret

我幾乎肯定使用字典的「魔法醬」在於字典由鍵 - 值對組成。

在列表中，您處理數組，這意味着for循環必須從列表中的索引0開始，以循環遍歷每條記錄。

字典只是要找到第一個「旋轉木馬」有問題的鍵 - >值對並返回，因此速度...

基本上，一組關鍵的測試會員 - >值對比搜索整個列表更快。你的列表越大，它會變得越慢......但這並不總是這種情況，有些情況下列表會更快......但我相信這可能是你正在尋找的答案

來源

2016-08-13 00:04:37 lopezdp

謝謝......我想我需要繼續研究這個問題,,,我第一次碰到這個......我想知道我在哪裏可以找到關於這個特定情況的更多信息？ – froycard

上週我在想這件事情，並且保存了這個鏈接。我想這是爲你發芽：https://wiki.python.org/moin/PythonSpeed – lopezdp

在Python中，字典密鑰查找的平均時間複雜度爲O（1），因爲它們被實現爲散列表。查找列表的時間複雜度平均爲O（n）。在你的代碼中，這在if tmp not in num:行中有所不同，因爲在列表案例中，Python需要搜索整個列表來檢測成員資格，而在dict情況下，除了絕對最壞的情況外，它不會。

有關更多詳細信息，請查看TimeComplexity。

來源

2016-08-13 00:10:35 Karin

非常感謝，您的評論剛剛指出我正確的方向，那些TimeComplexity表派上用場，必須考慮到當我嘗試在我的代碼中加快速度時。再次感謝 – froycard

如果是與速度有關，則不應創建任何列表：

n = 100000 
factors = ((frozenset(factors(i)), i) for i in range(2, n+1)) 
num = {k:v for k,v in factors if len(k)==2} 
suma = sum(num.values())

來源

2016-08-13 06:14:26 Daniel

Python字典vs列表，哪個更快？

回答

相關問題