python - 为什么访问稀疏矩阵很昂贵？

Question

我有一个 1034_by_1034 稀疏矩阵 (scipy.sparse.csr.csr_matrix)，它基本上表示图的邻接矩阵。我想检查一些元素是否是。但我发现这是一个非常缓慢的操作。在 if 语句 之前，代码在 11 秒内运行，但当我启用 if 检查时，它需要 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

原因很可能是从 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 这样使用列索引的算法来说，这不是一个问题。如果你像密集 MM 一样实现 SpMV，获取每个值，即使你有一些跳过零的神奇魔法，它也会非常慢。如果您认为这很糟糕，将一个元素插入 CSR/CSC 矩阵的代价非常高，以至于(几乎)从未有人这样做过。

简而言之，您可能会通过重新组织代码以便直接迭代 CSR 矩阵的三个向量或针对此特定问题使用不同的稀疏矩阵表示来获得更好的结果。

它可能更像“Python”，但如果保留矩阵表示和访问方法，我不希望您的代码即使在 C 的最佳情况下也能表现良好。