Разреженные матрицы

Модуль "Линейные списки" • урок 7 из 9 • ~10 минут

Проблема: Зачем нужны разреженные матрицы?

Представьте, что у вас есть граф из миллиона пользователей соцсети, и вы храните информацию о том, кто у кого в друзьях. Матрица смежности будет иметь размер 1 000 000 x 1 000 000. Если выделить память под двумерный массив целых чисел int32_t, потребуется около 4 Терабайт оперативной памяти! При этом большинство людей имеют всего по 100-200 друзей, то есть 99.999% ячеек будут содержать нули.

Пусть размер матрицы - n, а количество ненулевых элементов - m. Использовать специальные структуры для разреженных матриц имеет смысл, когда m много меньше n².

Разреженные матрицы: представление в виде триплетов

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

• row - номер строки;
• column - номер столбца;
• value - значение элемента.

Общие затраты памяти на хранение m элементов составят примерно 3m (плюс немного накладных расходов). Ниже мы рассмотрим две основные реализации: на базе вектора (массива) и на базе связного списка.

1. Размещение на массиве (векторе)

В этом варианте список ненулевых элементов хранится в динамическом массиве. Чтобы поиск элемента работал быстро, элементы упорядочиваются лексикографически по возрастанию индекса строки, а внутри строки - по столбцу.

// Элемент матрицы
typedef struct {
    uint32_t row;
    uint32_t column;
    int32_t value;
} Item;

// Разреженная матрица на массиве
typedef struct {
    Item *items;       // Динамический массив триплетов
    uint32_t rows;     // Общее количество строк в матрице (n)
    uint32_t columns;  // Общее количество столбцов в матрице (n)
    uint32_t size;     // Текущее количество элементов (m)
    uint32_t capacity; // Вместимость массива
} SparseMatrix;

Особенности размещения на массиве

• [+] Быстрый поиск: Так как массив отсортирован, мы можем использовать двоичный поиск для нахождения нужного индекса за O(log m).
• [-] Медленная вставка: Для вставки нового элемента в середину необходимо сдвинуть все последующие элементы вправо. Вставка и удаление занимают O(m).

2. Отображение на связный список

Если матрица часто изменяется (добавляются и удаляются новые связи), сдвиги в массиве становятся слишком дорогими. В таком случае триплеты выстраиваются в связный список.

В данном представлении элементы по-прежнему упорядочены по возрастанию строк. Все элементы одной строки расположены рядом друг с другом.

// Разреженная матрица на связном списке
typedef struct {
    List *items;       // Связный список из элементов Item
    uint32_t rows;
    uint32_t columns;
} SparseMatrix;

Асимптотика списочного представления

• Доступ к случайному элементу: O(m), так как нужно перебирать элементы списка. Двоичный поиск невозможен.
• Доступ ко всем элементам строки: O(m). Элементы одной строки лежат кучно.
• Доступ ко всем элементам столбца: O(m²) (примитивным перебором), так как элементы одного столбца могут быть "разбросаны" по всему списку! Для оптимизации поиска по столбцам используются более сложные ортосписки.
• Вставка и удаление (если позиция уже найдена): O(1). Как и в любом списке, перекладывать соседние элементы не нужно.