java - 通过 Java 中的键聚合文件中的键值行

Question

我有一个巨大的文件，由约 8 亿行 (60g) 组成。行可以是重复的，由一个 id 和一个值组成。例如:

id1   valueA
id1   valueB 
id2   valueA 
id3   valueC
id3   valueA
id3   valueC

注意:ID 没有像示例中那样按顺序(和分组)。

我想通过键聚合行，以这种方式:

id1   valueA,valueB
id2   valueA
id3   valueC,valueA

有 5000 个可能的值。

该文件不适合内存，所以我不能使用简单的 Java 集合。 此外，大部分行都是单一的(例如 id2)，它们应该直接写在输出文件中。

出于这个原因，我的第一个解决方案是对文件进行两次迭代:

• 在第一次迭代中，我存储了两个结构，只有 ID，没有值:
  • 单值 ID (S1)
  • 多值 id (S2)
• 在第二次迭代中，从内存中丢弃单值 id (S1) 后，我可以直接将单值 id-value 对写入输出文件，检查它们是否不在多值 id 中 (S2)

问题是由于内存限制，我无法完成第一次迭代。

我知道这个问题可能会以多种方式出现(键值存储、map reduce、外部排序)。

我的问题是什么方法可以更适应使用和快速实现？这是一个只有一次的过程，我更喜欢使用 Java 方法(而不是外部排序)。

Answer 1

如前所述(这很快!)，合并排序是一种方法。具体来说，按 id 在本地排序，例如，每 100 万行。然后将本地排序的行保存到更小的文件中。然后重复地将较小的、已排序的文件成对合并为一个大的已排序文件。您可以在合并较小的文件时进行聚合。

直觉是，当您合并 2 个排序列表时，您维护 2 个指针，每个列表一个，并在进行排序时进行排序。您无需加载完整列表。这允许您缓冲大文件并立即缓冲合并结果。

这是在内存中排序并输出到文件的示例代码:

private void sortAndSave(List<String> lines, Path fileOut) throws IOException {
    Collections.sort(lines, comparator);
    Files.write(fileOut, lines);
}

这是在本地排序并将结果保存到较小文件中的示例代码:

// Sort once we collect 1000000 lines
final int cutoff = 1000000;
final List<String> lines = new ArrayList<>();
int fileCount = 0;
try (BufferedReader reader = Files.newBufferedReader(fileIn, charset)) {
    String line = reader.readLine();
    while (line != null) {
        lines.add(line);
        if (lines.size() > cutoff) {
            fileCount++;
            sortAndSave(lines, Paths.get("fileOut" + fileCount));
            lines.clear();
        }
        line = reader.readLine();
    }
    if (lines.size() > 0) {
        fileCount++;
        sortAndSave(lines, fileOut, Paths.get("fileOut" + fileCount));
    }
}

这是合并排序 2 个文件的示例代码:

try (BufferedReader reader1 = Files.newBufferedReader(file1, charset);
     BufferedReader reader1 = Files.newBufferedReader(file2, charset);
     BufferedWriter writer = Files.newBufferedWriter(fileOut, charset)) {
    String line1 = reader1.read();
    String line2 = reader2.read();
    while (line1 != null && line2 != null) {
        if (comparator.compare(line1, line2) < 0) {
            writer.write(line2);
            line2 = reader2.read();
        } else {
            writer.write(line1);
            line1 = reader1.read();
        }
    }
    if (line1 != null) {
        // TODO: Merge in the remaining lines of file1
    } else if (line2 != null {
        // TODO: Merge in the remaining lines of file2
    }
}