hash - 文字数の最適化

Question

（これは現時点ではかなり仮説的なものなので、提供できる詳細はあまりありません。）

各行に 1 つずつ、ランダムな (英語の) 単語のフラットファイルがあります。各単語の出現回数をカウントする効率的なプログラムを作成する必要があります。ファイルは大きい (おそらく 1GB 程度) ですが、すべてに十分な RAM があります。それらは永続的なメディアに保存されているため、読み取り速度が遅いため、一度だけ直線的に読み取る必要があります。

私の頭の中で思いついた2つのアイデアは、単語でハッシュを使用することでした=>いいえ。発生の、またはいいえのトライ。終了ノードでのオカレンスの数。ハッシュ配列に十分な RAM がありますが、トライのルックアップは同じか高速になると考えています。

どのようなアプローチが最適でしょうか?

score 2 · Accepted Answer

キーが小文字に変換された単語であり、値がカウントである Dictionary オブジェクトを使用します。辞書に単語が含まれていない場合は、値 1 を追加します。単語が含まれている場合は、値を増やします。

score 2 · Accepted Answer

読むのが遅いことを考えると、おそらく目立った違いはありません。いずれにせよ、全体の時間はデータを読み取る時間によって完全に支配されるため、最適化に取り組む必要があります。メモリ内のアルゴリズム (実際にはほとんどがデータ構造) については、最も使いやすい言語でたまたま最も便利なものを使用してください。

score 2 · Accepted Answer

ハッシュテーブルは（正しく行われ、RAMがたくさんあると言った場合）O（1）で特定の単語をカウントしますが、トライはO（n）になります。ここで、nは単語の長さです。

十分な大きさのハッシュスペースがあれば、トライよりもハッシュテーブルの方がはるかに優れたパフォーマンスが得られます。

score 2 · Accepted Answer

葉が速くなる可能性があるため、カウントを試してみると思います。

まともなハッシュテーブルの実装では、単語を完全に読み取り、ハッシュ関数を使用して処理し、最後にテーブルを検索する必要があります。

単語を読んでいるときに検索が行われるように、トライを実装できます。この方法では、単語の完全なルックアップを行うのではなく、一意の単語プレフィックスを確立した後で、文字をスキップしていることに気付くことがよくあります。

たとえば、「torto」という文字を読んだことがある場合、トライは、このように始まる唯一の可能な単語が亀であることを認識します。

このインライン検索を、ハッシュアルゴリズムがハッシュできるよりも高速に単語に対して実行できれば、より高速に実行できるはずです。

ただし、これは完全にやり過ぎです。あなたが純粋に仮説的だと言ったので、私はとりとめのない質問をしました。あなたは仮説的なタイプの答えが欲しいと思いました。合理的な時間内にタスクを実行する、最も保守しやすいソリューションを使用してください。マイクロ最適化は通常、CPU 時間を節約するよりも工数を浪費します。

score 1 · Accepted Answer

あなたのユースケースではトライはやり過ぎだと思います。単語のハッシュ => 出現回数は、まさに私が使用するものです。Perl のような遅いインタープリター言語を使用しても、この方法でわずか数分で 1GB のファイルを書き換えることができます。（私は以前にこれをやったことがあります。）

score 1 · Accepted Answer

ハッシュ配列に十分な RAM がありますが、トライのルックアップは同じか高速になると考えています。

このコードは何回実行されますか? 1 回だけ実行する場合は、CPU の時間ではなく自分の時間を最適化し、(合理的な範囲内で) 実装するのに最も速い方法を実行することをお勧めします。キーと値のインターフェイスを実装する標準ライブラリ関数がある場合は、それを使用してください。

何度も実行している場合は、データファイルのサブセット (または複数のサブセット) を取得し、オプションのベンチマークを行います。データセットについて詳しく知らなければ、どちらか一方を推奨するのは疑わしいでしょう。

score 0 · Accepted Answer

大部分は、キャプチャしたデータで何をしたいかによって異なります。トライ (プレフィックスツリー) に対してハッシュテーブルを使用する理由を参照してください。

score 0 · Accepted Answer

簡単な python スクリプト:

import collections
f = file('words.txt')
counts = collections.defaultdict(int)
for line in f:
    counts[line.strip()] +=1

print "\n".join("%s: %d" % (word, count) for (word, count) in counts.iteritems())

score 0 · Accepted Answer

パイソンを使おう！

ハッシュテーブルにあるかどうかを尋ねる前に、行ごとにこれらの要素をセットデータ型に追加します。セットに含まれていることがわかったら、辞書の値 2 を追加します。これは、以前にセットに 1 回追加したためです。

これにより、毎回辞書に問い合わせることからメモリと計算の一部が取り除かれ、代わりに一意の値の単語をより適切に処理できます。呼び出しの最後に、辞書にないすべての単語をセットからダンプします1 の値。 (セットに関して 2 つのコレクションを交差させます)

hash - 文字数の最適化

9 に答える 9

Related

Reference