Java:从文本文件读取约 2 亿条边到内存的最快方法？

Question

我有一个包含 2 亿条边的文本文件，其形式为:

12 34
12 920

指示从节点 12 到节点 34 的边。它们需要以允许轻松访问相邻边列表的方式存储在内存中，以便快速查找连接到给定顶点的每条边。

我使用 HashMap 来存储节点，每个节点只包含一个链接列表:

public class Node {
    List<Node> links;

    public synchronized void AddLink(Node node)
    {
        if (links.indexOf(node) == -1)
            links.add(node);
    }
}

我还使用 BufferedReader.readLine() 从文本文件中读取每一行。问题是，这种方法大约需要 85 秒才能读取所有 2 亿条边。

30 小时后，我目前倾向于相信这些速度在 Java 中是不可能的。有没有我没有看到的更快的实现？

Answer 1

这个问题很有趣。如果您能提供更多信息就更好了。

您忽略的一个重要点是，您将在什么样的机器上实现该目标？它有多少内存？ CPU 的速度有多快？有多少核心？ I/O 有多快？

但无论如何，这里有一些可能有帮助的分析。如果您可以提供更多信息，那么我们就可以分析更多信息。

1.内存

(已修改，我在第一个答案中犯了一个错误。我没有注意到你使用了 ArrayList)

所以你正在使用ArrayList的HashMap。但这并不能保证内存开销。

假设Integer和int是4个字节，而引用是8个字节(我在这里很可能是错的，只是把它当作一个指针)。

在最好的情况下，假设只有一个顶点链接到所有其他顶点，并且该顶点是文件中的第一个数字。那么内存就是 200M * 8 字节 = 1.6 GB。

但在最坏的情况下，仍然有一个顶点链接到其他顶点，但现在该顶点是文件中的第二个数字。那么内存将为 200M * 20 字节 = 4 GB。

最坏情况的原因是，浏览了一下Java HashMap的source code ，HashMap的每个节点/条目都包含这些字段。

final int hash;
final K key;
V value;
Node<K,V> next;`

2.数据结构

就像其他人已经说过的那样，您需要关心数据结构。 HashMap 可能适合也可能不适合这里。

所有顶点都事先已知吗？例如，所有顶点都从 0 到 20K。在这种情况下，鉴于这个大数据集，我不会使用 HashMap。相反，我会使用列表的列表，这将每个节点的内存从 20 字节显着减少到仅 4 字节。这样我只需要 800MB 内存!

但是，如果顶点分布在整数空间上，则此方法不可行。但是，您仍然可能无法正确使用数据结构。你初始化的HashMap有足够的容量吗？当 HashMap 比较满时，必须重新哈希，这是非常昂贵的。同样，你初始化ArrayList时是否有足够的容量？ ArrayList 在满时必须调整大小，这也是有成本的。

最后，我注意到您使用了 SynchronizedMap，这对于您的情况来说确实是一个糟糕的主意。 SynchronizedMap 只是一个围绕 HashMap 的互斥锁，当多个线程同时修改 HashMap 时，它会锁定整个 HashMap，这意味着代码中没有并行性。相反，您应该使用 ConcurrentHashMap，它的粒度比 SynchronizedMap 小得多。直观的解释是，它只锁定正在修改的链表，因此现在如果多个线程修改不同的链表，那么它们可能会并行执行此操作。

3.阅读方法

为了读取这个大文件，您可能需要 checkout readLine 以外的方法。其他人已经指出了 nio 包中的 FileChannel 。还结账MappedByteBuffer .

结论

总之，除非您分享您的环境和数据模式，否则很难提供真正的建议。优化通常基于特定场景，而不是通用的。