1

私は次の問題を抱えています - 繰り返しが許可された膨大な数の単語を含むテキストファイルが与えられています。最も出現頻度の高い 1000 語を降順に出力するアルゴリズムを作成する必要があります。ここに例があります

**input.txt**

aa aa bb cc bb bb bb dd dd

**output.txt** (note - frequencies can be repeated)

bb 4
aa 2
dd 2
cc 1

  1. そして、これがこの問題を解決する私の方法です。HashMap最初にすべての単語を読み取り、単語をキーとして保存します。これを行うことの最終結果は、すべての単語とその頻度を取得することです。

  2. 次に、 を反復処理して、HashMap各キーと値のペアに対してオブジェクト {word, frequency} を作成し、それを a に挿入しますSortedSet(そのためのコンパレータを作成しました)。

  3. SortedSet結果を得るために 1000 回繰り返します。

この問題を解決するためのより良い方法を知りたいです。

ありがとう

4

2 に答える 2

4

この問題を解決するより良い方法はありますか?

これには2つの見方があります...「より良い」とはどういう意味かによって異なります。

「より良い」が「より少ない時間やメモリを使用する」ことを意味する場合、問題のサイズと利用可能なリソースに応じて、これに対処する潜在的な方法があります。例えば：

  • テキスト ファイル (または複数のファイル) がこれを正当化するのに十分な大きさである場合は、問題を分割してマルチプロセッサで実行することを検討できます。しかし、それは単純ではありません...そして、問題が小さすぎることが判明した場合、パーティション化のオーバーヘッドにより、実際にはソリューションが遅くなる可能性があります!

  • リンクされた Q&A には、ステップ 2 と 3 を潜在的に高速化する方法が説明されています。問題は、コードをベンチマークすると、ステップ 1 でほとんどの CPU 時間が費やされていることがわかるでしょう。（そして、入力ファイルが大きいほど、その効果は顕著になる可能性があります...）

「より良い」が「問題をより迅速に解決する」ことを意味する場合、答えは「おそらくいいえ」です。説明したアルゴリズムの適切に実装されたバージョンがあると仮定すると、(潜在的に) 高速なより洗練されたアルゴリズムに移行するための労力は、それだけの価値がない場合があります。

コンピューターの時間は、ソフトウェア開発者の時間よりも安い!

私のアドバイスは、次のことを行うことです。

  1. 既存のプログラムをベンチマークします。実際の入力ファイルで十分に高速に実行されますか? 「はい」の場合、プログラムが完了したと呼びます。

  2. 実際の入力ファイルで実行されている既存のプログラムをプロファイリングします。プロファイリングは明らかなパフォーマンスのホットスポットを示していますか? コードをチューニングする機会はありますか? 「はい」の場合は、それらを試して、ベンチマークの手順を繰り返して、実際に役立つかどうかを確認してください。

  3. GC ログを見てください。コードに過剰な GC オーバーヘッドがある兆候はありますか? 「はい」の場合は、単純な GC チューニング (ヒープ サイズの増加など) で違いが生じるかどうかを確認してください。

上記のすべてを行っても満足のいくパフォーマンスが得られない場合は、今が代替アルゴリズムを探し始めるときです。

于 2013-09-29T01:55:24.067 に答える