1

リストから各アイテムを取得し、それを別のリスト内の他のすべてのアイテムと比較するプログラムがあります。これまでのところ問題なく動作していますが、データが大きくなり、システム メモリを超えようとしています。

非常に大きな 2 つのリスト (各リストが 5 ~ 10 GB 程度) を比較する最良の方法は何だろうか。

これは私がやっていることの非常に簡単な例です (リストが巨大で、for ループの値が実際に処理/比較されていることを除いて)。

import java.util.Collection;
import java.util.HashSet;
import java.util.Arrays;

public class comparelists {
    public static void main( String  [] args ) {
        String[] listOne = {"a","b",
                "c","d",
                "e","f",
                "g","h",
                "i","j",
                "k","l"};

        String[] listTwo = {"one",
                "two",
                "three",
                "four",
                "five","six","seven"};

        for(int listOneItem=0; listOneItem<listOne.length; listOneItem++){
            for (int listTwoItem=0; listTwoItem<listTwo.length; listTwoItem++) {
                System.out.println(listOne[listOneItem] + " " + listTwo[listTwoItem]);
            }
        }

    }
}

メモリに収まらないため、ここにはいくつかのディスク IO が必要であることに気付きました。私の最初のアプローチは、両方のリストをファイルとして保存し、listOne から一連の行を保存してから、listTwo のファイル全体をストリーミングしてから、さらにいくつかの行を取得することでした。 listOneなどから。より良い方法はありますか?または、上記のようにリストにアクセスするJavaの方法ですが、必要に応じてディスクにスワップしますか?

4

3 に答える 3

2

ビッグ データをフラット ファイルに配置し、ファイルから一度に 1 つのデータ項目をストリーミングできます。この方法では、常に 2 つのデータ項目のみがメモリ内に存在します。

明らかに、これは効率性の賞を獲得するつもりはありませんが、テキスト ファイルの 1 行に 1 つの項目を含むデータ ファイルを使用する簡単な例を次に示します。

BufferedReader readerA = new BufferedReader(new FileReader("listA.txt"));
String lineA;
while ((lineA = readerA.readLine()) != null)
{
    BufferedReader readerB = new BufferedReader(new FileReader("listB.txt"));
    String lineB;
    while ((lineB = readerB.readLine()) != null)
    {
        compare(lineA, lineB);
    }
    // TODO: ensure .close() is called on readerB
}
// TODO: ensure .close() is called on readerA

処理しているデータが複雑すぎてテキスト ファイルに 1 行に 1 項目を簡単に格納できない場合は、ObjectInputStream と ObjectOutputStream を使用して同様のことを行うことができます。これらは、一度に 1 つの Java オブジェクトを読み書きしてファイルに書き込むことができます。

listB をメモリに収めることができれば、最初のループ内でかなりのディスク アクセスを節約できることは明らかです。十分な重複データがある場合、メモ化は listB をメモリに収めるのに役立つ場合があります。

また、アイテムの比較は教科書的な例であり、並列化を使用して高速化できる問題です。たとえば、ファイル読み取りスレッドがディスクからのスループットを最大化することに集中できるように、データ比較作業をワーカー スレッドに渡します。

于 2012-11-12T18:07:29.590 に答える
0

2 つの非常に大きなリストのデカルト積に対して何かを実行しようとしていることがわかります。

そして、あなたが心配している非効率性は、リストをファイルからメイン メモリに読み込む時間だと思います。

リストをメモリにロードできるブロックに分割するのはどうですか。l1[0]の最初の 1000 項目のリストl1l1[1]あり、次の 1000 項目のリストであるとします。

次に、比較します。

l1[0] with l2[0]
l1[0] with l2[1]
l1[0] with l2[2]
...
l1[0] with l2[0]
l1[1] with l2[1]
l1[2] with l2[2]
...

ファイルからの読み取りを減らして、同じ全体的な効果を達成します。

于 2012-11-12T18:04:58.613 に答える
0

Flyweight パターンを使用します。ここにリンクがあります:

http://en.wikipedia.org/wiki/Flyweight_pattern

于 2012-11-12T17:39:03.387 に答える