2.4Python数据类型的性能

Python数据类型的性能

前面我们了解了“大O表示法”以及对不同的算法的评估，下面来讨论下Python两种内置数据类型上各种操作的大O数量级
列表list和字典dict
这是两种重要的Python数据类型，后面的课程会用来实现各种数据结构，通过运行试验来估计其各种操作运行时间数量级

• 对比list和dict的操作

List列表数据类型

list类型各种操作（interface）的实现方法有很多，如何选择具体哪种实现方法？ 总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作80/20准则：80%的功能其使用率只有20%

最常用的是：按索引取值和赋值（v =a[i], a[i]= v）
由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)
另一个是列表增长，可以选择append()和_ add _()“+”
lst.append(v)，执行时间是O(1)
lst= lst+ [v]，执行时间是O(n+k)，其中k是被加的列表长度
选择哪个方法来操作列表，决定了程序的性能

• 4种生成前n个整数列表的方法

首先是循环连接列表（+）方式生成
然后是用append方法添加元素生成
接着用列表推导式来做
最后是range函数调用转成列表

• 使用timeit模块对函数计时

创建一个Timer对象，指定需要反复运行的语句和只需要运行一次的“安装语句” 然后调用这个对象的timeit方法，其中可以指定反复运行多少次

我们看到，4种方法运行时间差别很大，列表连接（concat）最慢，List range最快，速度相差近200倍。append也要比concat快得多，另外，我们注意到列表推导式速度是append两倍的样子

• List基本操作的大O数量级

  
  

• list.pop的计时试验

1.我们注意到pop这个操作，pop()从列表末尾移除元素，O(1)，pop(i)从列表中部移除元素，O(n)，原因在于Python所选择的实现方法，从中部移除元素的话，要把移除元素后面的元素，全部向前挪位复制一遍，这个看起来有点笨拙，但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1)，这也算是一种对常用和不常用操作的折衷方案
2.为了验证表中的大O数量级，我们把两种情况下的pop操作来实际计时对比
相对同一个大小的list，分别调用pop()和pop(0)，对不同大小的list做计时，期望的结果是pop()的时间不随list大小变化，pop(0)的时间随着list变大而变长

首先我们看对比，对于长度2百万的列表，执行1000次，pop()时间是0.0007秒，pop(0)时间是0.8秒，相差1000倍
3.我们通过改变列表的大小来测试两个操作的增长趋势

将试验数据画成图表，可以看出增长趋势：pop()是平坦的常数，pop(0)是线性增长的趋势

dict数据类型

字典与列表不同，根据关键码（key）找到数据项，而列表是根据位置（index），最常用的取值get和赋值set，其性能为O(1)，另一个重要操作contains(in)是判断字典中是否存在某个关键码（key），这个性能也是O(1)

list和dict的in操作对比

设计一个性能试验来验证list中检索一个值，以及dict中检索一个值的计时对比
生成包含连续值的list和包含连续关键码key的dict，用随机数来检验操作符in的耗时。

可见字典的执行时间与规模无关，是常数，而列表的执行时间则随着列表的规模加大而线性上升