2016-04-03 11 views
3

私はPython 2でオートコンプリートとオートコレクトプログラムを書いています。スペルチェッカーの書き方についてPeter Norvigのブログであるlinkを使って、オートコレクトプログラムを書いています。autocorrectプログラムのためのpythonデータ構造の高速保存と取り出し?

ここでは、ネストされたリストを使用して実装されたトライデータ構造を使用しています。私は特定の接頭辞で始まるすべての単語を与えることができるので、私はトライを使用しています。リーフは、単語と単語の頻度を示す値のタプルになります。例えば、悪い、バット、

['b'['a'['d',('bad',4),'t',('bat',3)]],'c'['a'['t',('cat',4)]]] 

ここで、4,3,4は、単語の使用回数または頻度の値です。同様に、私は約13万語の英語辞書を作成し、cPickleを使ってそれを保存しました。

これで、毎回トライ全体が読み込まれるのに約3〜4秒かかります。単語に遭遇するたびに頻度値をインクリメントしてから、更新されたトライを再度保存する必要があります。想像することができますが、毎回3〜4秒間待ってから、更新されたトライを毎回保存するために多くの時間を待つことが大きな問題になります。プログラムが実行されるたびにたくさんの更新操作を実行して保存する必要があります。

繰り返して更新される大きなデータ構造を格納するための高速または効率的な方法がありますか? IDEやモバイルデバイスの自動修正プログラムのデータ構造は、どのように保存されていますか?&はすばやく検索されましたか?私はさまざまなアプローチにもオープンしています。

答えて

2

いくつかのことが思い浮かびます。

1)データを分割します。特定の文字で始まる試行を格納しているそれぞれ26個のファイルを使用するとします。プレフィックスを使用するように改善することができます。このようにして、書き込む必要のあるデータの量が少なくなります。

2)すべてをディスクに反映させないでください。多くの操作を実行する必要がある場合は、それらをRAM(メモリ)で実行し、最後に書き留めます。データが失われることを恐れている場合は、しばらくしてから、またはいくつかの操作の後で計算をチェックポイントすることができます。

3)マルチスレッド。スペルチェックだけをプログラムするのでなければ、他に必要なことがあるはずです。ディスクIOを実行している間にすべてをブロックしないように、書き込みをロードする別のスレッドを用意してください。 Pythonでのマルチスレッドはちょっと難しいですが、それは可能です。

4)カスタム構造。シリアライゼーションに費やされた時間の一部は、シリアライゼーション機能を呼び出すことです。関数呼び出しの数が多いすべての辞書があるからです。完全なケースでは、正確にディスク表現に一致するメモリ表現を持つ必要があります。その後、大きな文字列を読み込んでカスタムクラスに配置します(必要なときにその文字列をディスクに書き込む)。これはもう少し進歩していると思います。なぜなら、Pythonはビットで遊ぶのが効率的ではないので、それほど巨大ではないでしょうが、速度の最後の部分を絞る必要がある場合は、これが道のりです。

+1

@gospelslide:上記の優れた提案を容易にするために作られた 'klepto'パッケージ(私は作者です)を見てみてください。 –

1

シリアル化を別のスレッドに移して定期的に実行することをお勧めします。すでに最新のバージョンがメモリに保存されているため、毎回データを再読み込みする必要はありません。このようにして、データがディスクに保存されている間、プログラムはユーザーに応答します。ディスク上に保存されたバージョンが遅れている可能性があり、最新のアップデートがプログラムクラッシュの場合に失われる可能性がありますが、これはあなたのユースケースにとって大きな問題ではないはずです。

特定のユースケースと環境によって異なりますが、ローカルデータセットを持つほとんどのプログラムは、マルチスレッドを使用してそれらを同期します。