Python字典和列表性能之间的比较_Python

python列表和字典

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

对比 list 和 dict 操作如下：

Python字典和列表性能之间的比较

list列表数据类型常用操作性能：

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

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

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

Python字典和列表性能之间的比较

创建一个 timer 对象，指定需要反复运行的语句和只需要运行一次的"安装语句"。

然后调用这个对象的 timeit 方法，指定反复运行多少次。

				?

									# timer(stmt="pass", setup="pass")   # 这边只介绍两个参数

									# stmt：statement的缩写，就是要测试的语句，要执行的对象

									# setup：导入被执行的对象（就和run代码前，需要导入包一个道理） 在主程序命名空间中  导入

									time1 = timer("test1()", "from __main__ import test1") 

									print("concat：{} seconds".format(time1.timeit(1000)))

									time2 = timer("test2()", "from __main__ import test2")

									print("append：{} seconds".format(time2.timeit(1000)))

									time3 = timer("test3()", "from __main__ import test3")

									print("comprehension：{} seconds".format(time3.timeit(1000)))

									time4 = timer("test4()", "from __main__ import test4")

									print("list range：{} seconds".format(time4.timeit(1000))

结果如下：

Python字典和列表性能之间的比较

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

总结列表基本操作的大 o 数量级：

Python字典和列表性能之间的比较

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

list.pop()的计时试验，通过改变列表的大小来测试两个操作的增长趋势：

				?

									import timeit

									pop_first = timeit.timer("x.pop(0)", "from __main__ import x")

									pop_end = timeit.timer("x.pop()", "from __main__ import x")

									print("pop(0)          pop()")

									y_1 = []

									y_2 = []

									for i in range(1000000, 10000001, 1000000):

									    x = list(range(i))

									    p_e = pop_end.timeit(number=1000)

									    x = list(range(i))

									    p_f = pop_first.timeit(number=1000)

									    print("{:.6f}        {:.6f}".format(p_f, p_e))

									    y_1.append(p_f)

									    y_2.append(p_e)

结果如下：

Python字典和列表性能之间的比较

将试验结果可视化，可以看出增长趋势：pop()是平坦的常数，pop(0)是线性增长的趋势。

Python字典和列表性能之间的比较

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

Python字典和列表性能之间的比较

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

				?

									import timeit

									import random

									y_1 = []

									y_2 = []

									print("lst_time         dict_time")

									for i in range(10000, 1000001, 25000):

									    t = timeit.timer("random.randrange(%d) in x" % i, "from __main__ import random, x")

									    x = list(range(i))

									    lst_time = t.timeit(number=1000)

									    x = {j: 'k' for j in range(i)}

									    dict_time = t.timeit(number=1000)

									    print("{:.6f}        {:.6f}".format(lst_time, dict_time))

									    y_1.append(lst_time)

									    y_2.append(dict_time)