在C++中壓縮對稱矩陣

Question

讓我們假設我們有一個simmetric矩陣。

A= 
    1 2 3 
    2 6 4 
    3 4 5 

現在，因爲它是simmetric，我們不需要存儲記住所有的數字。我們假設將0放在左下三角形的單元格中。

B = 
    1 2 3 
    0 6 4 
    0 0 5 

，如果我想要訪問B中的所有我需要做的0元素的含量爲反轉行和興趣細胞的山坳：

if(i>j) val += L[j][i] // ex: B[1][0] is stored in B[0][1] 

（讓我們假設我們的目標是總結所有非存儲元件）

在這一點上，我們只使用右上角的三角形，但我們實際上並沒有節省內存，因爲未使用的元素仍然以0值分配。

一個的方式來保存存儲器是使用向量的向量：

vector<vector<int>> C; 

，並相應地調整每一行。

C= 
    1 2 3 
    6 4 
    5 

通過這樣艱難的，我們不能用交換技巧了，因爲你可能會注意到，現在空元素在矩陣底部直角三角形。

未分配的值即可：

D= 
    x x x 
    x x 2 
    x 3 4 

在這種情況下

我們感興趣的是可以用這個，如果條件被發現的元素：

if(j >= size - i) 

現在的問題是確定正確的內容的0個元素。換句話說：

if(j >= size - i) ans += L[?][?] 

所以，例如，如果我在I = 1 J = 2我不應該訪問該元件[1] [2]，而是爲[0] [2] = 2（依此類推[2] [1] - > [0] [2] = 3，[2] [2] - > [1] [1] = 4）。

怎麼可能實現呢？

Answer 1

您特定的問題可以通過將左下的三角形和丟棄右上角的三角形來解決：

1 
2 6 
3 4 5 

的索引操作可以實現爲：

int operator()(int r, int c) const { return r >= c ? L[r][c] : L[c][r]; } 

如果你真的要矩陣的右上三角存儲轉移的方式，你提出（見ç），那麼你就可以訪問矩陣元素：

int operator()(int r, int c) const { return c >= r ? L[r][c-r] : L[c][r-c]; } 

但是，如果你真的想從您的壓縮一定的利潤，我建議包裝整個三角形在一個一維向量。具有矢量矢量反而會增加相當的開銷。

Answer 2

要將這樣的三角形數組存儲在壓縮的線性向量中，我使用了下面的類。

#define ogf_array_check(index, data_size) assert(index < data_size) 
#define ogf_assert(b) assert(b) 
    /** 
    * A 2d array of values aij where only the cells such 
    * that j <= i are represented. 
    */ 
    template <class T> class TriangularArray { 
    public: 
     typedef TriangularArray<T> thisclass ; 

     TriangularArray(int size) : size_(size), data_size_(size * (size + 1)/2) { 
      data_ = new T[data_size_] ; 
     } 
     ~TriangularArray() { delete[] data_; data_ = nil ; } 

     int size() const { return size_ ; } 
     int data_size() const { return data_size_ ; } 

     /** 
     * index0 denotes the line, and index1 the column, 
     * note that index1 should be less-than or equal to 
     * index0. 
     */ 
     T& operator()(int index0, int index1) { 
      ogf_array_check(index0, size_) ; 
      ogf_array_check(index1, size_) ; 
#ifdef OGF_ARRAY_BOUND_CHECK 
      ogf_assert(index1 <= index0) ; 
#endif 
      int offset = index0 * (index0 + 1)/2 ; 
      return data_[offset + index1] ; 
     } 

     /** 
     * index0 denotes the line, and index1 the column, 
     * note that index1 should be lerr or equal to 
     * index0. 
     */ 
     const T& operator()(int index0, int index1) const { 
      ogf_array_check(index0, size_) ; 
      ogf_array_check(index1, size_) ; 
#ifdef OGF_ARRAY_BOUND_CHECK 
      ogf_assert(index1 <= index0) ; 
#endif 
      int offset = index0 * (index0 + 1)/2 ; 
      return data_[offset + index1] ; 
     } 

     void set_all(const T& value) { 
      for(int i=0; i<data_size_; i++) { 
       data_[i] = value ; 
      } 
     } 

     T& from_linear_index(int index) { 
      ogf_array_check(index, data_size_) ; 
      return data_[index] ; 
     } 

     const T& from_linear_index(int index) const { 
      ogf_array_check(index, data_size_) ; 
      return data_[index] ; 
     } 

     T* data() const { return data_ ; } 

    private: 
     T* data_ ; 
     int size_ ; 
     int data_size_ ; 

    private: 
     TriangularArray(const thisclass& rhs) ; 
     thisclass& operator=(const thisclass& rhs) ; 
    } ;