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

#define SIZE 100
#define MAX_NONZEROS 1000

typedef struct {
    float values[MAX_NONZEROS];
    int rowIndex[MAX_NONZEROS];
    int colIndex[MAX_NONZEROS];
    int nonZeroCount;
} SparseMatrix;

void initSparseMatrix(SparseMatrix *matrix, int nonZeroCount) {
    matrix->nonZeroCount = nonZeroCount;
    for (int i = 0; i < nonZeroCount; i++) {
        matrix->values[i] = (float)(rand() % 100) / 10.0f;
        matrix->rowIndex[i] = rand() % SIZE;
        matrix->colIndex[i] = rand() % SIZE;
    }
}

void sparseToDense(const SparseMatrix *sparse, float dense[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            dense[i][j] = 0.0f;
        }
    }
    for (int i = 0; i < sparse->nonZeroCount; i++) {
        dense[sparse->rowIndex[i]][sparse->colIndex[i]] = sparse->values[i];
    }
}

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

int main() {
    SparseMatrix A, B;
    clock_t start, end;
    float denseA[SIZE][SIZE], denseB[SIZE][SIZE], denseC[SIZE][SIZE];

    initSparseMatrix(&A, 500); 
    initSparseMatrix(&B, 300); 
    
    start = clock();

    sparseToDense(&A, denseA);
    sparseToDense(&B, denseB);

    matmul(denseA, denseB, denseC);

    end = clock();

    double timeSpent = double(end - start) / CLOCKS_PER_SEC;

    printf("优化后的稀疏矩阵乘法用时: %e", timeSpent);

    printf("Result matrix C (partial):\n");
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            printf("%.2f ", denseC[i][j]);
        }
        printf("\n");
    }

    return 0;
}