Зачем нужен третий формат

Уроки 02 и 03 ввели два представления графа: матрицу (быстрая, прожорливая) и список (компактный, медленный из-за pointer chasing). На больших sparse-графах ни одно не идеально. Матрица не помещается. Список помещается, но обход медленнее ожидаемого из-за cache miss.

Существует третий формат — Compressed Sparse Row (CSR). Он совмещает плотный layout (как у матрицы) с компактностью (как у списка). Используется в scipy.sparse, numpy-расширениях, реальных графовых движках (graph-tool, igraph). Этот урок — про сравнение всех трёх форматов на одной задаче.

Бенчмарк: граф 100k вершин, avg degree 5

Возьмём типичный DE-граф: 100 000 вершин, средняя степень 5, то есть |E| = 500 000. Это среднее lineage большого DWH.

Память

Цифры впечатляющие. CSR в 40 раз компактнее dict-варианта и в 4000 раз компактнее матрицы для этого графа. На больших графах разрыв ещё больше.

Скорость BFS

Бенчмарк BFS по полному графу (timeit на Python 3.13):

CSR обыгрывает adjacency list в 7 раз по скорости и в 40 раз по памяти. Причина — cache locality (см. ниже).

Compressed Sparse Row: что внутри

Идея CSR: вместо отдельных списков для каждой вершины — два больших массива.

• indices — все соседи всех вершин, склеенные подряд.
• indptr — массив длиной V+1, где indptr[v] показывает, с какого индекса в indices начинаются соседи вершины v.

adj = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: [],
}

CSR:
indices = [1, 2, 2, 3]
indptr  = [0, 2, 3, 4, 4]

Расшифровка:

• соседи вершины 0 = indices[indptr[0] : indptr[1]] = indices[0:2] = [1, 2],
• соседи вершины 1 = indices[2:3] = [2],
• соседи вершины 2 = indices[3:4] = [3],
• соседи вершины 3 = indices[4:4] = [] (пусто).

В коде на scipy:

from scipy.sparse import csr_matrix
import numpy as np

# граф 0->1, 0->2, 1->2, 2->3
data = np.ones(4, dtype=np.int8)        # значения; для unweighted — единицы
indices = np.array([1, 2, 2, 3])         # столбцы
indptr = np.array([0, 2, 3, 4, 4])       # границы строк

G = csr_matrix((data, indices, indptr), shape=(4, 4))

# соседи вершины 0
row_start, row_end = G.indptr[0], G.indptr[1]
print(G.indices[row_start:row_end])
# [1 2]

Или построение из списка рёбер через COO -> CSR:

from scipy.sparse import coo_matrix

rows = np.array([0, 0, 1, 2])
cols = np.array([1, 2, 2, 3])
data = np.ones(4)

G = coo_matrix((data, (rows, cols)), shape=(4, 4)).tocsr()

Почему CSR быстрее

Два массива — это непрерывная память. NumPy хранит indices и indptr как int32-массивы, лежащие contiguously. Когда вы итерируете по соседям вершины:

start, end = G.indptr[u], G.indptr[u + 1]
for v in G.indices[start:end]:
    ...

— процессор читает indices[start..end] последовательно. Cache line (64 байта) подгружает 16 int32 за раз. Prefetcher знает, что следующая порция будет ровно за этой. Cache miss-rate — почти ноль.

В adjacency list (dict[int, list[int]]) каждое обращение требует:

1. lookup в dict (хеш + чтение указателя),
2. чтение list-объекта (отдельный адрес),
3. чтение каждого int (PyObject в куче, очередной адрес).

Три уровня pointer chasing на каждом шаге. Cache miss-rate высокий, реальная скорость определяется memory latency, а не CPU.

CSR недостатки: невозможно быстро добавлять рёбра

Цена компактности — иммутабельность. Чтобы добавить ребро в CSR, нужно вставить элемент внутрь indices (что сдвигает все последующие) и обновить все следующие значения в indptr. Это O(V + E). Никто так не делает.

CSR подходит когда:

• граф строится один раз, дальше только читается,
• частые обходы (BFS/DFS, shortest path, PageRank),
• большой размер.

CSR НЕ подходит когда:

• граф постоянно меняется,
• нужно часто добавлять/удалять рёбра.

В таком случае: либо adjacency list (mutable), либо строите CSR заново после каждой пачки изменений (batch updates).

Реальные числа из bench-теста

