1

特定の単語が辞書 (英語の単語リスト) にあるかどうかをすばやく確認できる必要があります。メンバーシップをチェックする速度 (要素の追加や削除ではありません) だけに関心があり、メモリの使用は実際には問題ではありません。

もともと私はこのようなセットを使用していました：

words = set(x.strip().lower() for x in open("/usr/share/dict/words").readlines())
if(word in words):
    ...

私のプログラムは約かかりました。テスト入力で実行するのに 4 秒。次に、DAWG ( http://pypi.python.org/pypi/pyDAWG ) を使用して、代わりに DAWG を事前計算して酸洗いすることで最適化を試みました。

words = pickle.load(open('wordlistDAWG.pyd'))
if(words.word2index(word) is not None):
    ...

同じテスト入力で、プログラムの実行に約 40 秒かかりました (私が気にしない DAWG をロードするのに数秒かかりました)。私は、DAWG を使用すると物事がより速く実行されることを望んでいました!

python がどのように物事をハッシュするかについての理解が欠けているのかもしれません - DAWG や Trie ではなく、私が取得しようとしているセット (O(1) メンバーシップ テスト?) はすでに最高ですか? DAWG はメモリを節約しますが、計算は節約しませんか?

どうもありがとう！

4

2 に答える 2

1

セットの代替として使用する場合、DAWG は CPU サイクルを節約しないと思います。

セットのルックアップはセットのサイズに関して O(1) であり、DAWG のルックアップも DAWG アイテムの数に関して O(1) です。DAWG ルックアップは、ルックアップ キーの長さに関して O(N) です (キーが DAWG にある場合、キーがDAWG にあるかどうかを確認するために必要な len(key) ステップがあります)。セット ルックアップも、キーの長さに関して O(N) です (キーのハッシュを計算する必要があるため)。つまり、これは実装に要約され、

  • ハッシュマップは通常、他のデータ構造 (DAWG や Tries を含む) よりも高速です。
  • Python セットは適切に最適化されています。組み込み型のハッシュ計算も最適化されています。CPython のセット/ディクテーションには、Unicode キー用の特殊なコードパスがあります。

DAWG は、アイテムが DAWG にない場合に有利な場合があります。これは、これをチェックするために len(key) ステップよりも少ないステップしか必要とせず、ハッシュを計算するために len(key) ステップが常に必要になるためです (ハッシュ値がキャッシュされていない場合)。しかし、この場合でもビルトインセットには勝てません。

恥知らずなプラグイン - https://pypi.python.org/pypi/DAWGを試すこともできますが、__contains__それでも dict よりも約 2 倍遅くなります。

ところで、word2index の pyDAWG Python バージョンは内部で多くの dict ルックアップを行うため、単一のセット ルックアップよりも高速になることはありません。

于 2013-03-01T13:30:18.770 に答える
0

word2index必要がないように聞こえる呼び出しによって、完璧なハッシュ機能を使用しています。exists代わりに使ってみませんか？

于 2013-02-19T09:45:41.277 に答える