1

我有一个程序，它从列表中获取每个项目并将其与另一个列表中的所有其他项目进行比较。到目前为止它工作正常，但数据越来越大并且将超过系统内存。

我想知道比较两个非常大的列表（每个列表可能 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

您可以将大数据放在平面文件中，然后一次从文件中流式传输一项数据。这样，在任何给定时间只有两项数据在内存中。

显然这不会赢得任何效率奖，但这里有一个简单的例子，它使用的数据文件在文本文件中每行包含一个项目：

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

如果您正在处理的数据太复杂而无法在文本文件中轻松地每行存储一个项目，您可以使用 ObjectInputStream 和 ObjectOutputStream 执行类似的操作，它可以一次读取一个 Java 对象并将其写入文件。

如果您可以设法将 listB 放入内存中，那么显然您会在第一个循环中节省相当多的磁盘访问。如果您有足够的重复数据，记忆化可能会帮助您将 listB 放入内存中。

此外，项目比较是一个教科书示例，一个可以通过使用并行化加速的问题。例如，将数据比较工作交给工作线程，以便文件读取线程可以专注于最大化磁盘的吞吐量。

于 2012-11-12T18:07:29.590 回答
0

使用享元模式。这是一个链接：

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

于 2012-11-12T17:39:03.387 回答
0

我可以看到您的目标是在2 个非常大的列表的笛卡尔积上执行某些操作。

而且我假设您担心的效率低下是将列表从文件读取到主内存的时间。

如何将列表分成可以加载到内存中的块。Sayl1[0]是其中的前 1000 个项目的列表，l1并且l1[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 回答