为什么访问稀疏矩阵代价高？

Question

我有一个1034乘1034的稀疏矩阵（scipy.sparse.csr.csr_matrix），这个矩阵基本上是一个图的邻接矩阵。我想检查一些元素是否为1。但是我发现这个操作非常慢。在执行if语句之前，代码运行需要11秒，但一旦我启用这个检查，它就变成了40秒！

这是我的代码片段：

target = list()
for edge_id in edges_ids:
    v1_label, v2_label = from_edgeID_to_vertix_labels(edge_id) #fast
    v1_index = g.get_v_index(v1_label) #fast
    v2_index = g.get_v_index(v2_label) #fast

    #if the following chunk is enabled, it becomes slow!     
    if A[v1_index, v2_index] == 1:
        target.append(1)
    else:
        target.append(0)
g.target = target

Answer 1

在这种情况下，使用一个嵌套的默认字典可能会更好：

from collections import defaultdict
A = defaultdict(lambda : defaultdict(int))
# Example of how to set an element in the adjacency matrix:
A[1][2] = 1

不过，这种方法不支持numpy或scipy提供的任何矩阵操作，但对于特定的使用场景来说，它应该会很快。

Answer 2

原因很可能是，从稀疏矩阵的CSR（压缩行存储）或CSC（压缩列存储）形式中，根据给定的索引（i, j）获取单个值是非常耗费资源的。这些稀疏矩阵的算法通常不是为了这样做而设计的：它们是为了在顺序遍历数组时使用找到的索引。

在CSR中，当你查找某一行时，实际上你会得到一个列索引和对应值的数组。如果你要获取一个单独的值，你必须在这个小的列索引数组中进行线性搜索（通常是无序的），看看这个值是否存在（如果不存在，值就是零）；如果找到了，你再从值数组中取出这个值并返回。这个过程可能看起来像这样（这只是一个示例，C代码）：

/* Obviously silly CSR matrix typedef */
typedef struct sparse_s {
    int    row[nnz+1];
    int    col[nnz];
    double value[nnz];
} sparse_s;


double spGetValue(sparse_s const* s, int i, int j)
{
    int k;

    for(k=s->row[i]; k<s->row[i+1]; k++) {
        if( j == s->col[k] ) {
            return s->value[k];
        }
    }
    return 0.0;
}

所以，如果你想在每一行上平均取10个元素，你就得为每次访问搜索一个包含十个元素的数组。这对像SpMV这样的算法来说问题不大，因为它们在找到列索引时就直接使用它们。如果你像处理密集矩阵那样实现SpMV，获取每个值，即使你有某种神奇的方法来跳过零值，这样做也会非常非常慢。如果你觉得这已经很糟糕了，往CSR/CSC矩阵中插入一个元素是极其昂贵的，几乎是不会被做的。

简而言之，你可能会通过重新组织代码，使其直接遍历CSR矩阵的三个向量，或者为这个特定问题使用不同的稀疏矩阵表示，来获得更好的结果。

这可能会更“符合Python风格”，但即使在最好的情况下，如果保留矩阵表示和访问方法，我也不指望你的代码在C中表现良好。