python - 为什么 python 上的稀疏矩阵计算太慢

Question

我使用的格式是 csr 稀疏矩阵，推荐它是加法和点运算符最快的稀疏结构。我将其性能与 np.array 的加法和点运算符进行了比较。然而，稀疏矩阵的计算比密集格式的情况慢得多，这似乎很奇怪。为什么？有没有更有效的方法来实现稀疏计算？

import numpy as np
import scipy.sparse as sp
import random

#%% generate dense vector
vector_length = 10000
nonzero_term = 200

x = np.zeros((vector_length, ))
y = np.zeros((vector_length, ))

index = random.sample(range(vector_length), nonzero_term)
x[index] = np.random.rand(nonzero_term)
index = random.sample(range(vector_length), nonzero_term)
y[index] = np.random.rand(nonzero_term)

#%% transform to sparse vector
x_sp = sp.csr_matrix(x)
y_sp = sp.csr_matrix(y)

#%% test

# dense add
%timeit [x + y]
# sparse add
%timeit [x_sp + y_sp]     
# dense dot
%timeit [x.dot(y)]
# sparse dot
%timeit [x_sp.dot(y_sp.T)] 

结果显示

100000 loops, best of 3: 6.06 µs per loop
10000 loops, best of 3: 97.8 µs per loop
100000 loops, best of 3: 3.45 µs per loop
1000 loops, best of 3: 225 µs per loop

Answer 1

两组操作都使用编译代码。但是数据的存储方式却大不相同。

x.shape 是 (10000,); y 同样。 x+y 只需分配一个相同形状的数组，并在 c 中高效地遍历 3 个数据缓冲区。

x_sp 有 200 个非零值，这些值在 x_sp.data 中，它们的列索引在 x_sp.indices 中。还有第三个数组 x_sp.indptr 但只有 2 个值。 y_sp 也类似。但是要添加它们，它必须遍历 4 个数组，并为两个数组赋值。即使在 c 中编码，也有很多工作要做。在我的测试用例中，x_sp+y_sp 有 397 个非零值。

对于这些一维数组(1 行矩阵)，点 涉及相同类型的值步进，只是将它们全部相加为一个最终值。

如果矩阵的密度足够低，稀疏计算可以更快。我认为，矩阵乘法比加法更是如此。

总而言之，对于稀疏矩阵，每个元素的计算更加复杂。所以即使元素很少，整体时间也趋于变长。