在Java中表示上三角矩阵的最佳数据结构是什么？

Question

假设给出了一个上三角整数矩阵.在Java中存储它的最佳方法是什么？天真的2d int数组显然效率不高.我提出的解决方案已移至答案部分.

Answer 1

如果您想节省内存，您的解决方案看起来很棒 - 它被称为打包存储矩阵。逐列、自上而下，您的数组将如下所示：1 2 6 3 7 8 4 1 9 5

\n\n

我建议根据总和公式(n\xc2\xb2 + n) / 2（行和列从零开始）对索引进行更简单的计算。

\n\n

list_index = (column^2 + column) / 2 + row;\n

\n\n

一个实现可能如下所示：

\n\n

public class TriangularMatrix {\n    private final int[] list;\n\n    public TriangularMatrix(int size) {\n        list = new int[sumFormula(size)];\n    }\n\n    public int set(int row, int column, int value) {\n        validateArguments(row, column);\n\n        int listIndex = getListIndex(row, column);\n        int oldValue = list[listIndex];\n        list[listIndex] = value;\n\n        return oldValue;\n    }\n\n    public int get(int row, int column) {\n        validateArguments(row, column);\n\n        return list[getListIndex(row, column)];\n    }\n\n    private void validateArguments(int row, int column) {\n        if (row > column) {\n            throw new IllegalArgumentException("Row (" + row + " given) has to be smaller or equal than column (" + column + " given)!");\n        }\n    }\n\n    private int getListIndex(int row, int column) {\n        return sumFormula(column) + row;\n    }\n\n    private int sumFormula(int i) {\n        return (i*i + i) / 2;\n    }\n}\n

\n\n

SO 上还有另一个问题讨论（负面）性能影响，尽管它是关于 Fortran 的。

\n

Answer 2

我想我找到了解决方案。这是我的解决方案：假设你有一个 4X4 上三角矩阵 M。

1 2 3 4
0 6 7 1
0 0 8 9
0 0 0 5

如果您可以将 M 的每个元素映射到一维数组中，那就是最好的解决方案。您需要知道的只是知道矩阵的哪个 [row,col] 对应于一维数组的哪个元素。以下是你如何施展魔法：

start_index=((col_index-1)+1)+((col_index-2)+1)+...+1
end_index=start_index + col_index

例如：如果我想查找矩阵第三列的元素在数组中的位置：

start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6
end_index=6+3=9

因此，我需要做的就是从数组的索引 6 开始，读取索引 9 之前的所有元素（包括第 9 个元素）。按照此过程，您可以在 (n + n^2)/2 空间中存储和检索 nXn 矩阵的所有单元格。