当前位置: 首页 > news >正文

矩阵压缩格式转换:COO转换CSC(C++)

目录

一、基本理论

1.1 COO格式

1.2 CSR格式

1.3 CSC格式

二、代码实现

三、测试


一、基本理论

        稀疏矩阵(Sparse Matrix)是大部分元素为零的矩阵,与之相对应的是稠密矩阵(Dense Matrix)。科学领域、工程计算、图形处理、机器学习等领域的大多数数据以稀疏矩阵的形式呈现。由于稀疏矩阵中含有大量的零元素,在矩阵计算过程中许多元素的迭代计算属于无效运算,为了减少不必要的运算,需要对稀疏矩阵进行处理,减少CPU和内存的无效消耗。最为有效、使用最广的方法是矩阵压缩,即稀疏矩阵存储时仅存储非0的数值以节约内存,计算时仅计算非0的部分以减少CPU消耗。

        常见的稀疏矩阵存储格式有:COO、CSR、CSC。

        以4x5的稀疏矩阵A为例:

A=\begin{bmatrix} 1 & 4 & 0 & 0 & 0\\ 0& 2 & 3 & 0 & 0\\ 5& 0 & 0 & 7 & 8\\ 0& 0 & 9 & 0 & 6 \end{bmatrix}

1.1 COO格式

        COO格式最为简单,与二维直角坐标系中某个点g=f(x,y)的表示形式相似,由行索引矩阵列索引矩阵非零数值矩阵组成,矩阵A对应的COO格式为:

