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

Question

我使用的格式是csr稀疏矩阵，它被推荐为add和dot算子最快的稀疏结构。我将其性能与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 is (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个非零值。

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

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

总而言之，稀疏矩阵下的每元素计算更为复杂。因此，即使元素很少，总体时间也会变长。