У меня есть вопрос о коде умножения разреженной матрицы в C

Question

Я изучаю разреженную матрицу в "Основах структур данных в 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

Это часть о так называемом "граничном условии", которая заставляет меня путать с этим кодом. Я не понимаю, почему это условие необходимо. Разве это не хорошо без этих условий?

Умножение матриц может быть вычислено без включения дополнительной записи, да, но данная функция не будет делать это правильно, нет.

В книге сказано: "... эти фиктивные термины служат в качестве стражей, которые позволяют нам получить изящный алгоритм .."

Это немного расплывчато, я согласен. Рассмотрим, как работает алгоритм: для каждой строки матрицы A он должен сканировать каждый столбец матрицы B (== строка матрицы newB), чтобы вычислить один элемент матрицы продукта. Но выбранное представление разреженной матрицы не записывает, сколько элементов имеется в каждой строке или столбце, поэтому единственный способ узнать, когда вы обработали последний элемент для данного столбца, - это посмотреть next один в линейном элементном порядке, и видите, что он принадлежит новому столбцу.

Данный код объединяет проверку на конец столбца и хранение результирующего элемента в обработку следующего элемента, но это оставляет проблему: что вы делаете с последним элементом в списке элементов матрицы? У него нет следующего элемента для запуска записи элемента матрицы результатов - по крайней мере, не натурального. Эту проблему можно решить с помощью некоторой логики специального случая, но удобнее просто добавить синтетический дополнительный элемент, который определенно принадлежит другому столбцу, чтобы конец матрицы больше не представлял собой особый случай.

Я не уверен, что согласен с тем, что термин «страж» подходит для этого. На самом деле это просто противоположность стражу во многих отношениях. Термин обычно означает специальное значение, которое не может быть частью обычных данных и поэтому может быть распознано как маркер конца данных. Строковые терминаторы являются примером. Этот «страж», с другой стороны, работает, имитируя реальные данные. Тем не менее, это дополнительный, искусственный элемент в конце списка, и в этом смысле это не сумасшествие, чтобы назвать его часовым.