性能优化——遍历图像的正确姿势
微信公众号：命运探知之魔眼
如有问题或建议，请后台留言，我会尽力解决你的问题。
前言
我是人工智障，一名程序猿。做过嵌入式、爬虫，目前在自学计算机视觉 。注册 「命运探知之魔眼」（名字取自影视作品「命运石之门」）这个公号已有些日子，真正有心将它运营起来是看到朋友狗哥运营它的公号
「一个优秀的废人」
之后。本「性能优化」系列是作为「计算机视觉」系列文章的拓展，主要分享一些代码优化和底层的知识。
任务描述
首先来看一项简单的任务：遍历一个矩阵，获取里面的值，但不需要做任何操作，只是读取。
矩阵是一个二维数组，或者在 Python 中是一个 numpy.array ，遍历这样的一个结构需要两层循环，沿着行方向和列方向的，但是循环的顺序有两种，乍一看似乎哪个在先哪个在后都没有关系，然而我会证明这两种顺序有很大的性能差异。
代码实现
我们分别给行优先访问和列优先访问定义两个函数。
行优先的意思是外层循环是沿行方向的，列优先则反之。
要对比两者的性能，我们定义了一个存放矩阵大小的 list ，让大小递增的矩阵分别用这两种方式访问，比较它们的运行时间。
下面是我使用的矩阵大小 list:
从 500 开始，以 1000 的步进值往 8000 递增。
然后来生成随机方阵，分别运行两种遍历方式：
row_major_time 和 col_major_time 存放了两种遍历方式对应不同矩阵大小的运行时间，把矩阵大小作为横轴，运行时间作为纵轴，我们画一个折线图，使用了 matplotlib 库，有兴趣可以自行查阅使用方法，不作过多介绍，画图的代码也贴在这里：
运行结果
Figure_1.png
可以看到随着矩阵大小增大，行优先跟列优先的运行时间产生了差异，行优先访问要比列优先快。
原因分析
要明白造成差异的原因，我们要了解 4 件事情。
一、内存的排列
内存对于操作系统是线性排列的，内存地址沿着一个方向增加，像数轴一样，如下图：
内存排列
二、图像在内存中的排列
图像是个二维数组，但内存的排列是一维的，因此图像在内存中实际是被展平成一维排列的，至于是沿着列方向还是行方向展，一般的实现都是沿着行方向展的，换句话说，申请图像的内存的时候是一行一行的申请的，numpy 和 C 语言中的 malloc 都是这样的。画图表示就是这样子的：
图像在内存中的排列
因此如果用行优先的方法访问的话，我们对于图像内存的访问是连续的，因为访问的方式跟内存申请的方式是一致的，好好比划一下。
三、高速缓存牛逼
高速缓存就是买电脑的时候看到 CPU 有个参数是 Cache 多少级多少 MB。高速缓存的作用跟内存类似，但是离 CPU 核非常的近，访问速度是内存的 5 ~ 10倍，造价也很高，程序在读取数据的时候总是先从 Cache 中查找有没有这项数据，才到主存中获取。因此，如果能让图像常驻或者部分常驻 Cache 的话，速度的提升是非常明显的。
四、高速缓存抓取数据的策略
Cache 的数据是从主存中拷贝过来的，Cache 对于我们存放的数据有个假设，就是认为短时间内对我们有用的数据，在内存上都是连续分布的。所以 Cache 并不是一个一个数据的从主存拷贝过来的，而是一片一片的拷。因此如果对你有用的数据真的是连续排布的，这样的策略就会大有裨益。正好，我们的图像就是这样的。
总结
现在看回运行结果的折线图，一开始两种访问方式的运行时间相差无几，是因为这时候的 Cache 还能容下整幅图，因此怎么访问速度都不会有太大的差异，到了后面图像越来越大，Cache 是不可能整个装下来的，差异就体现在哪种访问方式会提高缓存命中率了。
后语
我不是大神，不是什么牛人，于 性能优化 的领域我真的是新手，很多知识现学现卖，因此对于我的文章有什么纰漏或者疑问的，欢迎下方留言。
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20180725G14DZV00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
