如何高效实现CSR存储格式的转换？

### CSR存储格式的转换，，CSR（Compressed Sparse Row）是一种用于稀疏矩阵的存储格式，将非零元素及其位置信息存储在三个一维数组中，包括values、column_indices和row_ptr。这种格式通过行优先遍历矩阵，压缩存储非零元素，提高存储和计算效率。

CSR（Compressed Sparse Row）存储格式是一种用于高效存储稀疏矩阵的格式，特别适合于行向量操作，如矩阵-向量乘法，下面将详细介绍CSR存储格式的转换过程，包括从COO（Coordinate Format）到CSR的转换，以及相关的实现细节和示例代码。

一、CSR存储格式

CSR格式通过三个数组来存储稀疏矩阵：

1、row_ptr：存储每行非零元素的开始位置。

2、col_ind：存储非零元素的列索引。

3、data：存储非零元素的数值。

二、从COO转换到CSR的步骤

COO（Coordinate List）格式是另一种常见的稀疏矩阵存储格式，它通过三个数组存储非零元素的位置和数值：

1、row：存储非零元素的行索引。

2、col：存储非零元素的列索引。

3、data：存储非零元素的数值。

排序行索引

需要对COO格式的数据进行排序，以确保所有相同行的元素在一起，这可以使用常见的排序算法，如快速排序或归并排序，排序的目的是让数据在转换过程中更容易处理。

构造行指针数组

在CSR格式中，row_ptr数组用于指示每行的非零元素在data数组中的起始位置，为了构造这个数组，我们需要遍历排序后的行索引数组，记录每行的非零元素数量。

重新排序列索引和数值数组

在排序行索引之后，我们需要相应地重新排列列索引和数值数组，以确保它们与新的行顺序一致。

三、C语言实现从COO转换到CSR

以下是一个使用C语言实现从COO转换到CSR的示例代码：

#include <stdio.h>
#include <stdlib.h>
// COO格式的稀疏矩阵
typedef struct {
    int *row;
    int *col;
    double *data;
    int nnz;  // 非零元素的数量
    int rows; // 矩阵的行数
    int cols; // 矩阵的列数
} COOMatrix;
// CSR格式的稀疏矩阵
typedef struct {
    int *row_ptr;
    int *col_ind;
    double *data;
    int nnz;
    int rows;
    int cols;
} CSRMatrix;
// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    int row_a = *((int*)a);
    int row_b = *((int*)b);
    return row_a row_b;
}
// 排序COO格式的行索引
void sort_coo(COOMatrix *coo) {
    int *row_copy = (int*)malloc(coo->nnz * sizeof(int));
    int *col_copy = (int*)malloc(coo->nnz * sizeof(int));
    double *data_copy = (double*)malloc(coo->nnz * sizeof(double));
    // 复制原始数组
    for (int i = 0; i < coo->nnz; i++) {
        row_copy[i] = coo->row[i];
        col_copy[i] = coo->col[i];
        data_copy[i] = coo->data[i];
    }
    // 排序
    qsort(row_copy, coo->nnz, sizeof(int), compare);
    // 重新排列col和data数组
    for (int i = 0; i < coo->nnz; i++) {
        for (int j = 0; j < coo->nnz; j++) {
            if (row_copy[i] == coo->row[j]) {
                coo->col[i] = col_copy[j];
                coo->data[i] = data_copy[j];
                break;
            }
        }
    }
    // 更新row数组
    for (int i = 0; i < coo->nnz; i++) {
        coo->row[i] = row_copy[i];
    }
    free(row_copy);
    free(col_copy);
    free(data_copy);
}
// 从COO转换为CSR的函数
CSRMatrix* coo_to_csr(COOMatrix *coo) {
    CSRMatrix *csr = (CSRMatrix*)malloc(sizeof(CSRMatrix));
    csr->rows = coo->rows;
    csr->cols = coo->cols;
    csr->nnz = coo->nnz;
    csr->row_ptr = (int*)malloc((csr->rows + 1) * sizeof(int));
    csr->col_ind = (int*)malloc(csr->nnz * sizeof(int));
    csr->data = (double*)malloc(csr->nnz * sizeof(double));
    // 初始化row_ptr数组
    for (int i = 0; i <= csr->rows; i++) {
        csr->row_ptr[i] = 0;
    }
    // 统计每行的非零元素数量
    for (int i = 0; i < coo->nnz; i++) {
        csr->row_ptr[coo->row[i] + 1]++;
    }
    // 累加row_ptr数组
    for (int i = 0; i < csr->rows; i++) {
        csr->row_ptr[i + 1] += csr->row_ptr[i];
    }
    // 填充col_ind和data数组
    for (int i = 0; i < coo->nnz; i++) {
        int row = coo->row[i];
        int dest_index = csr->row_ptr[row];
        csr->col_ind[dest_index] = coo->col[i];
        csr->data[dest_index] = coo->data[i];
        csr->row_ptr[row]++;
    }
    // 调整最后一个元素的row_ptr为总的非零元素数
    csr->row_ptr[csr->rows] = csr->nnz;
    return csr;
}