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

Question

假设给定一个整数的上三角矩阵，最佳的Java存储方式是什么？朴素的二维int数组显然不够高效。我想到的解决方案已经移动到答案部分了。

- user3639557

---

“最好”的定义是什么？灵活性？使用现有的矩阵库之一。性能？使用简单的1D数组。（如果性能真的很关键，而且矩阵很“小”，甚至可以考虑创建一个(rowscols)的数组，并将其左下角留空）。无论如何，我都会避免使用不打算用作矩阵（如“Tables”）的类，或者嵌套数据结构，例如列表中的列表。此外，请注意，对于最后一点性能（即使使用数组），访问模式*也非常重要，以及您是使用行主还是列主存储。 - Marco13

你可以回答自己的问题：将你的解决方案移动到答案中（在本页面的“你的答案”框中键入）。 - Peter O.

@PeterO。谢谢。刚把它移到了答案部分。 - user3639557

Answer 1

如果您想节省内存，您的解决方案看起来很棒 - 它被称为紧缩存储矩阵。按列从上到下，您的数组将如下所示：1 2 6 3 7 8 4 1 9 5 我建议根据总和公式(n² + n) / 2（行和列从零开始）简化计算索引。

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

一个实现可能看起来像下面这样：

public class TriangularMatrix {
    private final int[] list;

    public TriangularMatrix(int size) {
        list = new int[sumFormula(size)];
    }

    public int set(int row, int column, int value) {
        validateArguments(row, column);

        int listIndex = getListIndex(row, column);
        int oldValue = list[listIndex];
        list[listIndex] = value;

        return oldValue;
    }

    public int get(int row, int column) {
        validateArguments(row, column);

        return list[getListIndex(row, column)];
    }

    private void validateArguments(int row, int column) {
        if (row > column) {
            throw new IllegalArgumentException("Row (" + row + " given) has to be smaller or equal than column (" + column + " given)!");
        }
    }

    private int getListIndex(int row, int column) {
        return sumFormula(column) + row;
    }

    private int sumFormula(int i) {
        return (i*i + i) / 2;
    }
}

这里有另一个关于SO讨论性能影响的问题，尽管它是关于Fortran。

- stuXnet

---

我已经解决了上三角矩阵的问题，这正是我所需要的。请看一下并告诉我您的想法。 - user3639557

@user3639557 我修改了回答以适应你的问题——我的第一个版本对于三角矩阵来说并不高效。 - stuXnet

Answer 2

Guava的Table呢？它使用HashMaps或TreeMaps（如果需要，还可以使用2D数组）进行实现，但是它提供了比定义Map>更好的API。请参考Table。

- Natix

Answer 3

如果矩阵始终为对角矩阵，我会使用：

List<List<Integer>> matrix = ...

如果是一个稀疏矩阵，我会使用映射：

Map<Map<Integer>> = ...

在第二种情况下，您可能需要将地图包装在一个具有get和set操作的类中，以便管理对新行和列的访问。

然而，所有这些都取决于您的需求、内存限制和矩阵大小。

- Pablo Francisco Pérez Hidalgo

---

我想出了另一种解决方案，请看一下并告诉我你的想法。 - user3639557

如果您的矩阵始终为三角形，则您的解决方案对于内存使用是正确和最优的。我建议您使用其封装类实现访问器方法，根据（i行，j列）索引直接访问其元素。 - Pablo Francisco Pérez Hidalgo

Answer 4

我认为我找到了解决方案。这是我的解决方案：假设您有一个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矩阵的所有单元格。

- user3639557