1

単語 (一部は繰り返される) を含む 1GB (非常に大きな) ファイルが与えられた場合、ファイルを読み取り、各単語が繰り返される回数を出力する必要があります。私のソリューションが高性能かどうか教えてください。

(簡単にするために、既に単語を にキャプチャしていると仮定しますarraylist<string>)

大きなO(n)は「n」だと思います。私は正しいですか??

public static void main(String[] args) {

            ArrayList al = new ArrayList();
            al.add("math1");
            al.add("raj1");
            al.add("raj2");
            al.add("math");
            al.add("rj2");

            al.add("math");
            al.add("rj3");
            al.add("math2");
            al.add("rj1");
            al.add("is");
            Map<String,Integer> map= new HashMap<String,Integer>();

            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);

                    map.put(s,null);

            }
            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);
                if(map.get(s)==null)
                    map.put(s,1);
                else
                {
                    int count =(int)map.get(s);
                        count=count+1;
                        map.put(s,count);
                }


            }

            System.out.println("");
        }
4

5 に答える 5

2

HashMap を使用するよりもうまくできると思います。

ハッシュマップ ソリューションに関する考察の材料

あなたの答えは受け入れられますが、これを考慮してください。簡単にするために、スペースに到達するまで一度に1バイトずつファイルを StringBuffer に読み込むと仮定します。その時点で toString() を呼び出して、StringBuffer を String に変換します。次に、文字列が HashMap にあるかどうかを確認し、格納されるか、カウンターがインクリメントされます。

英語のディック。Linux に含まれているファイルは 400k ワードで、サイズは約 5MB です。したがって、あなたが読んだ「1GB」のテキストのうち、HashMap に保存されるのは約 5MB だけであると推測できます。ファイルの残りの部分は、マップ内での検索が終了した後にガベージ コレクションする必要がある文字列に変換されます。私は間違っている可能性がありますが、HashCode を計算するためにバイト配列を内部的にコピーする必要があるため、文字列の構築中にバイトが繰り返し反復されると思います。そのため、このソリューションはかなりの量の CPU サイクルを浪費し、GC を頻繁に発生させる可能性があります。

考えられる唯一の解決策であっても、面接でこのようなことを指摘しても問題ありません。

カスタムのRadixTreeまたは Trie のような構造の使用を検討する場合があります

RadixT/Trie の挿入メソッドがどのように機能するかを覚えておいてください。これは、文字/バイト (通常は文字列) のストリームを取得し、各要素をツリー内の現在の位置と比較します。プレフィックスが存在する場合は、ロック ステップでツリーとバイト ストリームを下に進めます。新しいサフィックスに到達すると、ツリーにノードを追加し始めます。ストリームの最後に到達すると、そのノードが EOW としてマークされます。ここで、スペースにヒットするたびに現在の位置をツリーのルートにリセットすることにより、はるかに大きなストリームを読み取りながら同じことを行うことができると考えてください。

独自の基数ツリー (またはトライ) を記述した場合、ノードには (マーカーの代わりに) 単語の終わりのカウンターがあり、insert メソッドがファイルから直接読み込まれます。スペースを読み取るまで、ノードを一度に 1 バイト/文字ずつツリーに挿入できます。その時点で、挿入メソッドは単語の終わりのカウンターをインクリメントし（既存の単語の場合）、ツリー内の現在の位置を先頭にリセットし、バイト/文字の挿入を再度開始します。基数ツリーが機能する方法は、単語の重複したプレフィックスを折りたたむことです。例えば：

The following file:

math1 raj1 raj2 math rj2 math rj3 

would be converted to:

(root)-math->1->(eow=1)
     |    |-(eow=2)
     |    
      raj->1->(eow=1)
      | |->2->(eow=1)
      | |->3->(eow=1)
      j2->(eow=1)

このようなツリーへの挿入時間は O(k) になります。ここで、k は最長の単語の長さです。ただし、各バイトを読み取るときに挿入/比較しているためです。すでに必要なファイルの読み取りよりも効率が悪いわけではありません。

また、スタック変数となる一時バイトにバイトを読み込むことに注意してください。そのため、ヒープからメモリを割り当てる必要があるのは、新しい単語 (実際には新しいサフィックス) に遭遇したときだけです。したがって、ガベージ コレクションはそれほど頻繁には発生しません。また、基数ツリーで使用されるメモリの合計は、HashMap よりもはるかに小さくなります。

于 2011-07-25T07:30:54.130 に答える
1

mapreduceソリューションの使用を検討しましたか？データセットが大きくなった場合は、データセットを分割して単語を並行して数える方がよいでしょう。

于 2011-12-01T01:39:34.240 に答える
1

理論的には、HashMap アクセスは一般に O(1) であるため、アルゴリズムは O(n) だと思いますが、実際にはいくつかの非効率性があります。理想的には、ファイルの内容を 1 回だけ反復処理して、単語を読み込んでいる間に単語を処理 (カウント) します。ファイルの内容全体をメモリ (ArrayList) に保存する必要はありません。コンテンツを 3 回ループします。1 回目は内容を読み取るため、2 回目と 3 回目は上記のコードの 2 つのループです。特に、上記のコードの最初のループは完全に不要です。最後に、構築時のデフォルト サイズが非常に小さいため、HashMap の使用は必要以上に遅くなり、内部で何度も拡大する必要があり、毎回ハッシュ テーブルを再構築する必要があります。保持するものに適したサイズから始めることをお勧めします。

于 2011-07-24T18:45:40.917 に答える
0

あなたの質問に答えるには、まず、HashMap がどのように機能するかを理解する必要があります。これはバケットで構成され、すべてのバケットはリンクされたリストです。ハッシュのために別のペアが同じバケットを占有する必要がある場合、リンクされたリストの最後に追加されます。そのため、マップの負荷率が高いと、検索と挿入が O(1) ではなくなり、アルゴリズムが非効率になります。さらに、マップのロード ファクターが事前定義されたロード ファクター (デフォルトでは 0.75) を超えた場合、マップ全体が再ハッシュされます。

これは、JavaDoc http://download.oracle.com/javase/6/docs/api/java/util/HashMap.htmlからの抜粋です。

再ハッシュ操作の回数を最小限に抑えるために、初期容量を設定するときは、マップ内の予想エントリ数とその負荷係数を考慮する必要があります。初期容量がエントリの最大数を負荷係数で割った値よりも大きい場合、再ハッシュ操作は発生しません。

したがって、すべての単語が一意であると推測して、マップ容量を事前定義することをお勧めします。

Map<String,Integer> map= new HashMap<String,Integer>(al.size());

それがなければ、ソリューションは十分に効率的ではありませんが、再ハッシュの償却により、要素の挿入には n ではなく 3n のコストがかかるため、線形近似 O(3n) があります。

于 2011-07-24T19:25:36.870 に答える
0

単語を含むファイルを 1 回だけ読む必要があります。

事前にヌルを配置する必要はありません。メイン ループ内で実行できます。

どちらの場合も複雑さは確かに O(n) ですが、定数をできるだけ小さくしたいと考えています。(O(n) = 1000 * O(n)、右 :) )

于 2011-07-24T18:58:45.073 に答える