title: Why is collections.deque slower than collections.defaultdict?
body: <p>Forgive me for asking in in such a general way as I'm sure their performance is depending on how one uses them, but in my case <code>collections.deque</code> was way slower than <code>collections.defaultdict</code> when I wanted to verify the existence of a value.</p>
  
  <p>I used the <a href="http://norvig.com/spell-correct.html" rel="nofollow">spelling correction from Peter Norvig</a> in order to verify a user's input against a small set of words. As I had no use for a dictionary with word frequencies I used a simple <code>list</code> instead of <code>defaultdict</code> at first, but replaced it with <code>deque</code> as soon as I noticed that a single word lookup took about 25 seconds. </p>
  
  <p>Surprisingly, that wasn't faster than using a <code>list</code> so I returned to using <code>defaultdict</code> which returned results almost instantaneously.</p>
  
  <p>Can someone explain this difference in performance to me?</p>
  
  <p>Thanks in advance</p>
  
  <hr>
  
  <p><em>PS</em>: If one of you wants to reproduce what I was talking about, change the following lines in Norvig's script.</p>
  
  <pre><code>-NWORDS = train(words(file('big.txt').read()))
  +NWORDS = collections.deque(words(file('big.txt').read()))
  
  -return max(candidates, key=NWORDS.get)
  +return candidates
  </code></pre>