#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    float* values;
    int* rowIndex;
    int* colIndex;
    int nonZeroCount;
} SparseMatrix;

void sparseToDense(SparseMatrix* A, float** denseA, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            denseA[i][j] = 0.0;
        }
    }

    for (int k = 0; k < A->nonZeroCount; k++) {
        int row = A->rowIndex[k];
        int col = A->colIndex[k];
        float val = A->values[k];
        denseA[row][col] = val;
    }
}

void matmul(float** A, float** B, float** C, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            float sum = 0.0;
            for (int k = 0; k < n; k++) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
}

int main() {
    // 假设已经有了两个稀疏矩阵A和B
    SparseMatrix A, B;
    // 初始化A和B...

    int rowsA = A.rowIndex[A.nonZeroCount];
    int colsA = A.colIndex[A.nonZeroCount];
    int rowsB = B.rowIndex[B.nonZeroCount];
    int colsB = B.colIndex[B.nonZeroCount];

    float** denseA = (float**)malloc(rowsA * sizeof(float*));
    float** denseB = (float**)malloc(rowsB * sizeof(float*));
    float** denseC = (float**)malloc(rowsA * sizeof(float*));

    for (int i = 0; i < rowsA; i++) {
        denseA[i] = (float*)malloc(colsA * sizeof(float));
        memset(denseA[i], 0, colsA * sizeof(float));
    }
    for (int i = 0; i < rowsB; i++) {
        denseB[i] = (float*)malloc(colsB * sizeof(float));
        memset(denseB[i], 0, colsB * sizeof(float));
    }
    for (int i = 0; i < rowsA; i++) {
        denseC[i] = (float*)malloc(colsB * sizeof(float));
        memset(denseC[i], 0, colsB * sizeof(float));
    }

    sparseToDense(&A, denseA, rowsA, colsA);
    sparseToDense(&B, denseB, rowsB, colsB);

    clock_t start = clock();
    matmul(denseA, denseB, denseC, rowsA);
    clock_t end = clock();

    printf("优化的稀疏矩阵乘法耗时: %lf 毫秒\n", 1000.0 * (end - start) / CLOCKS_PER_SEC);

    return 0;
}