COO\left\{\begin{matrix} data=[1\;\;4\;\;2\;\;3\;\;5\;\;7\;\;8\;\;9\;\;6]\\ row=[0\;\;0\;\;1\;\;1\;\;2\;\;2\;\;2\;\;3\;\;3]\\ col=[0\;\;1\;\;1\;\;2\;\;0\;\;3\;\;4\;\;2\;\;4] \end{matrix}\right.

1.2 CSR格式

        CSR(Compressed Sparse Row)格式由行指针矩阵列索引矩阵非零数值矩阵组成,矩阵A对应的CSR格式为:

CSR\left\{\begin{matrix} data=[1\;\;4\;\;2\;\;3\;\;5\;\;7\;\;8\;\;9\;\;6]\\ ptr=[0\;\;2\;\;4\;\;7\;\;9]\\ col=[0\;\;1\;\;1\;\;2\;\;0\;\;3\;\;4\;\;2\;\;4] \end{matrix}\right.

具体含义:非零数值矩阵和COO格式中的一致。假设有m行,行指针矩阵有m+1个元素,行指针矩阵中前m个元素为每一行的第一个非零数在数据矩阵中的角标,

        第一行的第一个非零元素为1,在数据矩阵中为第0个元素;

        第二行的第一个非零元素为2,在数据矩阵中为第2个元素;

        第三行的第一个非零元素为5,在数据矩阵中为第4个元素;

        第四行的第一个非零元素为9,在数据矩阵中为第7个元素。

在行指针矩阵中,最后一个元素的值统一为整个矩阵中非零元素的总值,即为m。

1.3 CSC格式

        CSC(Compressed Sparse Column)格式与CSR格式类似,只是CSC是列压缩,CSR为行压缩,由行索引矩阵列指针矩阵非零数值矩阵组成,矩阵A对应的CSC格式为:

CSC\left\{\begin{matrix} data=[1\;\;5\;\;4\;\;2\;\;3\;\;9\;\;7\;\;8\;\;6]\\row=[0\;\;2\;\;0\;\;1\;\;1\;\;3\;\;2\;\;2\;\;3] \\ ptr=[0\;\;2\;\;4\;\;6\;\;7\;\;9]\end{matrix}\right.

具体含义:非零数值矩阵和COO格式中的一致。假设有n列,列指针矩阵有n+1个元素,列指针矩阵中前n个元素为每一列的第一个非零数在数据矩阵中的角标,

        第一列的第一个非零元素为1,在数据矩阵中为第0个元素;

        第二列的第一个非零元素为4,在数据矩阵中为第2个元素;

        第三列的第一个非零元素为3,在数据矩阵中为第4个元素;

        第四列的第一个非零元素为7,在数据矩阵中为第6个元素;

        第五列的第一个非零元素为8,在数据矩阵中为第7个元素。

在行指针矩阵中,最后一个元素的值统一为整个矩阵中非零元素的总值,即为n。

二、代码实现

#include <stdlib.h>
#include <stdio.h>#pragma warning(disable:4996)int main(int argc, char *argv[])
{FILE *fp_a;FILE *fp_b;const char *filename1, *filename2, *filename3, *filename4;int i;int row_num, col_num, data_num, b_row_num, b_col_num;int *row, *col, *row1, *col1;double *data, *data1, *b;double e;//1//从原始稀疏矩阵数据文件中读取数据fp_b = fopen("Y_out_coo.txt", "r");if(fp_b == NULL){printf("Cannot open file a.\n");exit(0);}//从原始稀疏矩阵数据文件中读取矩阵的行数,列数,非零数目fscanf(fp_b, "%d %d %d", &row_num, &col_num, &data_num);printf("%d %d %d\n\n", row_num, col_num, data_num);//为读取矩阵市场的系数矩阵的行数组(row),列数组(col),数据数组开辟空间(data)row = (int*)malloc(sizeof(int)*data_num);col = (int*)malloc(sizeof(int)*data_num);data = (double*)malloc(sizeof(double)*data_num);//为稀疏矩阵csr格式的行数组(row1),列数组(col1),数据数组开辟空间(data1)row1 = (int*)malloc(sizeof(int)*data_num);col1 = (int*)malloc(sizeof(int)*(col_num+1));data1 = (double*)malloc(sizeof(double)*data_num);//从原始稀疏矩阵数据文件中读取矩阵全部的行元素,列元素,非零元数据//原始稀疏矩阵数据文件中存储的非零元素的行坐标,列坐标均从1开始for(i = 0; i < data_num; i++){fscanf(fp_b, "%d %d %lf", &row[i], &col[i], &data[i]);printf("%d %d %lf\n", row[i], col[i], data[i]);}fclose(fp_b);printf("稀疏矩阵coo格式读入完毕!\n");//输入Ax=b中b数据//从原始稀疏矩阵数据文件中读取数据fp_b = fopen("b_out_coo.txt", "r");if(fp_b == NULL){printf("Cannot open file b_out_coo\n");exit(0);}//从原始稀疏矩阵数据文件中读取矩阵的行数,列数,非零元数目fscanf(fp_b, "%d %d", &b_row_num, &b_col_num);printf("%d %d\n", b_row_num, b_col_num);//创建b数组输入b = (double*)malloc(sizeof(double)*b_row_num);for(i = 0; i < b_row_num; i++){fscanf(fp_b, "lf", &b[i]);}fclose(fp_b);printf("Ab数据读入完毕!\n");//2//矩阵coo格式转化为csc格式int j, k, count;count = 0;k = 0;for(i = 0; i <= col_num; i++)  //初始化csc格式的列数组{col1[i] = 0;}for(i = 0; i < data_num; i++)  //记录每列的数据数目{col1[col[i]]++;}for(i = 1; i <= col_num; i++)  //计算csc格式的列信息的数组,这里命名为row1{i = col1[col[j]-1]++;row1[i] = row[j] - 1;data1[i] = data[j];printf("%lf\n", data[j]);}printf("First step: csc col info has been done! \n");/**********输出文件名***********/filename1 = "Y_out_CSC_Ap.txt";filename2 = "Y_out_CSC_Ai.txt";filename3 = "Y_out_CSC_Ax.txt";filename4 = "Y_out_CSC_Ab.txt";if((fp_b = fopen(filename1, "w")) == NULL){printf("Cannot open file write!\n");exit(0);}for(i = 0; i < col_num; i++){fprintf(fp_b, "%d", col1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename2, "w")) == NULL){fprintf(fp_b, "%d", row1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename3, "w")) == NULL){printf("Cannot open file write\n");exit(0);}for(i = 0; i < data_num; i++){fprintf(fp_b, "%lf", data1[i]);fprintf(fp_b, ", ");}fclose(fp_b);if((fp_b = fopen(filename4, "w")) == NULL){printf("Cannot open file write\n");exit(0);}for(i = 0; i < b_row_num; i++){fprintf(fp_b, "%.10lf", b[i]);fprintf(fp_b, ", ");}fclose(fp_b);printf("Coo has been transformed to CSC!\n");//释放申请的数组空间free(row);free(col);free(data);free(row1);free(col1);free(data1);free(b);return 0;
}

三、测试

        这里以219x219的稀疏矩阵为测试对象,其中非零数值共699个,输入文件为COO格式。

编译:

运行结果:

其中,

①Y_out_CSC_Ap.txt

②Y_out_CSC_Ai.txt

③Y_out_CSC_Ax.txt

④Y_out_CSC_Ab.txt

        感谢大佬来访,向各位大佬学习!


http://www.mrgr.cn/news/61760.html

相关文章:

  • ubuntu编译ffmpeg
  • VS2022 Windows.SDK for .Net版本不同导致程序崩溃
  • 项目1 yolov5鱼苗检测计数
  • 小红书图文无水印下载
  • WebGL 3D基础
  • 已解决Navicat 选择Mysql表 报错unkonow internal error: Access violation - no RTTI data
  • Python世界:自动化办公Word之批量替换文本生成副本
  • nginx[新手用][模块化][高效]配置
  • 使用命令行上传 ipa 到 App Store(iTMSTransporter 3.3)
  • [JAVAEE] 面试题(二) - CAS 和 原子类
  • 计算机组成原理之高级语言程序与机器级代码之间的对应、高级语言和机器级代码的具体示例
  • 优化云成本,打造卓越体验,他们有话说
  • 微信小程序 - 获取汉字拼音首字母(汉字英文首字母)根据汉字查拼音,实现汉字拼音首字母获取,在小程序上实现汉字的拼音提取首字母!
  • [专有网络VPC]管理VPC配额
  • 智慧园区 | 数智引领,让智慧触手可及
  • String的长度有限,而我对你的思念却无限延伸
  • IDEA 打包首个java项目为jar包
  • 开箱即用!智能文档处理“百宝箱”
  • Faces in Things数据集: 由麻省理工学院、微软等联合发布,探索人类视觉错觉的新里程碑
  • Ollama运行本地LLM大模型简单教程:大显存很重要
  • 【Golang】Golang的数组和slice切片的区别
  • 数据集(Dataset)是指为特定目的而收集、整理、存储的数据集合
  • 雷池社区版配置同步试用
  • 最长公共子串问题
  • 【Linux系统编程】第三十九弹---探索信号处理的奥秘:阻塞信号与sigset_t的深入剖析及实战
  • BUUCTF靶场Misc练习