用Java表示上三角矩陣的最佳數據結構是什麼？

Question

假設給出了一個整數上三角矩陣。用Java存儲這個最好的方法是什麼？天真的2d int數組顯然不高效。我提出的解決方案轉移到答案部分。

Answer 1

我想我找到了解決方案。這裏是我的解決方案：假設你有一個4X4的上三角矩陣M.

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

如果你能在一維數組M的每一個元素映射，這是最好的解決方案。所有你需要知道的是知道矩陣的哪個[行，列]對應於你的1d數組中的哪一個元素。這裏是你怎麼做的魔力：

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矩陣的所有單元。

Answer 2

如果矩陣始終是對角線，我會用：

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

如果它是一個稀疏矩陣，我會使用地圖：

Map<Map<Integer>> = ... 

在第二種情況下，您可能需要使用get和set操作將該映射包裝到類中，以便管理對新行和列的訪問。

所有這些都取決於您的需求，您的記憶限制和矩陣大小。

Answer 3

番石榴的Table呢？它是使用HashMaps或TreeMaps（以及需要的2D數組）實現的，但它提供了比定義Map<Integer, Map<Integer, V>>更好的API。

Answer 4

如果你想節省內存，你的解決方案看起來不錯 - 它被稱爲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。