企业官网建设流程全解析

上的网站app,代写网站,如何 做网站挣钱,成都广告公司联系方式电话前言#xff1a;这两天刚接手一个并行项目#xff0c;对矩阵分块进行计算#xff0c;而采用的矩阵存储格式就是CSR#xff0c;之前刚好对这个格式一直存在迷惑#xff0c;借着机会好好的学习一下。1、CSR介绍 CSR#xff08;Compressed Sparse Row#xff0c;压缩稀疏行…前言这两天刚接手一个并行项目对矩阵分块进行计算而采用的矩阵存储格式就是CSR之前刚好对这个格式一直存在迷惑借着机会好好的学习一下。1、CSR介绍CSRCompressed Sparse Row压缩稀疏行也就是常用在稀疏矩阵存储的一种格式。CSR 的核心思想是只存非零的数据并且把“空着”的地方挤掉。通过使用三个一维数组来达到存储的效果分别是values、col_indices、row_pointer。values数值存储矩阵中的所有非零元素。col_indices列索引用于存储每个非零元素对应的列索引。col_indices[i]表示第i个非零元素所在的列索引。row_pointer行偏移/行指针用于存储每一行在col_indices和values数组中的起始索引位置而row_pointer[i1] - row_pointer[i]表示第i行的非零元素个数。2、示例说明如下图所示是一个6×4的矩阵以及对应的CSR格式1、values按行从上到下行内从左到右读取所有绿色的数字。2、col_indices根据上面的数值分别位于哪一列填写也就是列坐标3、row_pointer是最难理解的部分如果是行坐标那就好理解了可惜不是它不直接存行号它存的是每一行在values中的起始下标。也就是第0行的起始索引是0第一行的起始数据是33前面有两个元素所以第一行就是就是2……计算过程如下数组长度 行数 1 7Row 0: 从下标0开始 (对应数值 4)Row 1: Row 0 有 2 个元素所以 Row 1 从下标 02 2开始 (对应数值 3)Row 2: Row 1 有 1 个元素所以 Row 2 从下标 21 3开始 (对应数值 5)Row 3: Row 2 有 1 个元素所以 Row 3 从下标 31 4开始 (对应数值 7)Row 4: Row 3 有 2 个元素所以 Row 4 从下标 42 6开始 (对应数值 2)Row 5: Row 4 有 1 个元素所以 Row 5 从下标 61 7开始 (对应数值 9)End: Row 5 有 1 个元素最后一位是 71 8(非零元素总数)3、二维稀疏矩阵转CSR格式#includeiostream#includevector#includeiomanip// 用于格式化输出// 定义 CSR 矩阵结构structCSRMatrix{std::vectordoublevalues;// 非零数值std::vectorintcol_indices;// 列索引std::vectorintrow_ptr;// 行偏移量introws;// 行数intcols;// 列数};/** * 将二维向量 (std::vectorstd::vectordouble) 转换为 CSR 格式 */CSRMatrixdense_to_csr(conststd::vectorstd::vectordoubledense_matrix){CSRMatrix csr;// 获取行数和列数if(dense_matrix.empty())returncsr;csr.rowsdense_matrix.size();csr.colsdense_matrix[0].size();// 1. 初始化 row_ptr// 规则row_ptr 的第一个元素永远是 0csr.row_ptr.push_back(0);// 2. 遍历二维矩阵for(inti0;icsr.rows;i){// 遍历当前行的每一列for(intj0;jcsr.cols;j){doublevaldense_matrix[i][j];// 3. 判断非零元素if(val!0.0){csr.values.push_back(val);// 存数值csr.col_indices.push_back(j);// 存列号}}// 4. 当前行遍历结束 row_ptr 的下一个值 当前 values 数组的总长度csr.row_ptr.push_back(csr.values.size());}returncsr;}4、查找特定位置元素说完了他的构造那么如果访问呢对于上述的例子比如我们想访问第 4 行第 3 列从图片看就是数字7在 CSR 格式中不能像普通二维数组那样直接用A[3][2]访问。需要通过row_pointer先找到“第 3 行”的数据范围然后在里面“搜”第 2 列。下面是具体的访问步骤和逻辑查行范围去row_pointer查第 4 行的起始位置和结束位置。起始row_pointer[3]4结束row_pointer[31](即row_pointer[4]) 6意味着第 3 行的数据存储在values数组下标[4, 6)的区间内。搜列索引遍历col_indices的下标 4 到 5寻找列号为2的元素。检查下标4col_indices[4]是2。匹配成功取值既然下标 4 对应的列号是对的那么取values[4]。values[4]7。#includeiostream#includevector// 查找矩阵中特定的元素 A[row, col]doubleget_element(inttarget_row,inttarget_col,conststd::vectorintrow_ptr,conststd::vectorintcol_indices,conststd::vectordoublevalues){// 1. 查找行范围intstart_idxrow_ptr[target_row];// 起点intend_idxrow_ptr[target_row1];// 终点 (不包含)// 2. 在该范围内遍历查找是否有列索引等于target_colfor(intidxstart_idx;idxend_idx;idx){if(col_indices[idx]target_col){returnvalues[idx];}}// 3. 如果循环结束还没找到说明该位置是 0return0.0;}// 定义一个结构体用来存 (行, 列, 值) 三元组structTriplet{introw;intcol;doublevalue;};/** * 遍历 CSR 矩阵的所有非零元素 * 对应 Python: get_all_non_zero_elements */std::vectorTripletget_all_non_zero_elements(conststd::vectorintrow_ptr,conststd::vectorintcol_indices,conststd::vectordoublevalues){std::vectorTripletresults;// 非零元素的总数就是 values 的大小results.reserve(values.size());// 1. 获取行数 (row_ptr 的长度减 1)intnum_rowsrow_ptr.size()-1;// 2. 外层循环遍历每一行for(inti0;inum_rows;i){// 获取当前行的起止位置intstart_idxrow_ptr[i];intend_idxrow_ptr[i1];// 3. 内层循环遍历这一行的所有非零元素for(intidxstart_idx;idxend_idx;idx){// 构造三元组并存入结果// row i (当前行号)// col col_indices[idx] (当前列号)// val values[idx] (当前数值)results.push_back({i,col_indices[idx],values[idx]});}}returnresults;}5、CSR总结特性描述 / 评价备注 (Why?)存储方式按行压缩存储非零元素也就是 Row-Major (行优先)空间复杂度2×NNZ(N1)2 \times NNZ (N 1)2×NNZ(N1)即values、column_indices、row_pointer三个数组NNZNNZNNZ个数值 NNZNNZNNZ个列号 (行数1)(行数1)(行数1)个行偏移。非常省内存。优势行切片 (Row Slicing) 极快想取第iii行直接row_ptr[i]到row_ptr[i1]就拿到了。优势矩阵-向量乘法 (SpMV) 极快CPU 缓存命中率高因为values数组是连续访问的。缺点 (致命)结构修改 (Insertion/Deletion) 极慢千万别往 CSR 里插入新元素这意味着需要把后面几十万个数据全部往后挪一位。缺点列切片 (Column Slicing) 极慢想取第jjj列必须遍历所有行去“搜”有没有第jjj列的元素。缺点随机访问 (Random Access) 不是O(1)O(1)O(1)查A[i][j]的时间复杂度是O(该行非零元个数)O(\text{该行非零元个数})O(该行非零元个数)因为要二分查找或线性扫描。并行性适合 OpenMP/多线程每一行是独立的很容易并行 (#pragma omp parallel for)。负载均衡可能较差 (Load Imbalance)如果第1行有100个元素第2行只有1个多线程分配时会导致有的核累死有的核闲死。适用场景矩阵乘法、有限元分析、迭代求解器写好了就不动的数据结构。不适用场景矩阵组装 (Assembly)正在生成矩阵时别用 CSR要用 COO 或 List of Lists生成完了一次性转 CSR。CSR 的“三不”原则不要动态修改如果需要频繁A[i][j] x且(i,j)原本是 0绝对不要用 CSR。请先用 COO 格式存最后make_compressed()转成 CSR。不要按列遍历如果算法里有for col in columns的逻辑CSR 会慢到让你怀疑人生。请转置矩阵或者改用CSC (压缩稀疏列)格式。不要直接用于复杂的矩阵-矩阵乘 (SpGEMM)虽然可以做但如果结果矩阵的稀疏结构不可预测通常需要先计算符号模式Symbolic Phase比稠密矩阵乘法麻烦得多。