java - 邻接表最有效的实现？

Question

我想用 Java 创建一个邻接列表，因为稍后我将获得大量节点作为输入，所以它需要非常高效。

哪种实现方式最适合这种情况？

列表的列表或者可能是 map ？我还需要在某处保存边缘权重。我不知道如何做到这一点，因为邻接列表本身显然只是跟踪连接的节点，而不是边权重。

Answer 1

警告:此路线是最受虐且最难维护的路线，仅在需要最高性能时才推荐。

邻接表是最难优化的数据结构之一，主要是因为它们的大小从一个顶点到下一个顶点都不同。在某些广泛的概念层面上，如果您将邻接数据包含在 Vertex 或 Node 定义中，那么这就使得 Vertex/Node 的大小变量。在大多数编程语言中，可变大小的数据和缓存友好所需的内存连续性往往会相互冲突。

大多数面向对象的语言并不是为了处理实际大小不同的对象而设计的。他们通过让它们指向/引用其他地方的内存来解决这个问题，但这会导致更高的缓存未命中率。

如果您想要尖端效率并且经常遍历相邻顶点/节点，那么您需要一个顶点及其对相邻邻居的可变数量的引用/索引(以及您的情况下的权重)以适合单个缓存行，并且很可能其中一些相邻顶点也适契约(Contract)一缓存行(尽管解决此问题并重新组织数据以将 2D 图映射到 1 维内存空间是一个 NP 困难问题，但现有启发式方法有很大帮助)。

因此，问题不再是使用什么数据结构，而是使用什么内存布局。数组是你的 friend ，但不是节点数组。您需要一个字节数组来连续打包节点数据。像这样的事情:

[node1_data num_adj adj1 adj2 adj3(可能有一些用于对齐和避免跨接的填充)node2_data num_adj adj1 adj2 adj3 ...]

这里的节点插入和删除开始类似于实现内存分配器的算法。当您连接一条新边时，实际上会更改节点的大小以及它在这些巨大的连续内存块中的位置。与内存分配器不同，您可能可以重新整理、压缩和整理数据，前提是您可以更新对数据的引用/索引。

现在，只有当您想要最快的解决方案，并且您的用例主要侧重于读取操作(评估、遍历)而不是写入操作(连接边、插入节点、删除节点)时，才可以这样做。否则，这完全是矫枉过正，而且是一个完整的 PITA，因为你将失去所有良好的面向对象结构，这些结构有助于使代码易于维护、重用等。这会让你消除所有结构，以利于处理细节和字节级别，只有当您的软件处于其质量与该图的效率成正比的领域时，才值得这样做。