探究数组排序提升Python程序的循环的运行效率的原因
作者:foreign keys 发布时间:2021-07-16 21:35:06
早上我偶然看见一篇介绍两个Python脚本的博文,其中一个效率更高。这篇博文已经被删除,所以我没办法给出文章链接,但脚本基本可以归结如下:
fast.py
import time
a = [i for i in range(1000000)]
sum = 0
t1 = time.time()
for i in a:
sum = sum + i
t2 = time.time()
print t2-t1
slow.py
import time
from random import shuffle
a = [i for i in range(1000000)]
shuffle(a)
sum = 0
t1 = time.time()
for i in a:
sum = sum + i
t2 = time.time()
print t2-t1
如你所见,两个脚本有完全相同的行为。都产生一个包含前一百万个整数的列表,并打印对这些整数求和的时间。唯一的不同是 slow.py 先将整数随机排序。尽管这看起来有些奇怪,似乎随机化足够将程序明显变慢。在我机器上,运行的Python2.7.3, fast.py 始终比 slow.py 快十分之一秒(fast.py 执行大约耗时四分之三秒,这是不平常的增速)。你不妨也试试看。(我没有在Python3上测试,但结果应该不会差太多。)
那为什么列表元素随机化会导致这么明显的减速呢?博文的原作者把这记作“分支预测(branch prediction)”。如果你对这个术语不熟悉,可以在 StackOverflow 的提问中看看,这里很好地解释了这个概念。(我的疑虑是原文的原作者遇到了这个问题或者与此类似的问题,并把这个想法应用到不太适合应用的Python片段中。)
当然,我怀疑分支预测(branch prediction)是否是真正导致问题的原因。在这份Python代码中没有顶层条件分支,而且合乎情理的是两个脚本在循环体内有严格一致的分支。程序中没有哪一部分是以这些整数为条件的,并且每个列表的元素都是不依赖于数据本身的。当然,我还是不确定python是否算得上足够“底层”,以至于CPU级别的分支预测能够成为python脚本性能分析中的一个因素。Python毕竟是一门高级语言。
因此,如果不是分支预测的原因,那为什么 slow.py 会这么慢?通过一点研究,经过一些“失败的开端”之后,我觉得自己找到了问题。这个答案需要对Python内部虚拟机有点熟悉。
失败的开端:列表vs.生成器(lists and generators)
我的第一想法是Python对排序的列表[i for i in range(1000000)] 的处理效率要比随机列表高。换句话说,这个列表可以用下面的生成器替代:
def numbers():
i = 0
while i < 1000000:
yield i
i += 1
我想这可能在时间效率上更高效些。毕竟,如果Python在内部使用生成器替代真正的列表可以避免在内存中一次保存所有整数的麻烦,这可以节省很多开销。slow.py 中的随机列表不能轻易的被一个简单生成器捕获,所有VM(虚拟机)无法进行这样的优化。
然而,这不是一个有用的发现。如果在slow.py的 shuffle() 和循环之间插入 a.sort(),程序会像 fast.py一样快。很明显,数字排序后的一些细节让程序更快。
失败的开端:列表对比数组
我的第二个想法是有可能数据结构造成的缓存问题。a 是一个列表,这自然让我相信a实际上是通过链表来实现的。如果shuffle操作故意随机化这个链表的节点,那么 fast.py 可能可以把列表的所有链表元素分配在相邻地址,从而采用高级局部缓存,而slow.py会出现很多缓存未命中的情况,因为每个节点引用不在同一个缓存行上的另外一个节点。
不幸的是,这也不对。Python的列表对象不是链接的列表,而是真正意义上的数组。尤其是用C结构体定义了Python列表对象:
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
……换句话说,ob_item 是一个指向PyObjects指针数组的指针,并且分配的大小是我们分配给数组的大小。因此,这对于解决这个问题也没帮助(尽管这对我不确定Python中关于列表操作的算法复杂度有些安慰:列表的添加操作算法复杂度是O(1),访问任意列表元素的算法复杂度是O(1),等等)。我只是想说明为什么Guido选择称它们为列表“lists”而不是数组“arrays”,而实际上它们却是数组。
解决办法:整体对象
数组元素在内存中是相邻的,因此这样的数据结构不会带来缓存问题。事实证明缓存位置是 slow.py 变慢的原因,但这来自于一个意料之外的地方。在Python中,整数是分配在堆中的对象而不是一个简单的值。尤其是在虚拟机中,整数对象看起来像下面这样:
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;
上面结构体中唯一“有趣”的元素是ob_ival(类似于C语言中的整数)。如果你觉得使用一个完整的堆对象来实现整数很浪费,你也许是对的。很多语言就为了避免这样而做优化。例如 Matz的 Ruby 解释器通常以指针的方式存储对象,但是对频繁使用的指针做例外处理。简单来说,Ruby解释器把定长数作为对象应用塞到同样的空间,并用最低有效位来标记这是一个整数而不是一个指针(在所有现代系统中,malloc总是返回以2的倍数对齐的内存地址)。在那时,你只需要通过合适的位移来获取整数的值——不需要堆位置或者重定向。如果CPython做类似的优化,slow.py 和 fast.py 会有同样的速度(而且他们可能都会更快)。
那么CPython是怎样处理整数的呢?解释器的什么行为给我们如此多的疑惑?Python解释器每次将整数分配到40Byte的“块”中(block)。当Python需要生成新的整型对象时,就在当前的整数“块”中开辟下一个可用空间,并将整数存储在其中。我们的代码在数组中分配一百万个整数,大部分相邻的整数会被放到相邻的内存中。因此,在有序的一百万个数中遍历展现出不错的缓存定位,而在随机排序的前一百万个数中定位出现频繁的缓存未命中。
因此,“为什么对数组排序使得代码更快”的答案就是它根本没有这个作用。没有打乱顺序的数组遍历的速度更快,因为我们访问整型对象的顺序和分配的顺序一致(他们必须被分配)。
猜你喜欢
- 代理模式Proxy模式是一种常用的设计模式,它主要用来通过一个对象(比如B)给一个对象(比如A) 提供'代理'的方式方式访问
- 百度有啊2009年情人节logo——大纸袋GG给大纸袋MM送了枝玫瑰花,大纸袋MM奖励了大纸袋GG一个吻,好可爱!淘宝网2009年情人节lo
- 写爬虫是一个发送请求,提取数据,清洗数据,存储数据的过程。在这个过程中,不同的数据源返回的数据格式各不相同,有 JSON 格式,有 XML
- 一、题目描述A:先输出提示语句,并接受用户输入的年、月。B:根据用户输入的年,先判断是否是闰年。C:根据用户输入的月来判断月的天数。D:用循
- 00 小编的问题小编向我们反馈,从微信里复制出来的图片,会被微信屏蔽,无法显示我们后天采用的是百度编辑器,而且已经做了远程图片本地化,于是检
- 之前我写过一篇文章介绍如何实现中国站长站的文章干扰码功能:《谈中国站长站的文章干扰码实现方法》 首发在asp之家。如果大家有兴趣可以先看看。
- 今天将webserice里面的一个代码,拷到一个C#类,结果运行编译错误。DataBase = Server.MapPath("d
- yolov5返回坐标(v6版)1 、从yolov5文件夹李找到detect.py,按Ctrl+F 输入annotator.box_label
- 密钥密码'''如密钥短语密码为: university -> universty明文: abcdefghijk
- pop()方法从列表移除并返回最后一个对象或obj。语法以下是pop()方法的语法:list.pop(obj=list[-1])
- python 中提供一种用于对函数固定属性的函数(与数学上的偏函数不一样)# 通常会返回10进制int('12345') &
- 脚本调试第一步:设置中断(鼠标左键点击)第二步:输入中断条件(可选功能,鼠标右键点击红点)第三步:触发中断(当符合条件是,中断被触发)出现中
- python pycharm中使用opencv时,没有代码自动补全提示解决方案有2种今天工作时突然发现,在写OPENCV相关代码时,没有自动
- 小编语:小编我最早使用的网页制作工作就是FrontPage啦,FrongPage方便简单,会用Word就能做网页。如果你对网页制作要求不高,
- 为了防止某些别有用心的人从外部访问数据库,盗取数据库中的用户姓名、密码、信用卡号等其他重要信息,在我们创建数据库驱动的解决方案时,我们首先需
- 装饰器对与Python新手以至于熟悉Python的人都是一个难理解, 难写的东西. 那么今天就分享一下我对Python 装饰器的理解所谓装饰
- ASP 组件 FILE对象当前,基于浏览器/服务器模式的应用比较流行。当用户需要将文件传输到服务器上时,常用方法之一是运行FTP服务器并将每
- 我在程序中加入了分数显示,三种特殊食物,将贪吃蛇的游戏逻辑写到了SnakeGame的类中,而不是在Snake类中。特殊食物:1.绿色:普通,
- turtle的文档:https://docs.python.org/3/library/turtle.html用Python的turtle库
- Selenium 是一个可以让浏览器自动化地执行一系列任务的工具,常用于自动化测试。不过,也可以用来给网页截图。目前,它支持 Java、C#