Разреженная матрица: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
м →Представление: орфография |
мНет описания правки Метка: редактор вики-текста 2017 |
||
Строка 13:
== Представление ==
Существует несколько способов хранения (представления) разреженных матриц, отличающиеся:
* удобством изменения структуры матрицы (активно используется косвенная адресация) - это структуры в виде списков и словарей.
* скоростью доступа к элементам и возможной оптимизацией матричных вычислений (чаще используются плотные блоки - массивы, увеличивая локальность доступа к памяти).
'''Словарь по ключам (DOK - Dictionary of Keys)'''
строится как словарь, где ключ это пара (''строка, столбец''), а значение это соответствующий строке и столбцу элемент матрицы.
'''Список списков (LIL - List of Lists)'''
строится как список строк, где ''строка'' это список узлов вида (''столбец, значение'').
'''Список координат (COO - Coordinate list)'''
хранится список из элементов вида (строка, столбец, значение).
'''Сжатое хранение строкой (CSR - compressed sparse row, CRS - compressed row storage, Йельский формат)'''
Мы представляем исходную матрицу <math>M^{n\times m}</math>, cодержащую <math>N_{NZ}</math> ненулевых значений в виде трёх массивов:
Строка 40 ⟶ 37 :
* ''массив значений'' - массив размера <math>N_{NZ}</math>, в котором хранятся ненулевые значения взятые подряд из первой непустой строки, затем идут значения из следующей непустой строки и т.д.
* ''массив индексов столбцов'' - массив размера <math>N_{NZ}</math> и хранит номера столбцов, соответствующих элементов из ''массива значений.''
* ''массив индексации строк'' - массив размера <math>n+1</math> (кол_во_строк + 1), для индекса <math>i</math> хранит количество ненулевых элементов в строках до <math>i - 1</math> включительно, стоит отметить что последний элемент ''массива индексации строк'' совпадает с <math>N_{NZ}</math>, а первый всегда равен <math>0</math>.первой
Примеры:
| |||