数据结构与算法 1-6 Python列表类型不同操作的时间效率

本系列是我在学习《基于Python的数据结构》时候的笔记。本小节首先回顾一下timeit代码执行时间测量模块，然后通过此模块测算Python中list列表一些操作的时间效率。

一

timeit模块

前一小节我们介绍了Python内置的代码执行时间测量模块timeit，timeit模块可以用来测试一小段Python代码的执行速度。接下来简单回顾一下timeit模块。

# Timer是测量小段代码执行速度的类
class timeit.Timer(stmt = "pass", setup = "pass", timer = <timer function>)

1. stmt参数是要测试的代码语句（statment）；
2. setup参数是运行代码时需要的设置；
3. timer参数是一个定时器函数，与平台有关，使用默认值即可；

通过类定义的参数可以看出stmt和setup参数都是string字符串类型。

timeit.Timer.timeit(number = 10000000)

Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数，默认为1000000次。方法返回执行代码的平均耗时，一个float类型的秒数。

二

list的操作测算

首先通过timeit模块来测算一下list四种创建列表操作的时间效率。

执行结果如下所示。

concat  2.0196248714445586 seconds
append  0.11828922818735288 seconds
comprehension  0.05133950992043568 seconds
list range  0.019711093590138784 seconds

这里需要注意的就是在创建Timer类对象时候参数的设置，为了描述方便下面以函数t1为例。

timer1 = Timer("t1()", "from __main__ import t1")

此时程序保存在"06_list.py"文件中，t1函数就存放在"06_list.py"文件中。这里需要注意的就是在创建类对象的时候，代码段t1函数并不会在"06_list.py"中执行，而是在另外一个单独的文件中执行，这也是为什么此时stmt参数为字符串的原因。如果想在这个单独的文件中调用"06_list.py"文件中t1函数，就需要运行环境中存在t1这个函数，因此就需要配置setup参数，此时显示执行文件为"06_list.py"文件，使用"06_list.py"文件作为启动文件的话，名字就变成了"__main__"，因此在外部文件中使用"from __main__ import t1"即可导入启动文件"06_list.py"文件下的t1函数。

三

list中的"+"和extend操作

接下来测算一下list中的"+"操作和extend操作的时间效率。

执行结果如下所示。

extend: 2.0692768273094866 seconds
" + ": 1.2737082011482657 seconds

通过两种构造列表的方式可以看出“+”和extend操作还是有所不同的：

1. +操作的话，首先创建一个新的列表，然后把"+"号左右两边列表中的元素添加到新的列表中；
2. extend操作在于进行扩充的时候list列表对象是不变的，不需要创建一个新的列表；

还有一点就是extend和append区别：

1. append添加元素的时候只能添加单个元素；
2. extend添加元素的时候可以是一个列表或者一个可迭代对象，当添加为可迭代对象的时候会把可迭代对象中的所有元素全部追加到前面列表中，无需创建一个新的列表接收；

总的来说，在创建列表的时候要少用"+"号操作。

四

list的append和insert操作

接下来测算一下list中的append和insert两种为列表添加元素操作的时间效率。

执行结果，此时添加10000个元素，只是为了效果明显。

append: 1.3883072103935907 seconds
insert(0): 33.94062760833102 second

此时可以发现append往尾部添加元素比insert(0)往头部添加元素要快的多。

接下来测算一下在列表头部pop出一个元素和在列表尾部pop出一个元素的时间效率。

执行结果如下所示。

pop_zero: 0.0357990792897073 seconds
pop_end: 0.00010755545995069782 seconds

可以发现pop操作和insert(0)与append操作类似，操作列表的最后一个元素的效率远远高于操作列表第一个元素的效率。这是由list列表使用的数据存储方式所决定的。