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

#define MAX_NONZEROS 100000
#define MAX_SIZE 1024

// COO格式的稀疏矩阵结构
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() % MAX_SIZE; 
        matrix->colIndex[i] = rand() % MAX_SIZE; 
    }
}

// 基础稀疏矩阵乘法函数
void sparse_matmul(SparseMatrix *A, SparseMatrix *B, SparseMatrix *C) {
    C->nonZeroCount = 0;
    for (int i = 0; i < A->nonZeroCount; i++) {
        for (int j = 0; j < B->nonZeroCount; j++) {
            if (A->colIndex[i] == B->rowIndex[j]) {
                int cRow = A->rowIndex[i];
                int cCol = B->colIndex[j];
                float cValue = A->values[i] * B->values[j];


                int k;
                for (k = 0; k < C->nonZeroCount; k++) {
                    if (C->rowIndex[k] == cRow && C->colIndex[k] == cCol) {
                        C->values[k] += cValue;
                        break;
                    }
                }
                if (k == C->nonZeroCount) {
                    C->values[k] = cValue;
                    C->rowIndex[k] = cRow;
                    C->colIndex[k] = cCol;
                    C->nonZeroCount++;
                }
            }
        }
    }
}

int main() {
    SparseMatrix A, B, C;


    int nonZeroCountA = 500; 
    int nonZeroCountB = 300; 
    initSparseMatrix(&A, nonZeroCountA);
    initSparseMatrix(&B, nonZeroCountB);

  
    clock_t start, end;
    start = clock();

  
    sparse_matmul(&A, &B, &C);

    end = clock();
    double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("稀疏矩阵乘法的运行时间为: %lf 秒\n", time_spent);

    return 0;
}