Сжатие симметричной матрицы в C++

Question

давайте предположим, что у нас есть симметричная матрица.

A= 
    1 2 3 
    2 6 4 
    3 4 5 

сейчас, так как это симметрично, нам не нужно запоминать все числа в нем. Предположим положить 0 в ячейки левого нижнего треугольника.

B = 
    1 2 3 
    0 6 4 
    0 0 5 

, если я хочу, чтобы получить доступ к содержимому 0 элементу B все, что нужно сделать, это инвертировать строку и столбец заинтересованной ячейки:

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[?][?] 

так, например, если я нахожусь в = 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]; } 

Если вы действительно хотите сохранить верхний правый треугольник матрицы сдвинутым образом, как вы предлагаете (см. C), тогда вы можете получить доступ к элементам матрицы как:

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) ; 
    } ;