SciPy 稀疏矩阵（6）：CSC

“

上回说到，CSR 格式的稀疏矩阵基于程序的空间局部性原理把当前访问的内存地址以及周围的内存地址中的数据复制到高速缓存或者寄存器（如果允许的话）来对 LIL 格式的稀疏矩阵进行性能优化。但是，我们都知道，无论是 LIL 格式的稀疏矩阵还是 CSR 格式的稀疏矩阵全都把稀疏矩阵看成有序稀疏行向量组。然而，稀疏矩阵不仅可以看成是有序稀疏行向量组，还可以看成是有序稀疏列向量组。我们完全可以把稀疏矩阵看成是有序稀疏列向量组，然后模仿 LIL 格式或者是 CSR 格式对列向量组中的每一个列向量进行压缩存储。然而，模仿 LIL 格式的稀疏矩阵格式 SciPy 中并没有实现，大家可以尝试自己去模仿一下，这一点也不难。因此，这回直接介绍模仿 CSR 格式的稀疏矩阵格式——CSC 格式。

”

PART. 01

SciPy CSC 格式的稀疏矩阵

SciPy CSC 格式的稀疏矩阵和 SciPy CSR 格式的稀疏矩阵差不多，属性名都是一样的，唯一不一样的地方就是 SciPy CSC 格式的稀疏矩阵把稀疏矩阵看成有序稀疏列向量组而 SciPy CSR 格式的稀疏矩阵把稀疏矩阵看成有序稀疏行向量组。之所以这种格式被我们称之为 CSC，是因为 CSC 是 Compressed Sparse Column 的缩写。

实例化

SciPy CSC 格式的稀疏矩阵类的定义位于 scipy.sparse 包中的 csc_matrix 类，对其进行实例化就能获取一个 SciPy CSC 格式的稀疏矩阵的实例。当然，构造实例的方法主要有 5 种：

1. csc_matrix(D)：D 是一个普通矩阵（二维数组）。
2. csc_matrix(S)：S 是一个稀疏矩阵。
3. csc_matrix((M, N), [dtype])：会实例化一个 M 行 N 列元素类型为 dtype 的全 0 矩阵。dtype 是一个可选参数，默认值为双精度浮点数。
4. csc_matrix((data, (row_ind, col_ind)), [shape=(M, N)])：data 是非零元素值，row_ind 是非零元素行索引，col_ind 是非零元素的列索引，shape 是矩阵的行列数（M 行 N 列），默认会通过非零元素行索引外加上非零元素列索引进行推断。
5. csc_matrix((data, indices, indptr), [shape=(M, N)])：第 i 列非零元素的行索引是 indices[indptr[i]:indptr[i+1]]，对应的非零元素值存储在 data[indptr[i]:indptr[i+1]]，shape 是矩阵的行列数（M 行 N 列），默认会通过 indices 和 indptr 进行推断。

案例

实例化一个 3 行 4 列元素类型为 8 位有符号整数的全 0 矩阵：

>>> import numpy as np
>>> from scipy.sparse import csc_matrix
>>> csc_matrix((3, 4), dtype=np.int8).toarray()
array([[0, 0, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 0]], dtype=int8)

通过元素值序列、行索引序列以及列索引序列来实例化一个 3 行 3 列元素值为 32 位有符号整数的稀疏矩阵：

>>> row = np.array([0, 2, 2, 0, 1, 2])
>>> col = np.array([0, 0, 1, 2, 2, 2])
>>> data = np.array([1, 2, 3, 4, 5, 6])
>>> csc_matrix((data, (row, col)), shape=(3, 3)).toarray()
array([[1, 0, 4],
       [0, 0, 5],
       [2, 3, 6]], dtype=int32)

通过第 5 种实例化方法实例化一个稀疏矩阵：

>>> indptr = np.array([0, 2, 3, 6])
>>> indices = np.array([0, 2, 2, 0, 1, 2])
>>> data = np.array([1, 2, 3, 4, 5, 6])
>>> csc_matrix((data, indices, indptr), shape=(3, 3)).toarray()
array([[1, 0, 4],
       [0, 0, 5],
       [2, 3, 6]])

