Python字典和列表性能之间的比较
作者:叶庭云 发布时间:2022-08-08 12:49:58
Python列表和字典
前面我们了解了 “大O表示法” 以及对不同的算法的评估,下面来讨论下 Python 两种内置数据类型有关的各种操作的大O数量级:列表 list 和字典dict。
这是 Python 中两种非常重要的数据类型,后面会用来实现各种数据结构,通过运行试验来估计其各种操作运行时间数量级。
对比 list 和 dict 操作如下:
List列表数据类型常用操作性能:
最常用的是:按索引取值和赋值(v=a[i],a[i]=v),由于列表的随机访问特性,这两个操作执行时间与列表大小无关,均为O(1)。
另一个是列表增长,可以选择 append() 和 “+”:lst.append(v),执行时间是O(1);lst= lst+ [v],执行时间是O(n+k),其中 k 是被加的列表长度,选择哪个方法来操作列表,也决定了程序的性能。
测试 4 种生成 n 个整数列表的方法:
创建一个 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))
结果如下:
可以看到,4种方法运行时间差别挺大的,列表连接(concat)最慢,List range最快,速度相差近 100 倍。append要比 concat 快得多。另外,我们注意到列表推导式速度大约是 append 两倍的样子。
总结列表基本操作的大 O 数量级:
我们注意到 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)
结果如下:
将试验结果可视化,可以看出增长趋势:pop()是平坦的常数,pop(0)是线性增长的趋势。
字典与列表不同,是根据键值(key)找到数据项,而列表是根据索引(index)。最常用的取值和赋值,其性能均为O(1)。另一个重要操作contains(in)是判断字典中是否存在某个键值(key),这个性能也是O(1)。
做一个性能测试试验来验证 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)
结果如下:
可见字典的执行时间与规模无关,是常数。
而列表的执行时间则会随着列表的规模加大而线性上升。
更多 Python 数据类型操作复杂度可以参考官方文档:
https://wiki.python.org/moin/TimeComplexity
来源:https://blog.csdn.net/fyfugoyfa/article/details/113845674
猜你喜欢
- 1,jdk配置由于jdk官网的链接不直接支持wget,可以使用下面的方法下载jdk,其中jdk版本为jdk1.8.0_91:wget --n
- 和获取网页上的信息不同,想要进行模拟登录还需要向服务器发送一些信息,如账号、密码等等。模拟登录一个网站大致分为这么几步:1.先将登录网站的隐
- Python是静态作用域语言,但是它自身是一个动态语言。在Python中变量的作用域是由变量在代码中的位置决定的,与C语言有些相似,但不是完
- pyfinance简介在查找如何使用Python实现滚动回归时,发现一个很有用的量化金融包——pyfinance。顾名思义,pyfinanc
- 文档介绍利用python写“猜数字”,“猜词语”,“谁是卧底”这三个游戏,从而快速掌握python编程的入门知识,包括python语法/列表
- 本文实例讲述了python简单读取大文件的方法。分享给大家供大家参考,具体如下:Python读取大文件(GB级别)采用的办法很简单:with
- 您可以使用 ObjectContext 对象提交或放弃一项由 Microsoft Transaction Server (MTS) 管理的事
- Django模板系统压根儿就没想过实现一个全功能的编程语言,所以它不允许我们在模板中执行Python的语句(还是那句话,要了解更多请参看理念
- 没有使用igraph库哦 因为我还没学小世界网络简介:1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型
- 本文实例讲述了Python中的错误和异常处理操作。分享给大家供大家参考,具体如下:#coding=utf8print ''&
- <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN&
- 一、前言:在经过一段时间的存储过程开发之后,写下了一些开发时候的小结和经验与大家共享,希望对大家有益,主要是针对Sybase和SQL Ser
- pandas中iloc()函数DataFrame.iloc纯基于整数位置的索引。import pandas as pdmydict = [{
- 1.join()的用法:使用前面的字符串.对后面的列表进行拼接,拼接结果是一个字符串# lst = ["alex",&q
- asp使用session来防止表单多次被提交的方法。formtest.asp' 表单文件<%Randomize&nb
- VScode查看python f.write()的文件乱码在使用 VScode 编写 python 代码,print(),汉字正常显示,使用
- ExtJS可以用来开发RIA也即富客户端的AJAX应用,是一个用javascript写 的,主要用于创建前端用户界面,是一个与后台技术无关的
- 本文深入剖析了python中dict,set,list,tuple应用及对应示例,有助于读者对其概念及原理的掌握。具体如下:1.字典(dic
- win7 pycharm设置界面全黑色方法:1.设置默认PyCharm解析器: 操作如下:Python–>Preferences–&g
- 前言这篇文章将详细讲解开始图像形态学知识,主要介绍图像腐蚀处理和膨胀处理。数学形态学(Mathematical Morphology)是一种