Разреженными называют матрицы, в которых количество незаполненных
(пустых, нулевых) ячеек существенно больше, чем заполненных.
Объекты с интерфейсом ImaSparseMatrix предоставляют эффективный
способ хранения и обработки таких матриц.
Интерфейс ImaSparseMatrix поддерживает сразу три представления
разреженной матрицы: поэлементное, построчное и постолбцовое.
Тем самым обеспечивается возможность эффективного перебора
элементов матрицы без обращения к пустым ячейкам.
Рассмотрим эти способы на примере.
Пусть задана разреженная матрица 3×4:
Элементом разреженной матрицы называется непустая ячейка.
Индексами элемента называются его координаты
в исходной матрице (нумерация индексов начинается с нуля).
В нашем примере положение элемента 8 задается парой индексов [0,2].
Всего в матрице имеется 4 элемента.
Поэлементное представление
— это список элементов матрицы,
в котором каждый элемент задан
парой индексов и значением:
[0,1]=9 |
[0,2]=8 |
[2,2]=7 |
[2,3]=6 |
Поэлементное представление используется в тех случаях,
когда надо перебрать все элементы разреженной матрицы,
например, чтобы вычислить сумму или найти максимальный элемент.
Построчное представление
— это список строк матрицы,
в котором каждая строка задана индексом и списком элементов.
Каждый элемент строки представлен индексом столбца и значением:
[0] | [1]=9 | [2]=8 |
[2] | [2]=7 | [3]=6 |
Если в алгоритме требуется перебрать все непустые строки разреженной матрицы,
и в каждой строке перебрать все элементы,
то это типичный случай, когда следует использовать построчное представление.
Постолбцовое представление
— это список столбцов матрицы,
в котором каждый столбец задан индексом и списком элементов.
Каждый элемент столбца представлен индексом строки и значением:
[1] | [0]=9 | |
[2] | [0]=8 | [2]=7 |
[3] | [2]=6 | |
Если в алгоритме требуется перебрать все непустые столбцы разреженной матрицы,
и в каждом стролбце перебрать все элементы,
то это типичный случай, когда следует использовать постолбцовое представление.
HRESULT Add([in] int row, [in] int col, [in] double val)
Функция добавляет в матрицу элемент со значением val,
положение которого в матрице задается парой индексов [row,col].
После добавления элементов и перед началом работы с матрицей
необходимо создать индексацию с помощью функции CreateIndex().
HRESULT CreateIndex();
HRESULT DeleteIndex();
Функции создания и удаления индексации.
Индексация обеспечивает эффективное преобразование
индексов элементов в порядковые номера, и обратно.
Индексацию необходимо производить
перед первым обращением к элементам матрицы
после одного или нескольких добавлений элементов функцией Add.
HRESULT Clear()
Функция очищает матрицу, удаляя все элементы.
Функции для обработки элементов в порядке поступления
HRESULT ElemCount([out,retval] int* count)
Функция возвращает количестыо непустых элементов в матрице.
HRESULT Elem([in] int i, [out,retval] double* elem)
Функция возвращает значение элемента по его номеру в порядке поступления.
HRESULT ElemIndex([in] int i, [in] int dim, [out,retval] int* index)
HRESULT ElemNo([in] int i, [in] int dim, [out,retval] int* no)
Функции возвращают соответственно индекс и номер элемента
по строке (dim=0) или по столбцу (dim=1).
Элемент задается номером i в порядке поступления.
Функции для обработки элементов по строкам.
HRESULT Rows([out,retval] int* size)
Функция возвращает число непустых строк в матрице.
HRESULT RowSize([in] int row, [out,retval] int* count)
Функция возвращает число элементов в row-ой строке, 0<=row<Rows.
HRESULT Row([in] int row, [in] int i, [out,retval] double* elem)
Функция выдает значение i-го элемента в row-ой строке.
HRESULT RowIndex([in] int row, [out,retval] int* index)
Функция выдает индекс строки с номером row.
HRESULT RowElemIndex([in] int row, [in] int i, [out,retval] int* index)
Функция возвращает индекс столбца для i-го элемента row-ой строки.
HRESULT RowElemNo([in] int row, [in] int i, [out,retval] int* no)
Функция возвращает номер элемента в row-ой строке,
индекс столбца которого равен i.
Если в строке нет такого элемента, возвращается (-1).
Функции для обработки элементов по столбцам.
Эти функции аналогичны функциям предыдущей группы.
HRESULT Cols([out,retval] int* size)
Функция возвращает число непустых столбцов в матрице.
HRESULT ColSize([in] int col, [out,retval] int* count)
Функция возвращает число элементов в col-м столбце, 0<=col<Cols.
HRESULT Col([in] int col, [in] int i, [out,retval] double* elem)
Функция выдает значение i-го элемента в col-м столбце.
HRESULT ColIndex([in] int col, [out,retval] int* index)
Функция выдает индекс столбца с номером col.
HRESULT ColElemIndex([in] int col,[in] int i,[out,retval] int* index)
Функция возвращает индекс строки для i-го элемента col-го столбца.
HRESULT ColElemNo([in] int col,[in] int i,[out,retval] int* no)
Функция возвращает номер элемента в col-м столбце,
индекс строки которого равен i.
Если в столбце нет такого элемента, возвращается (-1).