比较两个非常大的列表(不适合内存)的最佳方法是什么？

Question

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

我想知道比较两个非常大的列表(每个列表可能有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方式访问列表，就像我上面所做的那样，但是可以根据需要交换到磁盘？

Answer 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

如果您正在处理的数据太复杂，不能很容易地在文本文件中每行存储一项，那么您可以使用ObjectInputStream和ObjectOutputStream做类似的事情，它们可以一次读写一个文件。

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

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

Answer 2

使用Flyweight模式。这里有一个链接：

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

Answer 3

我可以看到你的目标是在2个非常大的列表的Cartesian product上执行一些事情。

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

如何将列表划分为可加载到内存中的块。假设l1[0]是l1中前1000项的列表，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]
...

以更少的文件读取获得相同的总体效果。