【Python】（三）Python中的列表

列表是python中常用的基础数据结构。python为列表内置了诸多效率很高的函数。但不同的内置函数其执行效率并不都能同时达到最佳，为此python对这些操作的效率进行了折中。因而，根据具体问题，选择更有效率的执行方式是很有意义的。

获得一个更长的列表

增加列表的长度，获得一个更长的列表，是编程中常见的任务之一。下面我们以四种方式来完成这个任务，并使用 Python 的 timeit 模块，捕获我们的每个函数执行所需的时间。

from timeit import Timer

def method_1(N):
    ###列表连接方式
    total_list = []
    for i in range(N):
        total_list += [i]

def method_2(N):
    ###append追加方式
    total_list = []
    for i in range(N):
        total_list.append(i)

def method_3(N):
    ###列表生成器方式
    total_list = [i for i in range(N)]

def method_4(N):
    ###用list函数直接转化方式
    total_list = list(range(N))
    
def main():
    t1 = Timer("method_1(1000)", "from __main__ import method_1")
    print(t1.timeit(number=100000), "毫秒", " ---列表连接方式")
    t2 = Timer("method_2(1000)", "from __main__ import method_2")
    print(t2.timeit(number=100000), "毫秒", " ---append追加方式")
    t3 = Timer("method_3(1000)", "from __main__ import method_3")
    print(t3.timeit(number=100000), "毫秒", " ---列表生成器方式")
    t4 = Timer("method_4(1000)", "from __main__ import method_4")
    print(t4.timeit(number=100000), "毫秒", " ---用list函数直接转化方式")


if __name__ == "__main__":
    main()

运行结果为：

11.50608054677568 毫秒  ---列表连接方式
12.595507761928646 毫秒  ---append追加方式
4.711808628512113 毫秒  ---列表生成器方式
2.192510759397706 毫秒  ---用list函数直接转化方式

可以看出，列表生成器方式和list函数转化方式的执行效率要更高一些。

从列表中删除元素

从列表中删除元素常用的函数是pop()。当列表末尾调用 pop()时，它需要 O(1), 但是当在列表中第一个元素或者中间任何地方调用 pop(), 它是 O(n)。原因在于 Python 实现列表的方式，当一个项从列表前面取出，列表中的其他元素靠近起始位置移动一个位置。这种差距会随着列表长度的增加变得更加明显。

import matplotlib.pyplot as plt
from timeit import Timer

list_length = [] ##记录列表长度
list_popend = [] ##记录列表尾弹出时间
list_popzero = [] ##记录列表首弹出时间

for i in range(1000000,30000001,1000000):
    print(i)
    list_length.append(i)
    x = list(range(i))
    popend = Timer("x.pop()", "from __main__ import x")
    list_popend.append( popend.timeit(number=100) )
    x = list(range(i))
    popzero = Timer("x.pop(0)", "from __main__ import x")
    list_popzero.append( popzero.timeit(number=100) )

plt.figure(figsize=(8,4))
plt.plot(list_length,list_popend,label="$popend$",color="red",linewidth=2)
plt.plot(list_length,list_popzero,"b--",label="$popzero$")
plt.xlabel("List Length")
plt.ylabel("ms")
plt.legend()
plt.show()

运行结果：

运行时间对比

结果验证了之前的描述。

python中列表主要操作的时间复杂度（来自网络）：