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

Question

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

Answer 1

如果您想节省内存，您的解决方案看起来很棒 - 它称为 packed storage matrix .逐列自上而下，您的数组将如下所示: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;
    }
}

有another question on SO讨论(负面)性能影响，尽管它是关于 Fortran 的。