12

テキストファイルに50,000,000（整数、文字列）のペアがあります。整数はミリ秒単位の時間であるため、13桁の長さです（例：1337698339089）。

テキストファイルのエントリは次のようになります。

1337698339089|blaasdasd
1337698339089|asdasdas
1337698338089|kasda

同一のエントリが存在する可能性があります。

重複する整数を保持し、（整数、文字列）ペアを保持して、整数のエントリを（昇順で）並べ替えたいと思います。私が採用したアプローチはメモリエラーにつながるため、別のアプローチを探しています。

私のアプローチは次のようなものです（いくつかの擬似コードを使用）：

// declare TreeMap to do the sorting
TreeMap<Double, String> sorted = new TreeMap<Double, String>();

// loop through entries in text file, and put each in the treemap:
for each entry (integer, string) in the text file:

   Random rand = new Random();
   double inc = 0.0;

   while (sorted.get(integer + inc) != null) {
       inc = rand.nextDouble();
   }

   sorted.put(integer + inc, string);

ここでは乱数を使用して、重複する整数をツリーマップに入力できるようにしています（0から1の間で2倍にインクリメントすることにより）。

// to print the sorted entries:
for (Double d : sorted.KeySet()) {
    System.out.println(Math.round(d) + "|" + sorted.get(d));
}

このアプローチは機能しますが、50,000,000エントリに分類されます（ツリーマップが大きくなりすぎているため、またはwhileループの実行時間が長すぎるためと思われます）。

より経験豊富なプログラマーがどのようなアプローチを取るのか知りたいです。

どうもありがとう！

4

8 に答える 8

13

十分なメモリがあれば、リストでこれを行うことができるはずです。エントリ用に別のクラスを作成します。

class Foo : Comparable<Foo> {
    private final long time;
    private final String text;

    // Constructor etc
}

メモリに関しては、5,000 万のインスタンスとそれらへの参照を格納できる必要があります。32 ビット JVM では、次のようになります。

  • オブジェクトごとに 8 バイトのオーバーヘッド (IIRC)
  • 8 バイトtime
  • textフィールドの 4 バイト
  • 文字列の最大 54 バイト (8 バイトのオーバーヘッド + 3 つintのフィールド IIRC +char[]配列参照 + 10 文字の配列の最大 32 バイト)
  • 配列内の参照用に 4 バイトまたはArrayList

つまり、インスタンスあたり約 80 バイトです。切り上げると 100 とします。それらの 50,000,000 を保存するには、5,000,000,000 バイト、別名 5GB が必要であり、これは 32 ビット JVM が処理できると私が信じている以上のものです。

したがって、これらすべてをメモリ内で実行するには、64 ビット マシンと 64 ビット JVM が必要になります。参照が大きくなることなどにより、オーバーヘッドが多少増加する可能性があります。実行可能ですが、それほど快適ではありません。

ただし、これの大部分は文字列によるものです。本当に効率的になりたい場合は、巨大な char 配列を作成し、オフセットを .xml 内に格納することができFooます。テキストデータを読み取るように配列に読み取り、それを使用して並べ替え後にデータを書き出します。より複雑で醜いですが、メモリ効率が大幅に向上します。

別の方法として、これをすべてメモリ内で行うのではなく、ファイル システムを介した並べ替えに関する多くの情報を検索することもできます。

于 2012-05-22T15:14:40.603 に答える
2

データベース（H2のようにJavaプロジェクトに直接プルできるので便利です）を使用して、インデックスを希望どおりに設定することを検討するかもしれません。データベースは、大量のデータを処理して整理するという問題をすでに解決しています。次に、SQLクエリを実行して結果を順番に取得し、書き戻すことができます。

結果セットは、データをチャンクでストリーミングします。すべてを単一のリストにロードしようとしないでください。

H2はメモリ内でサポートしますが、RAMと64ビットJavaがたくさんない限り、この場合はディスクを使用するように構成します。

于 2012-05-22T15:15:59.480 に答える
1

doubleを格納するためにlongaを使用する理由

AMap<Long, String>は重複キーを持つことはできません。一方が他方を上書きします。

これらすべてを記憶に収めることができるとは思えません。これは、long を格納するためだけに 0.5 GB であり、String にはそれ以上です。おそらく、32 ビット JVM では実行できません。

于 2012-05-22T15:12:57.947 に答える
1

JVM により多くのメモリを割り当てましたか? -Xmx1024M コマンド ライン オプションを付けて実行してみてください。そして、treeMap は不必要に複雑に見えます。組み込みの Java コマンドを使用できます。

于 2012-05-22T15:18:36.790 に答える
1

あなたの問題は2つの部分に分かれているようです:

  1. アルゴリズム: Java ソート アルゴリズムのビルドを使用することをお勧めします。このなど、Googleで参照を簡単に見つけることができます。
  2. JVM:問題の根本原因は、Java 仮想マシンに十分なメモリが割り当てられていないように思われます。降下する量の情報を扱っているため、最大サイズを大きくすることをお勧めします。

探している JVM 引数は次のようになります。

  • -Xmsは、初期 Java ヒープ サイズを指定し、

  • -Xmx Java ヒープの最大サイズ。

参考：http ://www.rgagnon.com/javadetails/java-0131.html

于 2012-05-22T15:34:27.813 に答える
0

スローされたエラーは何ですか? すべてのデータを正常にメモリにロードできますか? Java Comparator クラスを試すことをお勧めします。たぶん、ペアを表すカスタム オブジェクトを作成するようなことを試してみます。

class Entry{
    long i;
    String s;
}

次に、カスタム Comparator を作成します

class IComp implements Comparator<Entry>{
    public int compare(Entry e1, Entry e2){
      if(e1.i < e2.i) return -1;
      //complete the rest

    }
}

次に、すべてのオブジェクトを配列 Entry[] エントリに入れ、コンパレータ IComp icomp を作成します。 Arrays.sort(entry, icomp) を使用します。

5000 万のオブジェクトを作成するので、十分なヒープスペースがあることを確認する必要があります。

多数の重複する文字列があり、これらの文字列が不変である場合。文字列を保存するためのセットを作成し、それらをリサイクルしてエントリ内のより軽量なオブジェクトを作成することができます

Entry.s = set.get()...

于 2012-05-22T15:19:56.787 に答える
0

並べ替えが完了したときにすべての値を使用するかどうかはわかりません。しかし、5000 万という数字は、並べ替え後に上位の X 値を取得して、それらで何かを行う可能性があるというヒントを与えてくれます。

その場合：最小ヒープを使用するだけで、ヒープの上部よりも大きい数値に遭遇するたびに、ヒープから最小を削除して新しい数値を追加します。この方法では、すべての数値をメモリに保持する必要はなく、そのうちの X だけを保持する必要があります。

于 2012-05-27T11:06:01.910 に答える
0

データのチャンクを並べ替えて別のファイルに書き込み、それらのファイルにマージ並べ替えを適用することで、これを解決したいと 思います。

于 2012-05-23T04:33:53.630 に答える