java - How to count string num with limit memory?

Question

The task is to count the num of words from a input file.

the input file is 8 chars per line, and there are 10M lines, for example:

aaaaaaaa  
bbbbbbbb  
aaaaaaaa  
abcabcab  
bbbbbbbb  
...

the output is:

aaaaaaaa 2  
abcabcab 1  
bbbbbbbb 2  
...

It'll takes 80MB memory if I load all of words into memory, but there are only 60MB in os system, which I can use for this task. So how can I solve this problem?

My algorithm is to use map<String,Integer>, but jvm throw Exception in thread "main" java.lang.OutOfMemoryError: Java heap space. I know I can solve this by setting -Xmx1024m, for example, but I want to use less memory to solve it.

score 7 · Accepted Answer

最も堅牢な解決策は、ディスク領域を使用することだと思います。

たとえば、(ディスク領域を使用する) 大きなファイルを並べ替えるアルゴリズムを使用して、ファイルを別のファイルに並べ替えてから、同じ単語の連続出現をカウントできます。

この投稿がお役に立てば幸いです。または、外部ソートについて自分で検索してください。

更新 1

または、@jordeuが提案するように、H2、JavaDB などの Java 組み込みデータベースライブラリを使用できます。

更新 2

Prefix Treeを使用して、別の可能な解決策を考えました。ただし、私はそれらの専門家ではないため、最初のものを好みます。

score 5 · Accepted Answer

一度に 1 行ずつ読んでから、たとえば、HashMap<String,Integer> 単語をキーとして、カウントを整数として配置する場所を用意します。

キーが存在する場合は、カウントを増やします。それ以外の場合は、キーをカウント 1 でマップに追加します。

ファイル全体をメモリに保持する必要はありません。

score 3 · Accepted Answer

はっきりした単語の数を意味していると思いますか？

したがって、明らかなアプローチは、マップ内のキーとして各単語 (に関する固有の情報) を格納することです。値は関連付けられたカウンターです。予想される個別の単語の数によっては、それらすべてを保存することでメモリに収まる場合もありますが、すべての単語が異なる最悪のシナリオではそうではありません。

必要なメモリを減らすために、単語自体の代わりに、単語のチェックサムを計算して保存できます。たとえば、8 文字の単語の代わりに 4 バイトのチェックサムを保存するには (保存に少なくとも 9 バイトが必要)、90M ではなく 40M が必要です。さらに、単語ごとにカウンターも必要です。特定の単語の予想される出現回数によっては、2 バイト (最大 65535 回の出現) で済む場合があります。これには、10M の異なる単語に対して最大 60M のメモリが必要です。

アップデート

もちろん、チェックサムはさまざまな方法で計算でき、ロスレスであってもなくてもかまいません。これは、単語で使用される文字セットにも大きく依存します。たとえば、小文字の標準 ASCII 文字のみが使用されている場合 (上記の例に示されているように)、各位置に 26 個の異なる文字があります。したがって、各文字は 5 ビットでロスレスにエンコードできます。したがって、8 文字は 5 バイトに収まり、これは制限を少し超えていますが、状況によっては十分に密集している可能性があります。

score 1 · Accepted Answer

私は理論的な答えを説明するのが苦手ですが、ここに行きます....

あなたの質問は完全に明確ではないので、私は仮定を立てました。

すべての個別の単語を格納するために使用されるメモリは 80MB です (ファイル全体が大きくなります)。
単語にはASCII以外の文字が含まれている可能性があります（そのため、データを生のバイトとして扱います）。

毎回 ~ 40MB の異なる単語を保存するファイルを 2 回読み込めば十分です。

//  Loop over the file and for each word:
//
//      Compute a hash of the word. 
//      Convert the hash to a number by some means (skip if possible).
//      If the number is odd then skip to the next word. 
//      Use conventional means to store the distinct word. 
//
//  Do something with all the distinct words.

even次に、代わりにを使用して上記をもう一度繰り返しoddます。

次に、タスクを 2 つに分割し、それぞれを個別に実行できます。最初のセットの単語は、2 番目のセットには表示されません。

単語は (理論的には) すべて同じ文字で終わる可能性があるため、ハッシュが必要です。

ソリューションを拡張して、さまざまなメモリ制約で動作するようにすることができます。奇数/偶数とだけ言うのではなく、を使用して単語を X グループに分けることができますnumber MOD X。

score 1 · Accepted Answer

H2 データベースエンジンを使用します。必要に応じて、ディスクまたはメモリ上で動作します。そして、それは本当に優れたパフォーマンスを持っています。

