优化图计算性能的关键是让数据排布贴合cpu访问模式：用numpy预分配csr布局的邻接数组替代dict-of-lists，确保indptr和indices为c-contiguous，并避免临时对象创建与低效封装。
图结构在内存中不是天然连续的，直接用 list 或 dict 存邻接表，遍历时缓存不友好、跳转频繁，容易触发大量 TLB miss 和 cache line 重载——这是大规模图计算卡顿的根源之一。优化核心不是“换算法”，而是让数据排布贴合 CPU 访问模式。
用 NumPy 预分配邻接数组替代 dict-of-lists
Python 原生 dict 存图（如 {node: [neighbor1, neighbor2, ...]}）看似直观，但每个 list 独立分配、地址离散，且指针跳转开销大。换成固定大小的 NumPy 数组后，邻居可批量加载进 L1 cache。
- 先统计每个节点的出度，用
np.cumsum()构建 CSR（Compressed Sparse Row）布局的indptr数组 - 把所有邻居 ID 拼成一个扁平
np.array（dtype=np.int32足够，省一半内存） - 遍历某节点
v的邻居时，只查indptr[v]和indptr[v+1]，再切片indices[indptr[v]:indptr[v+1]]—— 这是纯内存连续访问 - 避免用
scipy.sparse.csr_matrix直接做计算：它封装层多，.indices和.indptr字段虽可用，但自带校验和对象开销；裸 NumPy 数组更轻量
按访问模式选 C-order 还是 F-order
图遍历通常是逐节点展开（BFS/DFS），每个节点处理其邻居列表——这本质是“行方向”操作。CSR 布局下，indptr 是节点索引（行号），indices 是邻居值（行内元素）。此时必须用 C-order。
-
indptr和indices都应显式声明为np.array(..., order='C') - 若误用 F-order，
indptr[v+1] - indptr[v]这类索引差值计算会变慢，因为跨行访问在 F-order 中不是连续地址 - 验证方式：
arr.flags.c_contiguous必须为True；arr.strides应满足strides[0] == arr.itemsize * arr.shape[1] - 注意：不要对 CSR 数据调用
np.asfortranarray()，哪怕后续要转置——图结构本身极少需要整体转置
避免临时 list 推导式和 generator 在 hot loop 中创建对象
常见错误是在 BFS 队列扩展时写 neighbors = [u for u in adj_list[v] if not visited[u]]。这每轮都新建 list，触发内存分配 + 引用计数更新，实测在千万级图上拖慢 3–5 倍。
- 改用预分配布尔掩码 +
np.where()：先算好mask = ~visited[indices[start:end]]，再np.compress(mask, indices[start:end]) - 或直接用
numba.jit(nopython=True)写一个纯数组循环函数，绕过 Python 对象层 - 禁用
gc.disable()在图遍历主循环前（确保不被垃圾回收打断），结束后再gc.enable() - 别依赖
itertools.chain拼接多个切片——它返回的是迭代器，每次next()都有函数调用开销；直接用np.concatenate()预合成一个临时数组更稳
内存映射与分块加载适合超大规模图
当图边数超过物理内存（比如百亿边），强行全载入会触发 swap，性能断崖下跌。这时得放弃“全图驻留”，改用分块策略。
- 把
indices按节点范围切分成多个.npy文件（如每 100 万节点一个文件），用np.memmap映射，仅在需要时 page-in -
indptr必须全加载到内存（它才几 MB），用于快速定位某节点邻居落在哪个文件哪一段 - 避免用
pandas.read_parquet加载边表：列存格式对邻接查询不友好；行存二进制（如struct.pack打包的u4,u4对）+np.frombuffer()更快 - 如果图是静态的，可提前用
zstd压缩indices，CPU 解压速度（>500 MB/s）远高于 SSD 读取未压缩数据的 I/O 延迟
真正卡住性能的往往不是算法复杂度，而是你手里的 adj_list[v] 返回的是 Python list 还是 NumPy ndarray；不是有没有用 JIT，而是 indptr 数组是不是 C-contiguous。这些细节不改，换再 fancy 的图神经网络库也没用。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