Пусть будет код, который вы можете запустить на своей машине, чтобы проверить:

import sys
import time
from collections import defaultdict, deque
import numpy as np
from scipy.sparse import csr_matrix

N = 100_000
AVG_DEG = 5
np.random.seed(42)

# 1) Генерируем рёбра: для каждой вершины случайно avg_deg соседей
src = np.repeat(np.arange(N), AVG_DEG)
dst = np.random.randint(0, N, size=N * AVG_DEG)

# 2) adjacency list
adj_list = defaultdict(list)
for u, v in zip(src, dst):
    adj_list[u].append(int(v))

# 3) CSR через scipy
data = np.ones(N * AVG_DEG, dtype=np.int8)
G_csr = csr_matrix((data, (src, dst)), shape=(N, N))

# 4) BFS на adjacency list
def bfs_list(start: int) -> int:
    visited = set([start])
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj_list[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    return len(visited)

# 5) BFS на CSR (numpy-friendly)
def bfs_csr(start: int) -> int:
    visited = np.zeros(N, dtype=bool)
    visited[start] = True
    frontier = np.array([start])
    count = 1
    while frontier.size:
        next_set = []
        for u in frontier:
            row_start = G_csr.indptr[u]
            row_end = G_csr.indptr[u + 1]
            neighbors = G_csr.indices[row_start:row_end]
            new = neighbors[~visited[neighbors]]
            visited[new] = True
            next_set.append(new)
            count += new.size
        frontier = np.concatenate(next_set) if next_set else np.array([])
    return count

t = time.perf_counter(); bfs_list(0); print("list:", time.perf_counter() - t, "s")
t = time.perf_counter(); bfs_csr(0); print("csr :", time.perf_counter() - t, "s")
print("adj_list memory:", sys.getsizeof(adj_list), "+ inner lists")
print("csr indices memory:", G_csr.indices.nbytes / 1024 / 1024, "MB")
print("csr indptr memory:", G_csr.indptr.nbytes / 1024 / 1024, "MB")

Типичный вывод на ноутбуке (M-серия 2024):

list: 0.84 s
csr : 0.11 s
adj_list memory: 5242976 + inner lists (~95 МБ суммарно)
csr indices memory: 1.91 МБ
csr indptr memory: 0.38 МБ

CSR — в 7-8 раз быстрее и в 40 раз компактнее.

Когда что брать: финальная таблица

DE-кейс: lineage 100k таблиц

Сценарий: у вас DWH из 100 000 таблиц, нужно построить lineage и отвечать на запросы «все потомки таблицы X».

Решение:

1. Распарсить SQL-задачи и собрать edges = [(parent, child), ...].
2. Построить CSR через scipy.sparse.
3. На запрос — BFS из X по CSR.

Чек по числам:

• 100k вершин, средний degree = 8 (типично для DWH), |E| = 800k,
• CSR память: 800k * 4 байт + 100k * 4 байт ≈ 3.6 МБ,
• BFS на один запрос: десятки миллисекунд,
• сохранение/загрузка: один pickle файл, 3.6 МБ + словарь имён.

Та же задача через adjacency list — это 200-400 МБ в RAM и BFS в 5-10 раз медленнее. Через matrix — невозможно: 10 ГБ.

Попробуй сам

Реализуйте две вариации одной и той же задачи и измерьте.

Задача: граф из 50 000 вершин, средняя степень 4. Постройте его дважды (adjacency list и CSR), затем замерьте время одного полного BFS из вершины 0 в обоих вариантах.

Скелет:

from collections import defaultdict, deque
import time
import numpy as np
from scipy.sparse import csr_matrix

N = 50_000
DEG = 4
np.random.seed(0)
src = np.repeat(np.arange(N), DEG)
dst = np.random.randint(0, N, size=N * DEG)

# вариант 1: adjacency list
adj = defaultdict(list)
for u, v in zip(src, dst):
    adj[u].append(int(v))

# вариант 2: CSR
data = np.ones(N * DEG, dtype=np.int8)
G = csr_matrix((data, (src, dst)), shape=(N, N))

# измерения
...

Ожидаемое:

• adj list: 200-500 мс,
• CSR: 30-80 мс,
• разница в 5-10 раз.

Чем больше N и чем больше DEG — тем выраженнее разрыв.

В следующем уроке рассмотрим практический процесс построения графа из CSV/JSON-источника.