2

使い方次第だと思いますので、一般的な質問は許してください。でも、私の場合は、値の存在を確認したいときcollections.dequeよりもかなり遅かったです。collections.defaultdict

小さな単語セットに対してユーザーの入力を検証するために、PeterNorvigのスペル修正を使用しました。単語頻度のある辞書は使い物にならなかったので、最初はシンプルなものを使いましたlistが、1つの単語の検索に約25秒かかることに気づいたらすぐにdefaultdict置き換えました。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
4

1 に答える 1

10

これらの3つのデータ構造は互換性がなく、非常に異なる目的を果たし、非常に異なる特性を持っています。

  • リストは動的配列です。リストを使用してアイテムを順番に格納し、ランダムアクセスを高速化したり、スタックとして使用したり（最後に追加と削除を行ったり）、何かを格納して後で同じ順序で繰り返し処理したりします。
  • Dequeもシーケンスであり、ランダムアクセスやスタックのような拡張ではなく、両端で要素を追加および削除するためだけのものです。
  • 辞書（デフォルト値を提供するのは比較的単純で便利ですが、この質問では-無関係な拡張）はハッシュテーブルであり、（インデックスではなく）フル機能のキーを値に関連付け、キーによる値への非常に高速なアクセスを提供しますそして（必然的に）キーの存在を非常に高速にチェックします。それらは順序を維持せず、キーがハッシュ可能である必要がありますが、まあ、卵を壊さずにオムレツを作ることはできません。

これらのプロパティはすべて重要です。どちらかを選択するときは常に覚えておいてください。この特定のケースで首を折るのは、辞書の最後のプロパティと、チェックする必要のある可能な修正の数の組み合わせです。いくつかの単純な組み合わせ論は、このコードが特定の単語に対して生成する編集の数の具体的な式に到達する必要がありますが、そのようなことを頻繁に誤解した人は、平均的な単語でも驚くほど多くなることを知っています。

これらの編集のそれぞれについてedit in NWORDS、未知の単語をもたらす編集を取り除くためのチェックがあります。inNorvigのプログラムでは、チェック（キーの存在チェック）は前に述べたように非常に高速であるため、少し問題はありません。しかし、辞書をシーケンス（両端キュー）と交換しました！シーケンスの場合、inシーケンス全体を反復処理し、各アイテムを検索された値と比較する必要があります（一致するものが見つかると停止できますが、編集が最も少ないのは両端キューの先頭にある既知の単語であるため、通常はすべてまたはほとんどを検索しますdeque）。かなりの数の単語があり、生成された編集ごとにテストが行​​われるため、文字列をハッシュして1回（または最大で-で）比較できるシーケンスで線形検索を実行することに時間の99％を費やすことになります。衝突の場合-数回）。

重みが必要ない場合は、概念的には見たことのない偽の値を使用しても、O（1）inチェックのパフォーマンスを向上させることができます。実際にはset、辞書とほぼ同じアルゴリズムを使用し、値を格納する部分を切り取るだけのを使用する必要があります（実際には、最初にそのように実装されました。セットが専用の個別のCモジュールで再実装されます）。

于 2011-08-04T08:16:47.843 に答える