score 0 · Accepted Answer

各 8 バイトワードをに変換してlong使用することができますTLongIntHashMap。これは、Map<String, Integer>またはMap<Long, Integer>

使用できる明確な単語が必要な場合TLongHashSet

score 0 · Accepted Answer

あらゆる最適化と同様に、トレードオフがあります。あなたの場合、より少ないメモリで同じタスクを実行できますが、実行時間が長くなります。

不足しているリソースはメモリであるため、単語を RAM に保存することはできません。

他の投稿で言及されているように、単語の代わりにハッシュを使用できますが、ファイルのサイズが大きくなると、ある時点で再び同じ問題に遭遇するため、これは解決策ではありません.

はい、外部 Web サーバーを使用してファイルをクランチし、クライアントアプリのジョブを実行できますが、質問を読むと、すべてを 1 つ (アプリ) で実行したいようです。

したがって、私の提案は、ファイルを反復処理し、単語ごとに次のようにすることです。

単語が初めて見つかった場合は、文字列を整数値 1 と共に結果ファイルに書き込みます。
単語が以前に処理された場合 (結果ファイルに表示されます)、レコード値を増やします。

このソリューションは、入力ファイルの行数や単語の長さに関係なく、適切にスケーリングされます*。

出力ファイルへの書き込み方法を最適化して、検索を高速化できますが、上記の基本的なバージョンで十分です。

編集:
*ディスク容量 XD がなくなるまで、うまくスケーリングします。したがって、前提条件は、少なくとも 2N バイトの空き使用可能スペースを持つディスクを用意することです。ここで、N はバイト単位の入力ファイルサイズです。

score 0 · Accepted Answer

各単語の SHA-1 を作成し、これらの数値をセットに格納します。次に、もちろん、数値を読み取るときに、そこに Set があるかどうかを確認します [(Set は定義上一意であるため、完全に必要というわけではないため、その SHA-1 番号を「追加」することもできます)]。

score 0 · Accepted Answer

単語がどのような種類の文字で構成されているかに応じて、このシステムを選択できます。

大文字と小文字のアルファベットの文字が含まれる可能性がある場合、(26*2)^8 の組み合わせ、つまり 281474976710656 になります。この数値は long データ型に収まります。

したがって、次のように文字列のチェックサムを計算します。

public static long checksum(String str)
{
    String tokes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    long checksum = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        int c = tokens.indexOf(str.charAt(i));

        checksum *= tokens.length();
        checksum += c;
    }

    return checksum;
}

これにより、1 ワードあたりの使用メモリが 8 バイト以上削減されます。文字列はの配列でchar、各文字は Java 2 バイトです。したがって、8 文字 = 16 バイトです。ただし、文字列クラスには char 配列だけでなく、より多くのデータが含まれています。サイズとオフセットの整数も含まれており、int あたり 4 バイトです。Strings および char 配列へのメモリポインタも忘れないでください。したがって、生の見積もりでは、これにより 1 ワードあたり 28 バイトが削減されると思われます。

したがって、1 ワードあたり 8 バイトで、10 000 000 ワードがあると、76 MB になります。あなたは私が気づいたことをすべて忘れていたので、これはあなたの最初の間違った見積もりです. つまり、この方法でもうまくいかないということです。

score 0 · Accepted Answer

可能な解決策：

ファイルの並べ替えを使用してから、各値の結果の出現を数えるだけです。
ファイルをデータベースにロードし、次のように count ステートメントを使用します。select value, count(*) from table group by value

score 0 · Accepted Answer

最初にファイルを並べ替えることができれば (たとえば、Unix でメモリ効率の良い "並べ替え" ユーティリティを使用する)、簡単です。並べ替えられたアイテムを読み取り、隣接する重複を数えながら、合計をすぐに新しいファイルに書き込みます。

Java を使用して並べ替える必要がある場合は、次の投稿が役立ちます。

http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

score 0 · Accepted Answer

ファイルを複数回読み取ることで、一定のメモリを使用できます。

基本的な考え方:

ファイルを n 個のパーティション p_1...p_n として扱い、それぞれを RAM にロードできるサイズにします。

p_i を Map 構造にロードし、ファイル全体をスキャンして、p_i 要素のみのカウントを追跡します (Heiko Rupp の回答を参照)。
j より小さい i を持つパーティション p_j で同じ値に遭遇した場合、要素を削除します
マップ内の要素の結果数を出力する
マップをクリアし、すべての p_1...p_n に対して繰り返します

java - How to count string num with limit memory?

12 に答える 12

アップデート

Related

Reference