Что такое разреженные массивы и почему они важны
Разреженный массив хранит только значимые элементы вместе с их индексами, а пустые позиции память не занимают. Матрица 10^6 x 10^6, где заполнено 0,01% ячеек, содержит триллион логических позиций и всего 100 миллионов значимых значений: плотное представление потребует 8 ТБ, тогда как разреженное хранит только ненулевые элементы и их индексы.
Степень заполнения описывают коэффициентом разреженности: sparsity = 1 - nnz / (n * m), где nnz - число ненулевых элементов, n и m - размеры по строкам и столбцам. Матрица 1000 x 1000 с 5000 ненулевыми даёт sparsity = 1 - 5000 / 1 000 000 = 0,995, то есть 99,5% позиций пустуют.
Разница между подходами измеряется порядком роста: плотный массив требует O(n*m) памяти, разреженный - O(nnz). Чем крупнее задача, тем сильнее это расхождение, поэтому на больших наборах данных выбор формата влияет на потребление памяти и время работы заметнее, чем выбор языка или библиотеки.
Определение и коэффициент разреженности
Разреженный массив (sparse array) содержит преимущественно нулевые или отсутствующие элементы, которые не хранятся явно. Второй параметр, который считают рядом со sparsity, - плотность: density = nnz / (n * m). Для примера выше density = 0,005, или 0,5%.
Порог, после которого плотное хранение становится невыгодным, зависит от задачи и от размера индексов. Практическое правило: при плотности ниже примерно 5% разреженные форматы выигрывают как по памяти, так и по вычислениям (Sparse Matrix Methods - CSR/CSC Formats). При более высокой плотности решение стоит принимать по замеру на своих данных, а не по общему правилу: эффективность разреженных форматов зависит от размера и разреженности массива, и в отдельных экспериментах даже при 90% разреженности плотный формат показывал лучшую производительность, а при 99% разреженности результаты двух форматов оказывались почти одинаковыми (Sparse storage format in the new sparse module of HeAT). Отдельно стоит учитывать размер: для матриц меньше примерно 1000 x 1000 накладные расходы разреженного формата (переходы по указателям, косвенная адресация) могут делать его медленнее плотного.
Термин употребляют в двух смыслах. В численных библиотеках речь обычно идёт о разреженных матрицах, то есть о двумерном случае. Для одномерных данных с пропусками используют словарь индекс-значение, отсортированный список пар, битовую карту с блоком значений или сжатие повторов (run-length encoding). Примеры из практики: временные ряды с пропущенными замерами, наборы идентификаторов просмотренных товаров у пользователя, инвертированный индекс поисковой системы.
Отдельно стоит держать в голове модель плотного массива: элементы лежат непрерывно, и адрес любого из них считается как base + i * size. Эта арифметика даёт O(1) на чтение, но требует места под все ячейки. Подробнее механику адресации разбирает материал о хранении элементов массива в памяти.
Почему плотное хранение неэффективно
Перерасход памяти считается простой арифметикой. Матрица 10^6 x 10^6 в типе float64 занимает 10^12 * 8 байт = 8 ТБ. Та же матрица с 0,01% ненулевых (nnz = 10^8) в формате CSR требует 800 МБ на значения, 400 МБ на индексы столбцов типа int32 и 4 МБ на указатели строк, итого около 1,2 ГБ. Выигрыш - примерно в 6700 раз. Более скромный пример с оценкой памяти для плотного и разреженного представления разобран в статье о плотном и разреженном хранении массивов: 10000 x 10000 с 1% ненулевых занимает 800 МБ плотно и около 12 МБ в CSR.
Второй источник потерь - кэш процессора. Линия кэша на 64 байта вмещает восемь значений float64. Если в строке на восемь чисел приходится один ненулевой элемент, полезно используется примерно восьмая часть пропускной способности памяти, остальное время уходит на чтение нулей. На задачах, упирающихся в память, это часто дороже, чем сама арифметика.
Лишние вычисления идут третьим пунктом. Умножение на ноль не меняет результат, но занимает слот в конвейере и потребляет энергию. Умножение плотной матрицы на вектор стоит O(n*m) операций, разреженной - O(nnz). При nnz = 10^8 и n*m = 10^12 разница в объёме работы составляет четыре порядка.
В машинном обучении разреженность встречается постоянно. При one-hot encoding словаря на 100 000 терминов документ из 200 уникальных слов даёт 99,8% нулей. Матрица документ-термин на 10^6 документов и 10^5 терминов при 10^7 ненулевых занимает в CSR около 124 МБ, а в плотном виде - 800 ГБ.
Структуры данных для компактного хранения разреженных массивов
Словари и деревья: гибкость для динамических данных
Словарь хранит пары «координата, значение»: ключом служит кортеж (i, j) или одиночный индекс. В Python роль такой структуры играет dict, в SciPy аналогичный формат называется DOK (Dictionary of Keys). Вставка, удаление и обновление элемента выполняются в среднем за O(1), и менять структуру можно сколько угодно раз без полной перестройки.
Плата за гибкость высока. Каждый элемент требует хранения ключа: кортеж из двух целых в CPython занимает десятки байт вместе с накладными расходами на объект, тогда как в CSR на элемент уходит 12 байт. Локальность памяти тоже страдает: соседние элементы разреженного массива попадают в разные участки кучи, и процессор не может воспользоваться предзагрузкой.
Дерево даёт упорядоченное хранение координат. Если элементы лежат в B-дереве или сбалансированном дереве поиска, диапазонные выборки вида «все значения строки с индексами от 100 до 200» выполняются за O(log nnz + k), где k - число найденных элементов. Такой подход удобен, когда массив одновременно читают диапазонами и точечно правят. Упорядоченные деревья лежат в основе индексов реляционных СУБД и работают по той же логике: сортировка ключей ускоряет выборку за счёт памяти.
Формат CSR (Compressed Sparse Row)
CSR хранит матрицу тремя массивами: values (ненулевые элементы по строкам), col_indices (номера столбцов для каждого значения) и row_ptr (указатели на начало каждой строки в первых двух массивах). Длина col_indices и values равна nnz, длина row_ptr равна n + 1.
Разбор на матрице 3 x 3: строка 0 = [1, 0, 0], строка 1 = [0, 2, 3], строка 2 = [4, 0, 5]. Тогда values = [1, 2, 3, 4, 5], col_indices = [0, 1, 2, 0, 2], row_ptr = [0, 1, 3, 5]. Поиск элемента в строке сводится к бинарному поиску в срезе col_indices между row_ptr[i] и row_ptr[i+1], то есть к O(log k), где k - число ненулевых в строке. Последовательный обход строки даёт линейное чтение памяти без промахов.
Слабое место CSR - изменения структуры. Вставка нового элемента в середину строки сдвигает хвост массивов, то есть стоит O(nnz). Доступ к столбцу требует обхода всех строк, поэтому column slicing работает медленно. Умножение матрицы на вектор (SpMV) и матрицы на матрицу с участием CSR выполняется эффективно: алгоритм проходит массивы слева направо. Формат csr_matrix - стандарт в SciPy для разреженных вычислений.
Формат CSC (Compressed Sparse Column)
CSC устроен зеркально: values и row_indices хранят элементы по столбцам, col_ptr указывает начала столбцов. Для той же матрицы 3 x 3 получим values = [1, 4, 2, 3, 5], row_indices = [0, 2, 1, 1, 2], col_ptr = [0, 2, 3, 5].
Формат выбирают, когда основная нагрузка связана со столбцами. Типичные сценарии: умножение вектора-строки на матрицу, прямой доступ к столбцам в задачах обработки признаков, разложения матриц. Разложение Холецкого и LU для разреженных матриц порождает множители, которые удобно хранить по столбцам, поэтому решатели систем линейных уравнений работают с CSC: функция scipy.sparse.linalg.splu, использующая библиотеку SuperLU, наиболее эффективна при передаче матрицы именно в формате CSC, а другие форматы перед факторизацией конвертируются в CSC (splu - SciPy Manual). Транспонирование CSC даёт CSR без пересчёта значений.
Выбор между CSR и CSC определяется направлением доступа. Если код чаще извлекает строки и умножает матрицу на вектор справа, берите CSR. Если чаще нужны столбцы, транспонирование или факторизация, берите CSC. Переключение формата операцией tocsr() или tocsc() требует пересборки индексов и стоит O(nnz).
Координатный формат (COO) и другие
COO хранит три параллельных массива одинаковой длины nnz: row, col, values. Никакой сортировки и группировки нет, поэтому формат удобен для сборки матрицы из потоков данных: элементы можно добавлять в произвольном порядке, а повторяющиеся координаты суммируются при конвертации в CSR или CSC. Плата - избыточность: 8 байт на пару индексов против примерно 4-5 байт в CSR, плюс невозможность быстрого доступа к элементу.
LIL (List of Lists) хранит по списку на каждую строку и допускает инкрементальное построение с изменением отдельных строк, но расходует больше памяти. Формат DIA эффективен для матриц с ненулевыми элементами на нескольких диагоналях, BSR - для блочных структур, где ненулевые элементы группируются в плотные блоки. Разреженные GPU-библиотеки часто требуют COO или BSR для передачи данных на устройство.
Практические примеры: ML, графы, научные вычисления
Машинное обучение: разреженные признаки и one-hot encoding
Векторизация текста через Bag-of-Words и TF-IDF даёт матрицу документ-термин, в которой доля нулей обычно превышает 99%. Векторизаторы scikit-learn возвращают именно разреженные матрицы, а линейные модели (логистическая регрессия, линейный SVM, SGD-классификатор) умеют обучаться на них напрямую, без преобразования в плотный вид. TF-IDF добавляет веса: tf умножается на idf, и результат остаётся разреженным, потому что ненулевые позиции не меняются.
Категориальные признаки с большим числом значений кодируют разреженными эмбеддингами: PyTorch поддерживает torch.sparse_coo_tensor и torch.sparse_csr_tensor, TensorFlow - tf.sparse.SparseTensor. Это позволяет держать словари на миллионы категорий, не раздувая тензор признаков. Задача, в которой плотное представление было бы невозможно: матрица 10^6 объектов на 10^5 признаков при 10^7 ненулевых занимает около 124 МБ в CSR против 800 ГБ плотно.
Графовые алгоритмы: списки смежности и PageRank
Матрица смежности реального графа почти всегда разрежена: у миллиона вершин и десяти миллионов рёбер плотное представление заняло бы 1 000 000 * 1 000 000 * 8 = 8 ТБ, а CSR с весами float64 - примерно 124 МБ (80 МБ значения, 40 МБ индексы, 4 МБ указатели). Для невзвешенного графа, где нужны только индексы, достаточно около 44 МБ.
CSR графа эквивалентен спискам смежности с непрерывным хранением, поэтому обход в ширину укладывается в O(V + E) при последовательном чтении памяти. В PageRank ключевым шагом вычисления является умножение матрицы на вектор, и при разреженной матрице это вычисление менее ресурсоёмко (PageRank - CS224W Notes). На практике векторно-матричные умножения выполняются на крайне разреженной матрице переходов, а вспомогательные матрицы не формируются и не хранятся целиком - достаточно их компонент ранга один. Каждое такое умножение имеет сложность O(n), поскольку в матрице около 10 ненулевых элементов на строку (Google's PageRank and Beyond). Обратные ссылки считают по транспонированной матрице, для чего удобно держать CSC того же графа.
Научные вычисления: метод конечных элементов и решение СЛАУ
Дискретизация методом конечных элементов даёт разреженную матрицу жёсткости: каждая строка связана только с соседними узлами сетки, и при сборке глобальной матрицы жёсткости используется формат sparse compressed row storage (CSR) (How to efficiently assemble global stiffness matrix). Для двумерной задачи на 10^6 узлов типично около 7 ненулевых на строку, то есть nnz порядка 7 * 10^6. В CSR это порядка 88 МБ (56 МБ значения, 28 МБ индексы, 4 МБ указатели), тогда как плотная матрица заняла бы 8 ТБ. Увеличение сетки до 10^7 узлов делает плотное хранение невозможным даже на серверах с сотнями гигабайт памяти.
Системы линейных уравнений такого размера решают итерационными методами: CG для симметричных положительно определённых матриц, GMRES и BiCGSTAB для несимметричных. Все они опираются на быстрое умножение разреженной матрицы на вектор. Предобусловливатели (Якоби, неполное LU) часто строятся по CSC-представлению и добавляют к матрице множители с новыми ненулевыми элементами, что называется заполнением. В SciPy для этого есть scipy.sparse.linalg.cg, spsolve и splu.
Как выбрать формат для больших разреженных данных
Критерии выбора: операции, память, производительность
Отправная точка - список операций, которые будут выполняться чаще всего. Формат под задачу, а не наоборот.
| Формат | Доступ к элементу | Срез по строке | Срез по столбцу | Вставка и удаление | Умножение на вектор | Память |
|---|---|---|---|---|---|---|
| DOK (словарь) | O(1) в среднем | медленно | медленно | O(1) | медленно | высокая |
| LIL (списки) | O(1) в строке | быстро | медленно | O(1) в строке | медленно | высокая |
| COO | нет | через маски | через маски | только добавление | после конвертации | средняя |
| CSR | O(log k) в строке | быстро | медленно | перестройка O(nnz) | быстро | низкая |
| CSC | O(log k) в столбце | медленно | быстро | перестройка O(nnz) | быстро | низкая |
Правила выбора по нагрузке: построение матрицы из потока данных - COO; пошаговое редактирование - LIL или DOK; чтение и обход по строкам - CSR; работа со столбцами, транспонирование и факторизация - CSC. Для матричных умножений и итерационных решателей выигрывает CSR, для операций вида M^T * v удобнее CSC. Оценку памяти и порог по доле ненулевых элементов удобно проверять на калькуляторе из статьи о критериях выбора формата хранения.
Рекомендации для production-задач
Для ML-пайплайнов держите признаки в CSR: так их отдают векторизаторы scikit-learn, так их принимают линейные модели. Переводите в CSC только те шаги, где идёт работа по столбцам, например нормализация отдельных признаков. В Pandas колонки с большим числом повторов можно хранить в SparseDtype, что сокращает память DataFrame, но не заменяет матричные форматы.
Для графовых задач держите прямое представление в CSR, а обратное - в CSC или в отдельной транспонированной копии. Копия стоит дополнительной памяти пропорционально nnz, зато избавляет от пересчёта индексов на каждой итерации алгоритма.
Для научных расчётов используйте CSC при факторизации и решении систем, CSR при массовых умножениях на вектор. Распределённые вычисления на терабайтных матрицах выполняют в Spark MLlib, который хранит данные блоками и обменивается между узлами сжатыми структурами. На GPU работают cuSPARSE (форматы CSR, CSC, COO, BSR) и разреженные тензорные операции PyTorch и TensorFlow.
Порог, после которого разреженный формат перестаёт окупаться, зависит от размера матрицы и характера операций. Ориентируйтесь на замеры: сравните время ключевой операции и объём памяти для плотного и разреженного варианта на своих данных, прежде чем переписывать пайплайн.
Типичные ошибки и подводные камни
Преобразование в плотный формат и переполнение памяти
Самая дорогая ошибка - вызвать toarray() или todense() на большой матрице. Разреженная матрица 10^5 x 10^5 с 1% ненулевых занимает в CSR около 1,2 ГБ, а после преобразования в плотную - 80 ГБ, что почти гарантированно приводит к аварийному завершению процесса или к убийству контейнера по лимиту памяти.
Перед любым преобразованием считайте размер: n * m * 8 для float64. Пока матрица остаётся разреженной, работайте с её внутренними массивами: в CSR это values и col_indices для данных, row_ptr для структуры. Опасны и промежуточные плотные операции: центрирование признаков вычитанием среднего превращает разреженную матрицу в плотную. Для таких шагов применяйте реализации с поддержкой разреженных данных, например масштабирование с параметром with_mean=False.
Неявные нули и дубликаты индексов
В COO можно записать одну и ту же координату несколько раз. При конвертации в CSR или CSC такие элементы суммируются, и это штатное поведение, но итог может отличаться от ожидаемого. Явные нули тоже хранятся как обычные элементы и увеличивают nnz, раздувая память и время вычислений; от них избавляются вызовом eliminate_zeros(). Дубликаты убирает sum_duplicates(), после чего полезно вызвать sort_indices(): несортированные индексы замедляют поиск и часть операций.
Отдельный риск - тип индексов. При nnz больше 2^31 значение не помещается в int32, и старые сборки библиотек с 32-битными индексами выдают ошибки или порчу данных. Для матриц такого масштаба проверяйте тип индексов и используйте сборки с 64-битной индексацией. И последнее: обход элементов в цикле на Python на порядки медленнее векторных операций над массивами, поэтому срезы и арифметику выполняйте средствами библиотеки.
Заключение
Разреженные массивы экономят память пропорционально доле нулей и ускоряют вычисления за счёт отказа от операций с пустыми элементами. Основные форматы: CSR и CSC для готовых к расчётам матриц, COO и LIL для сборки, словари и деревья для динамических данных и диапазонных выборок.
Практический порядок действий для нового набора данных: посчитайте nnz и плотность, выпишите три-четыре самых частых операции, выберите формат по таблице выше, проверьте расчёт памяти до первого запуска и убедитесь, что в пайплайне нет вызовов toarray(). Для экспериментов достаточно SciPy и scikit-learn, для GPU-расчётов подключайте cuSPARSE или разреженные тензоры PyTorch, для терабайтных объёмов - распределённые движки. Проверку гибридных форматов, аппаратной поддержки разреженности и методов сжатия индексов стоит отложить до момента, когда упрётесь в лимит памяти или скорость уже на разреженном представлении.