Матрица 10000×10000 типа float64 занимает 800 МБ независимо от того, сколько в ней значащих чисел. Если ненулевых всего 1%, плотное представление расходует память примерно в 66 раз больше, чем нужно: формат CSR на ту же матрицу требует около 12 МБ. Практический ориентир такой: при доле ненулевых ниже 10% берите разреженный формат, выше 30% — плотный, а в диапазоне 10–30% считайте по формулам и замеряйте на своих данных.
Дальше — устройство основных форматов, формулы оценки памяти с числовыми примерами, вывод порога доли ненулевых и критерии выбора под конкретную операцию.
Плотное и разреженное хранение: в чём принципиальная разница
Что такое плотный непрерывный массив
Плотный массив лежит в одном непрерывном блоке памяти. Адрес элемента с индексом i вычисляется как base + i × sizeof(T): логический индекс превращается в физическое смещение одним умножением и сложением. Заняты все ячейки, нули хранятся наравне со значимыми числами.
Массив int32 размером 1000×1000 содержит миллион элементов по 4 байта, итого 4 МБ. Матрица 10000×10000 типа float64 — уже 800 МБ. Рост по обеим размерностям даёт квадратичный расход памяти, и на больших n плотное представление перестаёт помещаться в ОЗУ.
Плотное хранение даёт доступ за O(1), предсказуемую локальность и возможность применять векторные инструкции. Как индексы превращаются в адреса и почему порядок обхода влияет на кэш, разобрано в статье Row-major и column-major: влияние порядка обхода на кэш и производительность.
Что такое разреженная структура и когда она нужна
Разреженная структура хранит только ненулевые элементы вместе с их координатами. Нули не хранятся вообще, и это главный источник экономии памяти.
Пример: матрица смежности графа с миллионом вершин и пятью миллионами рёбер. Плотный вариант занял бы 10¹² элементов, разреженный — около 5 млн значений плюс индексы. Похожая картина в методе конечных элементов: матрица жёсткости размером 10⁶ × 10⁶ содержит примерно 5 млн ненулевых, всё остальное нули.
Плата за экономию: массивы индексов, косвенный доступ к памяти и операции, которые на плотных данных идут быстрее. Умножение разреженной матрицы на вектор редко достигает пиковой пропускной способности памяти из-за постоянного чтения индексов.
Матрица 1000×1000 с 1% ненулевых содержит миллион ячеек, но лишь около 10 тыс. значимых чисел. Выбор между двумя представлениями зависит от доли ненулевых, типа операций и жёсткости требований к памяти.
Основные форматы разреженного хранения: CSR, CSC и словарь индексов
Формат CSR: структура и применение
CSR (Compressed Sparse Row) хранит матрицу в трёх массивах: values — ненулевые значения по строкам, col_indices — номера столбцов для каждого значения, row_ptr — указатели на начало каждой строки. Длина row_ptr равна числу строк плюс один, последний элемент равен nnz.
Разбор на матрице 3×3 со строками [1, 0, 2], [0, 0, 3] и [4, 5, 0]:
values = [1, 2, 3, 4, 5]
col_indices = [0, 2, 2, 0, 1]
row_ptr = [0, 2, 3, 5]
Значения строки j лежат в срезе values[row_ptr[j] : row_ptr[j+1]]. Для строки 1 это values[2:3], то есть элемент 3 в столбце 2. Просматривать весь массив не нужно: длина строки известна из разности соседних указателей.
CSR оптимален для построчного доступа. Умножение разреженной матрицы на вектор (SpMV) читает col_indices и values последовательно, что даёт предсказуемый поток данных. Вставка нового элемента сдвигает хвост массива, поэтому матрицу собирают в другом формате и конвертируют в CSR один раз, например из coo_matrix в SciPy.
Формат CSC: структура и применение
CSC (Compressed Sparse Column) повторяет CSR с точностью до транспонирования: values, row_indices и col_ptr длиной число столбцов плюс один. Для той же матрицы 3×3 получится:
values = [1, 4, 5, 2, 3]
row_indices = [0, 2, 2, 0, 1]
col_ptr = [0, 2, 3, 5]
CSC выигрывает там, где работа идёт по столбцам: решение систем с треугольными матрицами, разложение LU и Холецкого, умножение на транспонированную матрицу. По памяти CSR и CSC идентичны, разница только в порядке обхода, а значит в кэш-промахах и итоговой скорости конкретной операции.
Словарь индексов: гибкость против производительности
Словарь индексов (Dictionary of Keys, DOK) хранит пары «строка, столбец» как ключи хеш-таблицы, а значения — как данные. Родственный формат LIL держит список списков по строкам. Оба применяют для постепенного построения матрицы, когда координаты становятся известны по одной.
Пример: матрица собирается из потока событий, и пара (i, j) определяется во время разбора записи. Ни структура, ни nnz заранее неизвестны. Словарь примет элементы в произвольном порядке без перестроения массивов. Когда сборка закончена, матрицу переводят в CSR или CSC.
Цена гибкости — накладные расходы на каждый элемент и хеш-поиск при обращении. Рост таких структур с реаллокацией и копированием разобран в статье Динамические массивы: рост, реаллокация и цена копирования. Для матриц с миллионами ненулевых словарь занимает заметно больше памяти, чем CSR, и для вычислений он не подходит.
Как оценить объём памяти: формулы и примеры расчёта
Формула для плотного массива
M_dense = m × n × sizeof(T), где m и n — размерности, sizeof(T) — размер одного элемента в байтах.
Матрица 10000×10000 типа float64: 10⁸ × 8 = 8·10⁸ байт, то есть 800 МБ. Матрица 1000×1000 типа int32: 10⁶ × 4 = 4 МБ.
Для массивов структур sizeof(T) учитывает padding, который компилятор добавляет для выравнивания полей. Как перестановка полей сокращает размер, показано в статье Выравнивание данных в памяти и padding в массивах. Перед расчётом проверьте фактический sizeof, а не складывайте размеры полей вручную.
Формула для CSR и CSC
M_CSR = nnz × (sizeof(T) + sizeof(index)) + (m + 1) × sizeof(index)
M_CSC = nnz × (sizeof(T) + sizeof(index)) + (n + 1) × sizeof(index)
Здесь nnz — число ненулевых, sizeof(index) — размер типа индекса, обычно 4 байта для int32.
Расчёт для nnz = 1 000 000, T = float64 (8 байт), index = int32 (4 байта): 10⁶ × 12 = 12 000 000 байт плюс (10000 + 1) × 4 ≈ 40 КБ на row_ptr. Итого около 12,04 МБ против 800 МБ у плотного варианта, то есть в 66 раз меньше.
Полезное следствие: значения float64 занимают вдвое больше места, чем индексы. Если коэффициенты допускают float32, память на данные упадёт в два раза, но относительная доля индексов вырастет, и порог по плотности сдвинется.
Формула для словаря индексов
Точной универсальной формулы для словаря индексов нет: расход памяти зависит от реализации хеш-таблицы, типа ключа и среды выполнения. Для оценки снизу можно взять M_DOK ≈ nnz × (sizeof(key) + sizeof(T)), но реальный объём будет выше из-за накладных расходов на слоты таблицы и упаковку объектов.
Полезно помнить порядок величин. В Python dict — хеш-таблица с открытой адресацией: при вставке проверяется коэффициент заполнения (занятые слоты / всего слотов), и при превышении примерно 2/3 таблица перестраивается в больший размер с перехешированием всех записей. На практике это даёт около 200–300 байт на запись на 64-битном Python, а dict на 10 млн записей может потреблять 2–3 ГБ только на структуру. Сам объект dict добавляет от 60 до 120 байт в зависимости от разрядности сборки.
Поэтому для матрицы с миллионом ненулевых словарь индексов в интерпретируемом языке легко занимает на порядок больше CSR, и замер памяти на реальных данных здесь надёжнее любой формулы.
Порог доли ненулевых элементов: когда разреженный формат выигрывает
Математический вывод порога по памяти
Разреженное хранение выигрывает, когда M_sparse < M_dense. Для CSR при квадратной матрице:
nnz × (s + i) + (m + 1) × i < m × n × s
Обозначим долю ненулевых p = nnz / (m × n) и разделим обе части на m × n × s:
p < s / (s + i) × (1 - (m + 1) × i / (m × n × s))
Для больших m и n вторым множителем можно пренебречь: при m = n = 10000, s = 8, i = 4 он равен 1 - 5·10⁻⁵. Остаётся p < s / (s + i). Подстановка даёт теоретические границы по памяти:
| Тип значения | Тип индекса | Порог p |
|---|---|---|
| float64 (8 байт) | int32 (4 байта) | 0,67 |
| float32 (4 байта) | int32 (4 байта) | 0,50 |
| float64 (8 байт) | int64 (8 байт) | 0,50 |
| float32 (4 байта) | int64 (8 байт) | 0,33 |
Это оценка только по памяти. Скорость сдвигает порог вниз, иногда в разы.
Практические рекомендации по порогу
Единого отраслевого порога, подтверждённого документацией библиотек или воспроизводимым бенчмарком, нет: точка перехода зависит от операции, платформы и версии библиотеки. Приведённая ниже таблица — рабочая эвристика, а не измеренная константа; проверяйте её на своих данных.
| Доля ненулевых | Что выбрать |
|---|---|
| Меньше 5% | Разреженный формат: выигрыш по памяти и обычно по скорости |
| 5–15% | Разреженный выигрывает по памяти, по скорости зависит от операции |
| 15–30% | Считать по формулам и сравнивать оба варианта на своих данных |
| Больше 30% | Плотный формат часто быстрее и проще в коде |
Реальный порог ниже теоретического по трём причинам: разреженные операции читают индексы, теряют векторные инструкции и дают косвенный доступ с промахами кэша. На GPU картина сложнее: cuSPARSE ориентирована на матрицы с долей разреженности примерно от 70% до 99,9% в зависимости от операции (документация cuSPARSE 13.4), а эксперименты с CSR SpMV на GPU показывают, что эффективность ядра заметно растёт с увеличением полезной работы на строку (исследование производительности CSR SpMV). Числового порога плотности, при котором разреженный формат на GPU гарантированно окупается, в доступных источниках нет — его нужно измерять под конкретное ядро.
Графовые задачи стоят особняком. Матрица смежности почти всегда крайне разрежена, и порог для неё не обсуждается: работоспособной плотной альтернативы нет.
Практические примеры: численные методы и графовые задачи
Численные методы: разреженные матрицы в PDE
Дискретизация уравнения теплопроводности на сетке 1000×1000 даёт миллион неизвестных. Шаблон «пяти точек» порождает около пяти ненулевых на строку, то есть nnz ≈ 5·10⁶, а матрица коэффициентов имеет размер 10⁶ × 10⁶.
Доля ненулевых: 5·10⁶ / 10¹² = 5·10⁻⁶, то есть 0,0005%. Плотное хранение потребовало бы 8 ТБ, CSR — около 60 МБ на значения и индексы плюс 4 МБ на row_ptr. Выбор очевиден.
Порядок уравнений можно переставить так, чтобы ненулевые группировались ближе к диагонали, и тогда кэш работает эффективнее. Симметричные матрицы часто хранят в CSR с учётом только верхнего треугольника, экономя ещё около половины памяти на значениях.
Графовые задачи: матрица смежности и списки рёбер
Граф с 10 млн вершин и 100 млн рёбер в плотном виде дал бы 10⁷ × 10⁷ = 10¹⁴ ячеек. Даже по одному байту это 100 ТБ, задача не помещается ни в память, ни на диск. Доля ненулевых: 10⁸ / 10¹⁴ = 10⁻⁶, то есть 0,0001%.
В CSR без весов значения не хранят вовсе: col_indices занимает 10⁸ × 4 = 400 МБ, row_ptr — примерно 40 МБ. Итого около 440 МБ на граф, который в плотном виде не существует.
Обход в ширину идёт по исходящим рёбрам и хорошо ложится на CSR. Обход по входящим рёбрам удобнее через CSC либо через отдельный CSR, построенный на обращённом графе. CSR остаётся базовым форматом и точкой отсчёта при сравнении: на нём построены и специализированные графовые пайплайны, например проект CSR-раскраски графов на Cerebras WSE, где граф конфликтов конвертируется в CSR, разбивается по processing elements и раскрашивается спекулятивными BSP-раундами (CSR-graph-coloring). Подтверждённых данных о переходе графовых библиотек на 8-битные смещения для малых степеней вершин в доступных источниках нет, поэтому считать это общей практикой 2026 года не стоит.
Критерии выбора формата под конкретную нагрузку
Чек-лист для быстрого решения
- Посчитайте долю ненулевых. Меньше 10% — разреженный формат, больше 30% — плотный.
- Определите главную операцию. Построчный доступ и SpMV — CSR. Решение треугольных систем, разложения, доступ по столбцам — CSC.
- Проверьте, нужна ли динамическая вставка. Если структура собирается постепенно, начните с COO, DOK или LIL, затем конвертируйте в CSR или CSC.
- Оцените память по формулам из раздела выше. Если плотный вариант не помещается в ОЗУ, вопрос закрыт.
- Проверьте поддержку формата в библиотеке. SciPy, cuSPARSE и MKL работают с CSR, CSC и COO, а конвертация между ними стоит времени и памяти.
- Учтите платформу. На CPU разреженные форматы окупаются раньше, на GPU плотные ядра быстрее набирают пропускную способность.
Пример применения: SpMV для матрицы с долей ненулевых 5%, тип float64, индексы int32. По таблице порогов разреженный формат выигрывает и по памяти, и по скорости, а из форматов выбираем CSR, потому что операция строчная.
Типичные ошибки и как их избежать
- Плотное хранение разреженных данных. Матрица 10⁶ × 10⁶ с 0,0005% ненулевых требует 8 ТБ вместо 64 МБ.
- Разреженный формат для плотных данных. При доле ненулевых выше 60% индексы удваивают объём, а косвенный доступ замедляет работу.
- CSC там, где нужен построчный обход. Память та же, а промахи кэша съедают выигрыш.
- Игнорирование накладных расходов словаря индексов. На миллионе элементов DOK занимает заметно больше CSR, а в Python разрыв шире из-за упаковки объектов.
- Смена формата без замеров. Решение принимайте по профилю памяти и времени на своих данных, а не по общим рекомендациям.
Актуальность в 2026 году: что изменилось и что осталось
Базовые принципы не изменились. CSR и CSC остаются стандартом де-факто, их поддерживают SciPy, cuSPARSE и MKL, а структура из трёх массивов повторяется в большинстве библиотек. SciPy v1.18.0 поддерживает форматы BSR, COO, CSC и LIL (SciPy v1.18.0 Manual), а cuSPARSE 13.4 — плотные и разреженные форматы, включая BSR, с нумерацией индексов с нуля и с единицы и операциями конвертации между форматами (cuSPARSE 13.4 documentation). Интерфейсы CUSPARSE.jl также реализуют сжатое хранение по строкам и столбцам, блочный CSR и гибридный формат NVIDIA с автоматической конвертацией (CUSPARSE.jl).
Что поменялось: объёмы матриц растут, и выбор формата влияет на бюджеты памяти сильнее, чем десять лет назад. Для блочных матриц с плотными подблоками применяют BSR, который хранит индексы один раз на блок и снижает накладные расходы индексации. Отдельно стоит учитывать смену интерфейсов: SciPy переходит от sparse matrix к sparse array, и в ближайших релизах ожидается объявление старого интерфейса устаревшим. Утверждение об автоматическом подборе формата библиотеками в доступных источниках подтверждения не нашло — конвертация между форматами есть, а автоматический выбор нужно проверять по документации конкретной версии.
Аппаратный фон: кэши выросли, но разреженные операции упираются в пропускную способность памяти и не выигрывают от широких векторных блоков так, как плотные. На GPU разреженные ядра по-прежнему уступают плотным при умеренной плотности, а cuSPARSE явно нацелена на сильно разреженные матрицы.
Универсального формата нет, есть компромисс между памятью, скоростью и удобством сборки. Возьмите свою матрицу, посчитайте nnz и m × n, подставьте в формулы, проверьте оба варианта на реальных данных и зафиксируйте результат замера в комментарии к коду. Конкретные цифры зависят от версии библиотеки, платформы и порядка обхода, поэтому финальное решение подтверждайте профилировщиком.