依旧是通过元素值序列、行索引序列以及列索引序列来实例化一个 3 行 3 列元素值为 32 位有符号整数的稀疏矩阵，只不过这次我们看看相同的行列索引重复出现会怎样：

>>> row = np.array([0, 1, 2, 0])
>>> col = np.array([0, 1, 1, 0])
>>> data = np.array([1, 2, 4, 8])
>>> csc_matrix((data, (row, col)), shape=(3, 3)).toarray()
array([[9, 0, 0],
       [0, 2, 0],
       [0, 4, 0]], dtype=int32)

显然，重复的行列索引把对应值相加，这和 COO 格式的稀疏矩阵处理方式完全一样。

依旧是通过第 5 种方法来实例化一个元素值为 32 位有符号整数的稀疏矩阵，只不过这次我们看看某一列的行索引重复出现会怎样：

>>> indices = [0, 1, 0, 2, 3, 1]
>>> data = [1, 1, 1, 1, 1, 1]
>>> indptr = [0, 3, 6]
>>> csc_matrix((data, indices, indptr), dtype=int).toarray()
array([[2, 0],
       [1, 1],
       [0, 1],
       [0, 1]])

显然，在这里处理的方式是把一列中重复行索引的对应值相加，和 COO 格式的稀疏矩阵差不多。当然，该实例的 indptr 属性、indices 属性、data 属性就是之前获取的 3 个同名列表，根本不做重复相加等化简操作。如何进行重复相加等化简操作只需要调用 sum_duplicates() 方法，调用该方法不仅会把重复的行索引的对应值相加，还会把同一列的行索引按从小到大的顺序排好。然而，这个方法并不完美，特别是当重复的行索引的对应值相加之后正好为 0，它根本不会自动去掉这样的零元素，删除零元素还需调用 eliminate_zeros() 方法。这 2 个方法都是原地操作，无返回值。现在方法有了，怎么消除零元素以及重复的行索引无非就是两个方法的调用顺序的问题。显然我们应该先消除重复的行索引，再消除零元素。反过来之所以不行是因为可能存在重复 2 次的行索引，一个地方元素值为 1，另一个地方元素值为 -1，显然它们都不是 0，所以先消除零元素不能把它们消去，然后消除重复的行索引把它们加在一起又出现了零元素。

优缺点

SciPy CSC 格式的稀疏矩阵有着以下优点：

1. 进行算术操作的性能非常高效。
2. 进行列切片操作的性能非常高效。
3. 进行矩阵乘向量运算的操作特别迅速。

当然，SciPy CSC 格式的稀疏矩阵也有缺点：

1. 进行行切片操作的性能非常低下。
2. 对其修改矩阵元素的代价非常高昂。

PART. 02

下回预告

不同于 LIL 格式和 CSR 格式都是把稀疏矩阵看成有序稀疏行向量组，然后对行向量组中每一个行向量进行压缩存储，CSC 格式把稀疏矩阵看成有序稀疏列向量组，然后通过模仿 CSR 格式来对列向量组中每一个列向量进行压缩存储。

然而，学过线性代数的人都非常地清楚，一个大矩阵可以分成很多个小矩阵，这样的矩阵被我们称之为分块矩阵。对于一个大的稀疏矩阵我们显然也可以进行分块，只不过绝大多数情况下大量的块是元素全为零的矩阵，显然，我们可以通过仅存储非零矩阵块也能实现稀疏矩阵的压缩存储。因此，我们可以模仿之前的所有的稀疏矩阵格式，只要把非零元素换成非零矩阵块即可。然而，SciPy 中仅实现了模仿 CSR 格式的稀疏矩阵格式，模仿其他稀疏矩阵的格式全都没有实现，大家可以尝试自己去模仿一下，这一点也不难。大家可以尝试自己去模仿一下，这一点也不难。因此，下回直接介绍模仿 CSR 格式的稀疏矩阵格式——BSR 格式。