Python 列表和字典数据结构的性能分析

list列表数据类型

list类型各种操作（interface）的实现方法有很多，如何选择具体哪种实现方法？ 总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作。
有一个准则：

80/20准则：80%的功能其使用率只有20%
在实现列表数据结构时，Python的设计师有许多选择，每一个选择都会影响操作的性能。为了做出正确的选择，他们考虑了列表最常见的用法，并据此优化列表的实现，以使最常用的操作非常快。

当然，他们也尽力使不常用的操作也很快，但在需要权衡时，往往会牺牲低频操作的性能。

最常用的是：按索引取值和赋值（v =a[i], a[i]= v）,由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)

另一个是列表增长，可以选择append()和__add__()“+”
lst.append(v)，执行时间是O(1),
lst= lst+ [v]，执行时间是O(n+k)，其中k是被加的列表长度，
选择哪个方法来操作列表，决定了程序的性能。

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

import time

# 1 循环连接
def test1(num):
    l = []
    for i in range(num):
        l = l + [i]

# 2 append()方法
def test2(num):
    l = []
    for i in range(num):
        l.append(i)

# 3 列表推导式
def test3(num):
    l = [i for i in range(num)]

# 4 list(range())
def test4(num):
    l = list(range(num))

num = 100000
t1 = time.time()
test1(num)
t2 = time.time()
print('concat %f seconds\n' % (t2-t1))

test2(num)
t3 = time.time()
print("append %f seconds\n" % (t3-t2))

test3(num)
t4 = time.time()
print("comprehension %f seconds\n" % (t4-t3))

test4(num)
t5 = time.time()
print("list range %f seconds\n" %  (t5-t4))

运行结果：

concat 19.451530 seconds

append 0.007978 seconds

comprehension 0.003990 seconds

list range 0.002991 seconds

我们看到，4种方法运行时间差别很大，列表连接（concat）最慢，List range最快。

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

我们注意到pop这个操作，
pop()从列表末尾移除元素，O(1)
pop(i)从列表中部移除元素，O(n)
原因在于Python所选择的实现方法，从中部移除元素的话，要把移除元素后面的元素，全部向前挪位复制一遍，这个看起来有点笨拙，但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1)，这也算是一种对常用和不常用操作的折中方案。

为了验证表中的大O数量级，我们把两种情况下的pop操作来实际计时对比
相对同一个大小的list，分别调用pop()和pop(0)，对不同大小的list做计时，期望的结果是pop()的时间不随list大小变化，pop(0)的时间随着list变大而变长。


虽然测试结果说明pop(0)确实比pop()慢,但是并没有证明pop(0)的时间复杂度是O(n),也没有证明pop()的是O(1)。要证明这一点，需要看看两个操作在各个列表长度下的性能。以下代码实现了这个测试。

图2-3展示了实验结果。可以看出，列表越长，pop(0)的耗时也随之变长，而 pop()的耗时很稳定。这刚好符合O(n)和O(1)的特征。

实验会有一些误差。因为用来测量的计算机运行着其他进程，所以可能拖慢代码的速度。因此，尽管我们尽力减少计算机所做的其他工作,测出的时间仍然会有些许变化。这也是测试1000遍的原因，从统计角度来说，收集足够多的信息有助于得到可靠的结果。

dict字典数据类型

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

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

结果：

下图展示了实验结果：

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