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

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

Проблема: вложенные map’ы дорогие

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

Данные разбросаны по памяти. CPU cache prefetcher не помогает — каждый доступ это случайный pointer chase.

Для алгоритмов вроде PageRank или PPR, которые итерируют по соседям миллионы раз, этот overhead доминирует. В одном реальном профиле только FragmentId.__hash__ дал 295 миллионов вызовов и 14.4 секунды CPU — и это только хэширование, без самих dict lookup’ов.

А если хранить как полную матрицу?

Для графа из 10 000 узлов со средней степенью 5 у тебя ~50 000 рёбер. Полная матрица смежности — $10\,000 \times 10\,000 = 10^8$ ячеек. Ненулевых из них $50\,000 / 10^8 = 0.05\%$ — 99.95% пустого места, ~400 MB нулей. И обход строки трогает все $N$ ячеек, даже если ненулевых только 5.

Решение: CSR

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

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

Чтобы найти соседей узла $i$:

$\text{neighbors}(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] — пустой slice.

Почему «Compressed Sparse Row»

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

Производительность: одинаковый Big-O, разные константы

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

Разница в константах обычно 10-30x для графовых обходов. Три источника:

1. Ноль хэширования — 295M вызовов hash становятся нулём
2. Cache locality — непрерывные массивы ложатся в L1/L2 кэш, нет pointer chasing
3. Векторизация — numpy операции на плоских массивах используют SIMD инструкции

Когда НЕ использовать CSR

CSR оптимизирован для read-heavy, write-once графов:

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

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