*Разрежённая матрица* -- матрица с преимущественно нулевыми элементами. В противном случае, если большая часть
элементов матрицы ненулевая, матрица считается *плотной*.
Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно
к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти.
Однако в разрежённых матрицах можно хранить и обрабатывать только ненулевые элементов,
что снижает требования к памяти и позволяет использовать более эффективные алгоритмы.
--
1. Словарь по ключам: ``map<pair<int,int>, double> A;``
2. Список списков: ``vector<list<pair<int,double>>> A;``
3. Список координат: ``list<tuple<int,int,double>> A;``
4. Сжатое хранение строкой (столбцом):
* массив значений ``vector<double> Anz``, в котором хранятся ненулевые значения, из первой строки, затем из следующей и т. д.
* массив индексов столбцов ``vector<int> Acol``, который хранит номера столбцов соответствующих элементов из массива значений.
* массив индексации строк ``vector<int> Arow(n+1)``, который хранит начальные индексы элементов строк в ``Anz`` и ``Acol``.
Рекомендуется упорядочивать элементы в списках по возрастанию индексов, тогда операции над разрежёнными матрицами будут выполняться более эффективно по следующим причинам: 1) можно применить слияние двух упорядоченных последовательностей, работающее за линейное время; 2) результат слияния также упорядочен, поэтому можно добавлять значения в конец списка значений результирующей матрицы.
Начало
Учебные материалы