从 CSR/CSC 到 GCXSsparse 多维压缩格式的工作原理深度解析【免费下载链接】sparseSparse multi-dimensional arrays for the PyData ecosystem项目地址: https://gitcode.com/gh_mirrors/sp/sparse稀疏数组是 PyData 生态中处理海量零元素数据的核心武器。今天我们要深度解析的是sparse 多维压缩格式—— 它正是 GitHub 加速计划 sp/sparse 项目Sparse multi-dimensional arrays for the PyData ecosystem中 GCXS 格式的核心。GCXS 是经典 CSR/CSC 格式向 N 维数组的推广在 PyData 生态中sparse 库通过 GCXS 把二维的行压缩思想扩展到任意维度让高维稀疏张量的存储效率提升一个数量级。这篇文章将带你从 CSR/CSC 出发一步步看懂 GCXS 的原理、存储布局与源码实现即使你是稀疏存储的新手也能轻松入门。为什么需要稀疏存储先看一个反直觉的事实假设你有一个形状为(1000, 1000, 1000)的三维数组其中有 1% 的元素非零。按 dense 方式存储需要 10 亿个元素的容量而真正有意义的数据只有 1000 万个。如果还按普通数组存99% 的内存都被浪费了。sparse 稀疏数组的价值就在这里只记录哪里有什么而不是哪里有什么都没有。复习一下 CSR/CSC二维稀疏矩阵的黄金标准在动手理解 GCXS 之前必须先把 CSRCompressed Sparse Row压缩稀疏行和 CSCCompressed Sparse Column压缩稀疏列吃透。它们只用三个数组就能完整描述一个稀疏矩阵数组含义data所有非零元素的值长度 nnz非零个数indices每个非零元素在行内的列坐标indptr每一行第一个非零元素在data中的起始位置长度 行数 1举个例子一个 4×4 矩阵中只有 4 个非零元素data [10, 13, 9, 21] indices [0, 2, 3, 8] indptr [0, 2, 3, 3, 4]读取方式很简单第i行的非零元素位于data[indptr[i]:indptr[i1]]。CSR/CSC 之所以能成为科学计算的事实标准是因为它们压缩率高、且非常适合逐行逐列的数学运算比如稀疏矩阵乘法SpMV。COO 的困境维度每加一维存储成本就翻倍把稀疏数组从二维推广到三维以上最直觉的方案是 COOCoordinate List坐标列表。COO 用一个(ndim, nnz)的坐标矩阵加一个(nnz,)的值数组把每个非零元素的多维下标全部显式记录下来。问题也随之而来COO 的存储开销与维度数强相关。在二维时每个元素只需记 2 个坐标到五维就要记 5 个坐标坐标数组的体积直接翻了 2.5 倍。对于动辄四维、五维的张量数据比如张量分解、深度学习中的张量运算COO 的坐标税高得吓人。这正是 GCXS 要解决的核心痛点。相关对比可参考项目文档 docs/introduction.md 中的格式设计章节。GCXS 工作原理把 CSR 的行压缩升维GCXS 全称 General Compressed eXtended Sparse其理论基础来自 2015 年发表的 GCRS/GCCS 论文Efficient storage scheme for n-dimensional sparse array。它的核心思想极其优雅把多维数组重新组织成压缩维度和非压缩维度两部分压缩维度合并成一个大行其余维度合并成一个大列然后套用 CSR 的三数组布局。在 sparse 库中GCXS 类实现于sparse/numba_backend/_compressed/compressed.py它依然由data、indices、indptr三个数组组成data非零值长度 nnzindices非零元素在非压缩维度合并后的坐标indptr每个压缩行的起始偏移。二维时 GCXS CSR/CSC这是最妙的一点当ndim 2时GCXS 与 CSR/CSC 完全等价。源码注释明确写着For arrays with ndim 2, GCXS is the same CSR/CSC。也就是说你不需要学习一套全新的格式二维场景下它就是熟悉的配方。三维以上压缩轴的自由选择对于 N 维数组compressed_axes参数决定了压缩哪些轴。默认情况下sparse 会选择形状最小的那个轴进行压缩以获得最佳压缩比。源码中的_from_coo函数if compressed_axes is None: # defaults to best compression ratio compressed_axes (np.argmin(x.shape),)实际转换过程分四步见sparse/numba_backend/_compressed/compressed.py重排轴把压缩轴放到最前面其余轴按原序放在后面线性化用linear_loc把多维坐标压成一维线性坐标排序分组按线性坐标排序相同行的元素聚到一起构造 indptr用np.bincountcumsum生成每行起始指针indices记录列坐标。存储对比GCXS 到底能省多少内存用一个具体例子量化感受一下。假设一个形状(10, 10, 10)的三维数组nnz 100索引用 int32存储格式索引数组体积说明稠密数组10 × 10 × 10 × 8B 8000B全量存储COO3 × 100 × 4B 1200B每个元素记 3 个坐标GCXS压缩 1 轴(100 100 11) × 4B ≈ 844B压缩轴只记行指针维度越高差距越悬殊。GCXS 的存储成本几乎不受维度数影响只与 nnz 和一个压缩轴的规模相关这正是它与 COO 的本质区别。官方文档 docs/introduction.md 中对此有明确表述。实战如何创建和转换 GCXS 数组在 sparse 库中创建 GCXS 数组的方式非常灵活核心入口都可以从sparse/numba_backend/_compressed/compressed.py的类方法中找到一键转换 SciPy 稀疏矩阵from_scipy_sparse方法直接把scipy.sparse的 CSR/CSC 矩阵变成 GCXS且自动识别压缩轴方向import sparse from scipy import sparse as sp csr sp.random(100, 100, density0.1, formatcsr) g sparse.GCXS.from_scipy_sparse(csr) # compressed_axes(0,)从 NumPy 稠密数组转换import numpy as np x np.random.random((20, 30, 40)) x[x 0.9] 0 # 制造 90% 的零 g sparse.GCXS.from_numpy(x)动态更换压缩轴GCXS 还提供了change_compressed_axes方法相当于把 CSR 换成 CSC——但可以在任意维度之间切换g2 g.change_compressed_axes((1,)) # 换一个轴压缩进阶技巧如何选择最优的压缩轴选对压缩轴能让存储和运算双双受益这里给出三条可操作的建议默认选形状最小的轴这是库的默认策略通常压缩比最高按运算模式选轴如果后续要做沿某个轴的规约sum、max把该轴作为压缩轴可以让indptr直接参与分组运算源码_reduce_calc就是这么利用压缩轴加速的转置后再压缩高维转置后原压缩轴失效sparse 会在转置时自动重排坐标无需手动干预。小结从 CSR/CSC 到 GCXS本质上是一次降维打击把 N 维稀疏数组重排成二维结构后复用成熟的 CSR 三数组布局。GCXS 既保留了 CSR 高压缩率、适合批量运算的优点又打破了它只能处理二维矩阵的枷锁。对 PyData 生态中的张量分解、图计算、深度学习场景来说sparse 库的这个 GCXS 格式是处理高维稀疏数据绕不开的利器。如果你准备上手克隆仓库后重点阅读sparse/numba_backend/_compressed/目录下的compressed.py、convert.py与common.py就能完整吃透这套设计。【免费下载链接】sparseSparse multi-dimensional arrays for the PyData ecosystem项目地址: https://gitcode.com/gh_mirrors/sp/sparse创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
