Сжатие симметричной матрицы в переполнении стека
давайте предположим, что у нас есть симметричная матрица.
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:
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).
как это возможно?
Решение
Ваш конкретный вопрос может быть решен путем сохранения нижнего левого треугольника и отбрасывания верхнего правого треугольника:
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]; }
Однако, если вы действительно хотите получить некоторую прибыль от сжатия, я бы посоветовал упаковать весь треугольник в один одномерный вектор. Наличие вектора векторов вместо этого добавляет довольно накладные расходы …
Другие решения
Чтобы хранить такие треугольные массивы в сжатом линейном векторе, я использую следующий класс.
#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) ;
} ;