代表較低/較高三角形矩陣的有效方法

Question

我正在處理2維C/C++程序中的數據。在這裏，我的值是按成對計算的，這裏的值將與foo[i][j]和foo[j][i]相同。

因此，如果我通過使用一個簡單的二維數組來實現它，我的一半空間將被浪費。那麼什麼是最好的數據結構來表示這個下/上三角矩陣。

問候，

Answer 1

真的，你最好只使用普通的二維矩陣。 RAM很便宜。如果你真的不想這樣做，那麼你可以用適當數量的元素構建一個一維數組，然後找出如何訪問每個元素。例如，如果陣列的結構是這樣的：

j 
    1234 
i 1 A 
    2 BC 
    3 DEF 
    4 GHIJ 

，並已經將它保存爲一個維數組，左到右，你會用array[3]訪問元素C(2, 2)。你可以制定一個功能從[i][j]到[n]，但我不會破壞你的樂趣。但是，除非所涉及的三角陣列真的很大，否則你不必這樣做，或者你非常關心空間。

Answer 2

使用交錯數組：如果你有N項，然後下三角陣無主對角線將有

int N; 
// populate N with size 

int **Array = new Array[N]; 
for(int i = 0; i < N; i++) 
{ 
    Array[i] = new Array[N - i]; 
} 

它會創建數組一樣

0 1 2 3 4 5 
0 [   ] 
1 [   ] 
2 [  ] 
3 [  ] 
4 [ ] 
5 [ ] 

Answer 3

（N - 1）* N/2個元素，或者具有主對角線的（N + 1）* N/2個元素。沒有主對角線，（I，J）（I，J∈0..N-1，I> J）⇒（I *（I-1）/ 2 + J）。在主對角線上，（I，J∈0..N-1，I≥J）⇒（（I + 1）* I/2 + J）。

（是的，當你是一個2.5千兆字節的機器上分配4千兆字節，削減一半併產生巨大的變化。）

Answer 4

在一個代表獨特的元素，男，所需的數N乘N對稱矩陣：

隨着主對角線

m = (n*(n + 1))/2

沒有對角線（對稱矩陣作爲OP描述，主對角線是必要的，但只是爲了好的措施...）

m = (n*(n - 1))/2。

如果使用帶截斷的整數運算，則不用2除以直到最後一個操作非常重要。

您還需要進行一些算術運算，以在對應於對角矩陣中的行x和列y的分配內存中查找索引i。

在分配的存儲器索引i，x行和列中的Y上對角矩陣的：

隨着對角線

i = (y*(2*n - y + 1))/2 + (x - y - 1) 

沒有對角線

i = (y*(2*n - y - 1))/2 + (x - y -1) 

對於下面的對角矩陣在方程中翻轉x和y。對於對稱矩陣，只需在內部選擇x> = y或y> = x，並根據需要使成員函數翻轉。

Answer 5

Riffing上丹妮的回答......

不是分配不同大小的許多陣列，這可能導致內存碎片或怪異的高速緩存訪​​問模式，你可以分配一個數組來保存數據和一個小數組在第一次分配中保持指向行的指針。

const int side = ...; 
T *backing_data = new T[side * (side + 1)/2]; // watch for overflow 
T **table = new T*[side]; 
auto p = backing_data; 
for (int row = 0; row < side; ++row) { 
    table[row] = p; 
    p += side - row; 
} 

現在你可以使用table好像它是一個鋸齒狀排列如圖丹妮的回答是：

table[row][col] = foo; 

但是，所有的數據是在一個單一的塊，它可能無法以其他方式取決於你的分配器的策略。

使用行指針表可能比也可能不會比使用Praxeolitic公式計算偏移更快。

Answer 6

在阿德里安McCarthy的答案，與

p += row + 1; 

取代

p += side - row; 

爲下三角矩陣，而不是上面的一個。

Answer 7

由於Dan和Praxeolitic提出了具有對角線但具有校正過渡規則的下三角矩陣。

對於n乘n的矩陣，您需要數組(n+1)*n/2長度和過渡規則爲Matrix[i][j] = Array[i*(i+1)/2+j]。

#include<iostream> 
#include<cstring> 

struct lowerMatrix { 
    double* matArray; 
    int sizeArray; 
    int matDim; 

    lowerMatrix(int matDim) { 
    this->matDim = matDim; 
    sizeArray = (matDim + 1)*matDim/2; 
    matArray = new double[sizeArray]; 
    memset(matArray, .0, sizeArray*sizeof(double)); 
    }; 

    double &operator()(int i, int j) { 
    int position = i*(i+1)/2+j; 
    return matArray[position]; 
    }; 
}; 

我做到了與double，但你可以把它作爲template。這只是基本的骨架，所以不要忘記實施析構函數。