本文主要介绍选择合适的数据结构。实验环境是CentOS7 + GCC。
1. 优化方法简述
在解决具体问题时选择合适的数据结构是非常重要的，以稀疏矩阵向量乘法为例进一步说明数据结构选择的重要性。稀疏矩阵向量乘是科学工程计算的核心算法，为了提升稀疏矩阵向量乘法的性能，将采用坐标存储、行压缩存储、对角存储以及埃尔帕克（ELLPACK）存储四种稀疏矩阵存储格式实现稀疏矩阵向量乘法并进行测试对比。
当矩阵A 是一个 m×n 的矩阵，x 是一个n×1 的列向量，y 是一个m×1 的列向量时，稀疏矩阵向量乘法的数学公式可以表示为：
这个公式说明y_i是矩阵 A 第i 行的元素与向量x 对应位置元素的乘积之和。
2. 示例分析
2.1 示例一
首先我们看一下坐标存储。坐标存储格式也称为三元组存储格式，其分别存储每个非零元素的行索引row、列索引col以及数值data。这种存储方式的主要优点是灵活、简单、易于按行和按列访问稀疏矩阵。
下面给出了坐标存储稀疏矩阵乘的代码。
运行命令：
（1）gcc MatriVecMulti1.cpp -o MatriVecMulti1
（2）./MatriVecMulti1
2.2 示例二
示例二简单介绍行压缩存储。主要思想是逐行对稀疏矩阵进行压缩，并且记录每行首个非零元素的位置信息。行压缩存储格式由三个数组构成，数值data按行存放非零元素，列号col记录对应于data中每个非零元素位于的列数，指针ptr记录每行第一个非零元素在data中的存储位置。
下面给出了行压缩存储稀疏矩阵乘的代码。
运行命令：
（1）gcc MatriVecMulti2.cpp -o MatriVecMulti2
（2）./MatriVecMulti2
2.3 示例三
示例三简单介绍对角存储。对角存储格式专为由多条非零对角线组成的稀疏矩阵设计，对角存储格式采用一个二维矩阵和一个向量来存储原矩阵，其中二维矩阵中的每一列用来存储原矩阵中的一条对角线，而向量则用来存储各列对应原矩阵中主对角线的偏移量。
下面给出了对角存储稀疏矩阵乘的代码。
运行命令：
（1）gcc MatriVecMulti3.cpp -o MatriVecMulti3
（2）./MatriVecMulti3
2.4 示例四
示例四简单介绍ELLPACK存储。对于一个m*n的矩阵，每行最多有k个非零值元素，ELLPACK格式将非零值存储于一个m*k的稠密矩阵Data中。相应的列指针被存储在指数矩阵Indices中，然后用0或者其它的哨兵值来填补空缺。与对角存储格式一样，indices和data矩阵都是按列顺序来存储的，当稀疏矩阵存储格式为ELLPACK时，向量乘法实现如下。
下面给出了ELLPACK存储稀疏矩阵乘的代码。
运行命令：
（1）gcc MatriVecMulti4.cpp -o MatriVecMulti4
（2）./MatriVecMulti4
通过上述代码可发现，当采用对角存储格式时，其性能往往好于其它格式。缺点是采用对角格式，非零元素的坐标需要通过计算才能得到，因此通常在稀疏矩阵向量乘法计算中不会采用对角格式。只有非零元所占比例大于某一阈值时，使用ELLPACK存储格式会取得更好的性能。对角存储和ELLPACK这两种格式都需要对矩阵进行补零操作，对稀疏矩阵向量乘程序性能有一定影响，而坐标存储和行压缩存储格式则不存在这个问题，它们只存储矩阵中的非零元素，不会引入不必要的开销。
每种稀疏矩阵存储结构的不同将导致在进行优化时必须选择不同的方法，因此需针对每一种方法选择不同的优化策略，以获得最优的性能。
3. 总结
选择合适的数据结构是软件开发中至关重要的决策之一。不同的数据结构适用于不同的应用场景，根据应用程序的需求来选择合适的数据结构可以提高程序的性能和可维护性。
4. 参考资料
（1）十三张图带你彻底了解所有数据结构 - 知乎 (zhihu.com)
（2）数据结构之道：如何选择适合你的数据存储_数据结构用合适的方法存储网络-CSDN博客
