CSR: как графы хранят в плоских массивах

Кликните по узлу или пройдите по узлам ползунком, чтобы увидеть, какие участки массивов отвечают за его соседей: две его закладки в indptr указывают на края его среза. Попробуйте узел 2 — так выглядит пустой диапазон. Кликните по клетке плотной матрицы, чтобы добавить или убрать ребро и увидеть, как перестраиваются массивы, или по любой ячейке массива, чтобы найти узел, которому она принадлежит.

Проблема: вложенные словари дорого стоят

Граф с $N$ узлами и $E$ рёбрами обычно хранят вложенным словарём — graph[node_i][node_j] = weight. Каждый раз, когда вы спрашиваете «кто соседи узла 0?», рантайм хеширует ключ, проходит по корзинам, сравнивает на равенство, возвращает внутренний словарь — ещё одну хеш-структуру в куче — и итерирует по ней, с хешем и сравнением на каждом соседе. Каждый вес — отдельный объект в куче.

Данные разбросаны по памяти. Префетчер процессора бессилен: каждое обращение — случайный прыжок по указателю.

Для алгоритмов вроде PageRank или PPR, которые проходят по всем соседям миллионы раз, эти накладные расходы становятся доминирующими. В одном реальном профиле FragmentId.__hash__ в одиночку дал 295 миллионов вызовов и 14,4 секунды процессорного времени — и это только хеширование, без самих обращений к словарю.

А если взять полную матрицу?

Для графа с 10 000 узлов и средней степенью 5 получается около 50 000 рёбер. Полная матрица смежности — это $10{,}000 \times 10{,}000 = 10^8$ ячеек. Ненулевых из них $50{,}000 / 10^8 = 0{,}05\%$ — 99,95% впустую, примерно 400 МБ нулей. И проход по строке всё равно трогает все $N$ ячеек, даже если ненулевых там пять.

Решение CSR

Дайте каждому узлу целочисленный индекс $0 \ldots N{-}1$ и храните всё в трёх плоских массивах:

• indptr (длина $N{+}1$) — закладки: indptr[i] говорит, где начинаются соседи узла $i$
• indices (длина $E$) — все узлы-приёмники, упакованные подряд, участок за участком
• weights (длина $E$) — веса рёбер, параллельно indices: weights[k] — вес ребра в indices[k]

Соседи узла $i$ находятся так:

$\text{соседи}(i) = \texttt{indices}[\,\texttt{indptr}[i] \;:\; \texttt{indptr}[i{+}1]\,]$

Фокус с indptr

Представьте семейный список покупок. Все позиции написаны одним длинным списком, а на отдельной бумажке сказано: «строки 1–5 — мамины, 6–7 — папины, 8–12 — бабушкины». Длинный список — это indices. Бумажка с диапазонами строк — indptr.

Когда indptr[i] == indptr[i+1], диапазон пуст — у узла нет исходящих рёбер. Узел 2 как раз такой: indptr[2] = 3 и indptr[3] = 3, то есть indices[3:3] — пустой срез.

Откуда название «Compressed Sparse Row»

• Compressed — нули не хранятся
• Sparse — формат рассчитан на данные, где большинство элементов нулевые
• Row — обход идёт по строкам, то есть по узлам-источникам; для доступа по столбцам есть CSC (Compressed Sparse Column)

Производительность: та же асимптотика, другие константы

И хеш-таблицы, и CSR дают доступ к соседям за $O(1)$ асимптотически. Ускорение берётся из констант:

Разница в константах на задачах обхода графа обычно составляет 10–30 раз и складывается из трёх источников:

1. Ноль хеширования — 295 миллионов вызовов хеша превращаются в ноль
2. Локальность кеша — непрерывные массивы помещаются в L1/L2, прыжков по указателям нет
3. Векторизация — операции numpy над плоскими массивами используют SIMD-инструкции

Когда CSR не нужен

CSR оптимизирован под графы, которые пишут один раз, а читают много:

• Динамические графы — вставка или удаление ребра требует перестройки массивов. Если граф часто меняется, список смежности или список рёбер удобнее.
• Доступ по столбцам — найти все узлы, которые ссылаются на узел $i$, в CSR стоит $O(E)$. Для этого берут CSC или хранят оба представления.
• Очень плотные графы — если большинство ячеек ненулевые, обычная матрица проще и не платит за бухгалтерию indptr.

Типичный сценарий: постройте граф тем, чем удобно — словарём словарей, списком рёбер, — а перед тяжёлой вычислительной фазой один раз переведите в CSR. Конвертация стоит $O(N + E)$ и окупается на первом же полном обходе.

Nikolay Eremeev, Senior Data Infrastructure Engineer. Пишет о том, что строит в продакшене. CV ·hi@nikolay-eremeev.com