爲什麼collections.deque比collections.defaultdict慢？

Question

請原諒我以這樣的一般方式提問，因爲我確定他們的表現取決於他們的使用方式，但在我的情況下，collections.deque比我想要驗證值的存在方式要慢得多。

我使用了spelling correction from Peter Norvig來驗證用戶對一小組單詞的輸入。由於我沒有使用詞頻詞典，所以我最初使用簡單的list而不是defaultdict，但只要我注意到單個單詞查找花費了大約25秒，就用deque代替了它。

令人驚訝的是，這並不比使用list快，所以我返回使用defaultdict，它幾乎是瞬間返回結果。

有人可以向我解釋這種性能差異嗎？

在此先感謝

---

PS：如果你一個人想重現我在說什麼，改變弱勢族羣的劇本以下行。

-NWORDS = train(words(file('big.txt').read())) 
+NWORDS = collections.deque(words(file('big.txt').read())) 

-return max(candidates, key=NWORDS.get) 
+return candidates 

Answer 1

這三種數據結構是不能互換的，它們各自有不同的目的，有非常不同的特點：

• 列表是動態數組，可以使用它們來存儲順序物品快速隨機訪問，用作堆棧（最後添加和刪除）或者只是存儲一些東西，然後以相同的順序迭代它。
• Deques也是序列，僅用於在兩端添加和刪除元素，而不是隨機訪問或堆棧式增長。
• 字典（提供一個默認值只是一個相對簡單和方便，但對於這個問題 - 無關擴展）是散列表，它們將全功能鍵（而不是索引）與值相關聯，並提供對值的快速訪問通過密鑰和（必然）非常快速的檢查關鍵存在。他們沒有維持秩序並要求鑰匙可以被烘烤，但是，你不能在沒有打破雞蛋的情況下製作煎蛋卷。

所有這些屬性都很重要，只要您選擇其中一個，請牢記它們。在這個特殊情況下，你的脖子是結合字典的最後一個屬性和必須檢查的可能更正的數量。一些簡單的組合應該得出一個具體的公式，這個代碼爲一個給定的單詞生成的編輯次數，但是每個錯誤地預測這些事情的人通常都會知道，即使對於一般的單詞，它也會出乎意料地大。

對於每個這些編輯，有一個檢查edit in NWORDS淘汰導致未知單詞的編輯。在Norvig的程序中沒有什麼問題，因爲in檢查（關鍵存在檢查）如前所述非常快。但是你用一個序列（一個deque）交換了字典！對於序列，in必須遍歷整個序列，並將每個項目與搜索到的值進行比較（它可以在找到匹配時停止，但由於最少的編輯是位於雙端隊列開頭的已知單詞，它通常仍會搜索全部或大部分deque）。由於有很多詞彙，並且每次編輯都會進行測試，所以您最終花費了99％的時間在一個序列中進行線性搜索，您只需對一個字符串進行散列並將其比較一次（或至多 - 碰撞案例 - 幾次）。

如果你不需要權重，你可以在概念上使用你永遠不會看到的僞造值，並且仍然可以獲得O（1）in檢查的性能提升。實際上，你應該使用一個set，它使用與字典幾乎相同的算法，並刪除它存儲該值的部分（它實際上是第一次實現的，我不知道自從sets在專用的，獨立的C模塊中重新實現）。