Python部落(python.freelycode.com)组织翻译，禁止转载，欢迎转发。 Python是一门整合了很多强大的基础数据类型的高级编程语言。分析Python程序的运行时间需要很好的理解不同Python数据类型的时间成本。 比如说，在Python中，你可以这么写： L = L1 L2 L,L1,L2是列表。这个语句把L1和L2连接起来并赋值给L。该语句的运行时间取决于L1和L2的长度。（运行时间多多少少跟两个列表长度之和成正比。） 我们本节的目的是回顾各种Python数据类型的操作，确定或估计他们的运行时间。估计方法是对比相关的Python代码和一些试验（分析真实的运行时间，对结果进行插值拟出一条比较好的曲线）。 Python运行时间试验和讨论 我们计算不同大小输入的运行时间，然后用最小二乘法拟合找到运行时间的高阶项系数。（哪一项高阶项由实验决定，也可以自动化决定） 最小二乘法拟合是用来最小化残差的平方和的，用scipy.optimize.leastsq。 （这个程序以前的版本不只找出高阶项系数，还找出低阶项系数。但是插值程序难以区别n和n lg(n)。而且，我们更关心的是相对误差而不是绝对误差。最后，只看高阶项、只研究相对误差是最简单的。） 使用的机器是IBM Thinkpad T43p，1.86GHz的Pentium M处理器，1.5GB的内存。 计时代码见[timing.py](http://theory.csail.mit.edu/classes/6.006/fall07/timing/timing.py)。其样本输出见[timing.out.txt](http://theory.csail.mit.edu/classes/6.006/fall07/timing/timing.out.txt)。（由于随机的运行时间，这个输出可能和下面的表格有些不同。。。） Python整数操作代价 Python整数型操作的代价 x,y和z是n位数字 w是2n位数字 s是n位字符串 乘法跟除法时间不同可以是因为乘法用了Karatsuba算法，时间复杂度为O(nlg3)。而除法用了O(n2)算法。 Python字符串操作的代价 Python字符串操作的代价 s和t是长度为n的字符串 u长度为(n/2) Python列表操作的代价
Python列表操作的代价 L和M是长度为n的列表 p的长度为n/2 第一次向列表中添加元素时，会有额外的时间消耗，因为列表会被复制；同时有额外大约列表大小的1/8的空间会被添加到列表末尾。每次这额外添加的空间被用完了，列表就会重新分配到大约1.125倍长度的新数组中去。 Python字典操作的代价 Python字典操作的代价 D是n个元素的字典 复制和列出字典所有的值的高阶项应该是什么呢？好像应该是线性的，但是这两个操作的数据显示好像有些超线性。我们这里取n lg(n)作为线性回归变量，但是不需要做进一步的探究。 英文原文：http://scripts.mit.edu/~6.006/fall08/wiki/index.php?title=Python_Cost_Model |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
