Java大型数据结构用于存储矩阵

Question

我需要存储一个二维矩阵，其中包含邮政编码和它们之间的距离（以公里为单位）。我的客户有一个计算距离的应用程序，然后将其存储在Excel文件中。目前有952个地点，所以该矩阵将有952x952 = 906304个条目。

我尝试将其映射到HashMap [Integer，Float]中。整数是两个地点的两个字符串的哈希代码，例如“A”和“B”。浮点值是它们之间的距离（以公里为单位）。

填充数据时，我遇到了OutOfMemoryExceptions，仅在205k条目后。你有什么建议如何聪明地存储这些数据吗？我甚至不知道将整个数据集放入内存中是否明智。我的选项是SQL和MS Access...

问题是我需要非常快速且可能经常访问数据，这就是为什么我选择了HashMap，因为它在查找方面的运行时间复杂度为O（1）。

谢谢你的回复和建议！

Marco

- Marco

Answer 1

使用二维数组会更加节省内存。 您可以使用一个小的哈希表将952个位置映射到0到951之间的数字。 然后，只需要执行以下操作：

float[][] distances= new float[952][952];

要查找东西，只需使用两个哈希查找将这两个地方转换为两个整数，并将它们用作2D数组中的索引。

通过这种方式，您可以避免浮点数的封装，以及大型哈希映射的内存开销。

但是，906304实际上并不是很多条目，您可能只需要增加Xmx最大堆大小。

- Chi

---

由于 distance(a, b) == distance(b, a)，您可以使用三角矩阵来进一步减少50%的内存使用。 - Stephen C

根据CPerkins的答案，“哈希查找”以获取整数应该是HashMap<String,Integer>，其中包含952个邮政编码作为其键，分配从0到951的整数。 - Stephen Denne

Answer 2

我会认为你可以即时计算距离。可能已经有人做过了，所以你只需要找出他们使用的算法和输入数据，例如每个邮政编码的中心点的经度/纬度。

编辑：有两种常用的算法可用于查找由经度/纬度对给定的两点之间的（近似）大圆距离。

• Vincenty公式基于椭球近似。 它更准确，但实现起来更复杂。

• Haversine公式基于球面近似。 它不太准确（0.3％），但实现起来更简单。

- Stephen C

---

请注意，这些可能是（举个例子）驾驶距离。如果是这样的话，数值将需要从地图等来源获取，并不是一个相对简单的几何推导（顺便一提，我意识到问题没有明确说明）。 - Brian Agnew

ZIP代码之间的驾车距离是比ZIP代码之间的大圆距离更模糊的概念。如果您走这条路，您可能需要在特定位置之间获得驾车距离...并且简单的查找表可能不足以胜任。 - Stephen C

我们使用客户已经在使用的应用程序来计算距离。所以我需要处理这些该死的Excel表格 :) 但是这些算法看起来非常有趣！ - Marco

@Marco - 你仍然可以劝说客户告诉你原始坐标... - Stephen C

Answer 3

您是否可以简单地增加JVM可用的内存？

java -Xmx512m ...

默认情况下，最大内存配置为64Mb。这里有一些更多的调优技巧。如果你能够做到这一点，你就可以将数据保持在进程中，最大化性能（即不需要即时计算）。

- Brian Agnew

---

我要指出的是，这不是一个通用解决方案。例如，在英国有数百万个邮政编码（相当于美国的ZIP代码）。 - Stephen C

Answer 4

我点赞Chi和Benjamin的答案，因为他们告诉了你需要做什么，但是在这里我想强调，直接使用两个字符串的哈希码会让你陷入麻烦。你很可能会遇到哈希冲突的问题。

如果你将这两个字符串进行拼接（注意使用一个不能出现在位置标识符中的分隔符），并让HashMap发挥其作用，那么这将不会是一个问题，但是你提出的方法，即使用两个字符串的哈希码作为键，这会让你陷入麻烦。

- CPerkins

Answer 5

最近我在我的硕士论文中处理了类似的需求。

我最终使用了一个矩阵类，它使用了 double[] 而不是 double[][]，以减轻双重引用成本（data[i] 是一个数组，然后是 array[i][j] 是一个 double），同时允许虚拟机分配一个大的、连续的内存块：

public class Matrix {

    private final double data[];
    private final int rows;
    private final int columns;

    public Matrix(int rows, int columns, double[][] initializer) {
        this.rows = rows;
        this.columns = columns;
        this.data = new double[rows * columns];

        int k = 0;

        for (int i = 0; i < initializer.length; i++) {
            System.arraycopy(initializer[i], 0, data, k, initializer[i].length);
            k += initializer[i].length;
        }
    }

    public Matrix set(int i, int j, double value) {
        data[j + i * columns] = value;
        return this;
    }

    public double get(int i, int j) {
        return data[j + i * columns];
    }
}

这个类应该比 HashMap 使用更少的内存，因为它使用了一个原始数组（不需要装箱）：它只需要906304 * 8〜8 Mb（对于double）或906304 * 4〜4 Mb（对于float）。我的意见。

NB 为简单起见，我省略了一些健全性检查。

- dfa

Answer 6

你需要更多的内存。在启动Java进程时，请使用以下命令：

java -Xmx256M MyClass

-Xmx定义了最大堆大小，因此这表示该进程可以使用高达256 MB的内存用于堆。如果仍然不够用，请将该数字逐步增加直到达到物理限制。

- Benjamin Cox

Answer 7

关于堆大小的建议是有帮助的。但是，我不确定您是否准确描述了矩阵的大小。

假设您有4个位置。那么您需要评估A->B，A->C，A->D，B->C，B->D，C->D之间的距离。这意味着您的HashMap中有6个条目（4选2）。

这会让我相信您的HashMap的实际最优大小是（952选2）=452,676;而不是952x952=906,304。

当然，这一切都是基于您只存储单向关系（即从A->B，而不是从B->A，因为那是冗余的），而且由于内存空间已经存在问题，我建议您这样做。

编辑：应该说您的矩阵大小不是最优的，而不是说描述不准确。

- Madison Caldwell

Answer 8

Stephen C. 的观点很好：如果距离是直线距离，那么你可以通过实时计算来节省内存。你只需要为 952 个邮政编码的经度和纬度留出空间，然后在需要时使用 Vicenty 公式进行计算即可。这将使你的内存使用量在邮政编码方面为 O(n)。

当然，这种解决方案假设了一些情况，在你的特定情况下可能会被证明是错误的，例如你是否有邮政编码的经度和纬度数据，以及你是否关心直线距离而不是更复杂的驾车路线等。

如果这些假设是正确的，那么用一些计算换取大量内存可能会帮助你在未来扩展数据集时更好地应对。

- Seth

Answer 9

创建一个新类，其中包含2个位置名称的插槽。始终将字母表中第一个名称放在第一个插槽中。为其提供适当的equals和hashcode方法。给它一个compareTo（例如按名称按字母顺序排序）。将它们全部放入数组中。排序。

另外，hash1 = hash2并不意味着object1 = object2。永远不要这样做。这是一种hack方法。

- Mark Bolusmjak