なぜcollections.dequeはcollections.defaultdictよりも遅いのですか？

Question

私は彼らのパフォーマンスがどのように使用されているかによると確信していますが、私の場合はcollections.dequeがcollections.defaultdictより遅く、値の存在を確認したいと思っています。

私は小さなセットの単語に対してユーザーの入力を確認するためにspelling correction from Peter Norvigを使用しました。単語の頻度のある辞書には役に立たなかったので、最初はdefaultdictの代わりに単純なlistを使用しましたが、1単語の検索に約25秒かかったことに気付くとただちにdequeに置き換えました。

驚いたことに、それはlistを使用するよりも速くなかったので、私はdefaultdictを使用して戻って、結果をほぼ即座に返しました。

誰かがこのパフォーマンスの違いを私に説明できますか？事前

---

PSで

ありがとう：あなたの一つは、私が話していたものを再生したい場合は、Norvigのスクリプトに次の行を変更します。

-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

これらの3つのデータ構造は互換性がありません、彼らは非常に異なる目的を果たし、非常に異なる特性を持っている：

• リストが動的配列である、あなたは高速なランダムアクセスのために順次項目を格納するためにそれらを使用し、スタックとして使用（最後に追加および削除）するか、または何かを格納してから、後で同じ順序で反復処理します。
• Dequesもシーケンスであり、ランダムアクセスやスタックのような成長ではなく、両端で要素を追加したり削除したりするためだけです。
• ディクショナリ（比較的単純で便利なデフォルト値を提供しますが、この質問に対しては無関係な拡張子）はハッシュテーブルであり、インデックスの代わりに完全な機能を持つキーを値に関連付け、重要な存在の鍵と（必然的に）非常に速いチェックによって。彼らは秩序を維持しておらず、キーをハッシュ可能にする必要がありますが、卵を壊さずにオムレツを作ることはできません。

これらのプロパティはすべて重要です。いずれか一方を選択した場合は常に注意してください。この特殊なケースで首を壊すのは、辞書の最後の特性とチェックする必要のある訂正の数の組み合わせです。いくつかのシンプルなコンビナトリアルは、このコードが特定の単語に対して生成する編集数についての具体的な式に到達する必要がありますが、このようなことを十分に誤って予測した人は、平均単語でさえも驚くほど多くなります。

の場合、それぞれの編集には、edit in NWORDSのチェックがあり、不明な単語になる編集を除外します。 Norvigのプログラムでは少し問題はありません.のチェック（鍵の存在チェック）は、これまでのように非常に高速です。しかし、あなたは辞書をシーケンス（デキュ）でスワップしました！シーケンスの場合、inはシーケンス全体を反復し、各アイテムを検索された値と比較する必要があります（マッチすると停止する可能性がありますが、最小の編集は両端キューの先頭にある既知の単語なので、デキューのすべてまたはほとんど）。非常に少数の単語があり、生成された各編集に対してテストが行​​われるので、文字列をハッシュして一度比較することができるシーケンスで線形検索を行うと、99％の時間を費やします衝突の場合 - 数回）。

体重が必要ない場合は、決して見ない偽の値を概念的に使用しても、O（1）inチェックのパフォーマンスが向上します。実際には、setを使用して、辞書とほとんど同じアルゴリズムを使用し、値を格納する部分を切り捨てる必要があります（実際に最初に実装されたように、2つがどのように離れているか分かりません専用の独立したCモジュールで再実装されました）。