c - 我有一个关于 C 中稀疏矩阵乘法代码的问题

Question

我正在 Horowitz 的“C 数据结构基础知识”中学习稀疏矩阵。 我的问题是关于稀疏矩阵乘法!我确实知道它是如何工作的和算法，但我无法理解代码。

下面是关于“mmult”的代码

正是关于所谓的“边界条件”的部分让我对这段代码感到困惑。我不明白为什么需要这个条件。没有这些条款不是很好吗？我需要一些帮助来理解这一部分...

书上说“......这些虚拟术语充当哨兵，使我们能够获得优雅的算法......”

typedef struct {
int row;
int col;
int value;
} SM; // type SM is "Sparse Matrix"

void mmult(SM* A, SM* B, SM*C) {
int i, j;
int rowsA, colsB, totalA, totalB, totalC; 
int rowbegin, A_Row, B_Col, sum;
SM* newB;

rowsA = A[0].row, colsB = B[0].col;
totalA = A[0].value, totalB = B[0].value;
totalC = 0;

if (A[0].col != B[0].row) {
    fprintf(stderr, "can't multiply\n");
}
transpose(B, newB) // newB is a transposed matrix from B

/* set boundary condition */
A[totalA+1].row = rowsA;
newB[totalB+1].row = colsB;
newB[totalB+1].col = -1;

rowbegin = 1;
for (i = 1, A_Row = A[1].row, sum = 0; i <= totalA;) {
    B_Col = newB[0].row;
    for (j = 1; j <= totalB + 1) { // don't know why it should be iterated by totalB+1
        /* current multiplying row != A[i].row */
        if (A[i].row != A_Row) {
            storesum(C, A_Row, B_Col, &totalC, &sum);
            for(;newB[j].row == B_Col;j++);
            i = rowbegin; // reset i to rowbegin, which is the first row term of current multiplying row;
        }
        /* current multiplying column != newB[j].col */
        else if (newB[j].row != B_Col) {
            storesum(C, A_Row, B_Col, &totalC, &sum);
            B_Col = newB[j].row;
            i = rowbegin;
        }
        /* Otherwise, during multiplication.. */
        else {
            switch(compare(A[i].col, newB[j].row)) {
            case -1 : 
                i++;
                break;
            case 0 : 
                sum += (A[i].value * newB[j].value);
                i++, j++;
                break;
            case 1 : j++;
            }
        }
    }
    for(;A[i].row == A_Row;) i++;
    A_Row = row[i].row;
    rowbegin = i;
}
}

void storesum(SM* C, int row, int col, int* totalC, int* sum) {
/* storesum is to store to C and set sum to 0 when multiplying current row or column is over */
if(*sum) {
    (*totalC)++;
    C[totalC].row = row;
    C[totalC].col = col;
    C[totalC].value = *sum;
    *sum = 0;
}
}

Answer 1

It is the part about so called "boundary condition" that makes me confused with this code. I don't understand why this condition is needed. Isn't it just fine without these terms??

可以在不包含额外条目的情况下计算矩阵乘法，是的，但是给定的函数无法正确执行，否。

The book says "...these dummy terms serve as sentinels that enable us to obtain an elegant algorithm.."

这有点含糊，我同意。考虑该算法的工作原理:对于矩阵 A 的每一行，它必须扫描矩阵 B 的每一列(== 矩阵 newB 的行)以计算乘积矩阵的一个元素。但所选择的稀疏矩阵表示不会记录每行或每列中有多少个元素，因此了解何时处理给定列的最后一个元素的唯一方法是查看下一个元素em> 按线性元素顺序排列，可以看到它属于一个新列。

给定的代码将对列末尾的检查和结果元素的存储集成到下一个元素的处理中，但这留下了一个问题:如何处理矩阵元素列表中的最后一个元素？它没有以下元素来触发结果矩阵元素的记录——至少不是一个自然的元素。这可以通过一些特殊情况逻辑来解决，但更简洁的是，只需添加一个肯定属于不同列的合成额外元素，这样矩阵的末尾就不再构成特殊情况。

我不确定我是否同意“哨兵”一词是否适合于此。事实上，它在很多方面都与哨兵相反。该术语通常表示不能成为普通数据一部分的特殊值，因此可以被识别为数据结束标记。字符串终止符就是一个例子。另一方面，这个“哨兵”通过模仿真实数据来工作。然而，它是列表末尾的一个额外的、人为的元素，从这个意义上说，称其为哨兵并不疯狂。