摘要：而内存的物理地址中，二维数组是以行优先的顺序存储，测试图像数据大小为字节，假设内存页为字节，那么按行优先遍历，遍历完一行则中断一次缺页，整个过程只需要中断次缺页异常，进行页替换。综上所述行优先遍历的方式比列优先效率快。
数组是数据结构的基础，之所以这么说是因为数组反映了内存的物理结构。在内存中，数组是连续分布的。而在程序中，往往要在内存中分配一块连续的空间来使用。例如，在图像处理邻域，耳熟能详的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的命中率比按行优先遍历的低。
综上所述：行优先遍历的方式比列优先效率快。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/118850.html
摘要：方法使用另一个构造函数它需要你提供每一行的字节数而不要求对齐，为什么网上的转换方法不使用这个也许大家使用的图片大小都是符号规范的。 cv::Mat转换为QImag...
摘要：数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从算起的。列表中没有索引，这是数组与列表最大的不同点。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含。 ...
摘要：可以针对笔者常用的数独本文的实现都基于该，实现数独的识别求解并把答案自动填入。专家级别的平均秒完成求解包括图像数字提取，识别过程，完成全部操作。步骤四数独求解，生成答案，并生成需要填充的数字序列。 1 序 数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3...
摘要：可以针对笔者常用的数独本文的实现都基于该，实现数独的识别求解并把答案自动填入。专家级别的平均秒完成求解包括图像数字提取，识别过程，完成全部操作。步骤四数独求解，生成答案，并生成需要填充的数字序列。 1 序 数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3...
摘要：本文主要是介绍了和开发环境的搭建，以及基于示例程序的演示。使用的方式是将作为库，然后调用。比较时使用的都是基本图像处理操作，例如灰度化，高斯模糊，边缘检测等等。 Android NDK 和 OpenCV 整合开发总结(3) 这一节的主要内容是OpenCV在Android NDK开发中的应用，包括下面几个方面的内容： 如何实现Static Initialization从而不需要安装...
阅读 2528·2021-10-13 09:40
阅读 1996·2021-09-30 09:46
阅读 1941·2021-09-22 15:27
阅读 2943·2021-09-03 10:32
阅读 2004·2021-09-02 15:34
阅读 3369·2021-09-01 11:38
阅读 2289·2019-08-30 15:56
阅读 2093·2019-08-30 13:01
