使用共享序列存储和访问整数列表的最有效方法 （Java）

问：

这个问题与此非常相似，除了在 Java 中。

我正在处理 2D 地图数据，其中节点表示为整数，每条边都具有正的遍历成本。我需要存储和访问图中每个节点对（从 200 到 250k 个节点）之间的最快路径节点序列（路由）。路线信息不会随时间而改变。在一次程序运行中，我需要访问这些数据大约 1 亿次，因此访问效率与存储效率一样重要。

我已经预先计算了（感谢 Python）：

• 从每个源节点，前一个节点到目的地，沿路线：ijk
• 和 之间的路线的（时间）成本：ijc(i,j)

由此，我可以很容易地预先计算 和 通过跟踪节点从 返回 到 。然而，即时执行此操作的效率非常低，因为我们经常重复相同的构造过程。ijkji

因此，我（相信我）需要预先计算并存储每对和的最快路径节点序列。我实现了以下内容，这两个都太占用内存了：ij

• Map<origin, Map<destination, LinkedList<Integer>>>
• LinkedList<Integer>[origin][destination]

其中 a 表示起点和终点之间的路线。LinkedList<Integer>ij

我高度怀疑许多路由都包含共同的子序列。在 Java 中，有没有一种方法可以识别（通过预计算或其他方式）这些常见的子序列，从而大大减少存储路由集合所需的内存，同时保持访问效率？例如，要遍历 N 元树 （from to ），其中每个节点都是路由的唯一子序列或公共子序列？ij