一、数组在内存的存储方式

数组是数据结构的基础，之所以这么说是因为数组反映了内存的物理结构。在内存中，数组是连续分布的。而在程序中，往往要在内存中分配一块连续的空间来使用。例如，在图像处理邻域，耳熟能详的opencv中有一数据类型Mat，我们一般都会以Mat来存储图像数据。Mat是一个二维数组，可以通过两个for循环遍历图像上各个像素值。有人习惯按行优先遍历，有人喜欢按列优先遍历，表面上看，这两中写法的时间复杂度都是O(nm)（n表示图像的高，m表示图像的宽),可实际上是否都是O(nm)呢？

二、代码示例及结果

列优先遍历代码如下（示例）：

	Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
	if (!src.empty())
		imshow("src", src);
	int nums = 10;
	while (nums)
	{
		double t = (double)getTickCount();
		for (int i = 0; i < src.cols; i++)
		{
			for (int j = 0; j < src.rows; j++)
			{
				uchar srcValue = src.at<uchar>(j, i);
			}
		}
		t = ((double)getTickCount() - t) / getTickFrequency(); //获得时间，单位是秒
		cout << "time:" << t<<"ms"<<endl;
		nums--;
	}

通过一个循环，重复测试了10次，列优先遍历的时间耗时通过控制台打印如下：
在这里插入图片描述
行优先遍历代码如下（示例）：

	Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
	if (!src.empty())
		imshow("src", src);
	int nums = 10;
	while (nums)
	{
		double t = (double)getTickCount();
		for (int i = 0; i < src.rows; i++)
		{
			for (int j = 0; j < src.cols; j++)
			{
				uchar srcValue = src.at<uchar>(i, j);
			}
		}
		t = ((double)getTickCount() - t) / getTickFrequency(); //获得时间，单位是秒
		cout << "time:" << t<<"ms"<<endl;
		nums--;
	}

同样，行优先遍历也通过一个循环，重复测试了10次，时间耗时通过控制台打印如下：
在这里插入图片描述
通过以上测试可以发现，行优先遍历的方式比列优先效率快。

三.分析

1. CPU高速缓存（英语：CPU Cache）：在计算机系统中，CPU高速缓存是用于减少处理器访问内存所需平均时间的部件。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。（百度百科解释）。
2.虚拟内存：虚拟内存被操作系统用以管理内存，对物理内存进行扩展，其作用是替代物理内存的部分工作来运行程序，让操作系统就可以运行更多的程序，同时执行更多的任务。
3.二维数组在内存中的存储结构如下图：数据在内存中是以行优先的方式存储。

在这里插入图片描述
4.代码测试的图像大小为4096X1200,位深度为8，如下图。之所以行优先遍历的方式比列优先效率快，是因为cpu在访问内存地址的时候，首先访问的是虚拟内存，检查TLB，映射成对应的物理地址进行数据访问。如果命中，会得到其物理地址，之后会访问cache，如果cache中有要访问的数据，那么本次访问就结束，如果没有，就到内存中寻找，并更新cache；如果TLB不命中，那么那么系统内核会调用缺页异常处理程序去处理，这个过程中会进行页替换等操作，最终取得要访问的数据。而内存的物理地址中，二维数组是以行优先的顺序存储，测试图像数据大小为4096X1200字节，假设内存页为4096字节，那么按行优先遍历，遍历完一行则中断一次缺页，整个过程只需要中断1200次缺页异常，进行页替换。而按列优先遍历，每遍历一个元素便中断一次缺页异常，整个过程4096X1200次中断，可想而知，按列优先遍历产生中断耗时比按行优先遍历大了许多。而实际中物理内存一般比较充足，系统分配的页内存远远不止4096字节，所以缺页中断的次数不会这么多。同理，如果检查TLB命中，得到其物理地址之后会访问cache，如果cache没有要访问的数据，就到内存中寻找，并更新cache；由于二维数组在内存中的存储方式，按列优先遍历访问cache的命中率比按行优先遍历的低。
在这里插入图片描述