Python数据结构与算法 列表和字典性能比较

简介: 前面我们了解了 “大O表示法” 以及对不同的算法的评估,下面来讨论下 Python 两种内置数据类型有关的各种操作的大O数量级:列表 list 和字典dict。
  • 前面我们了解了 “大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()的计时试验,通过改变列表的大小来测试两个操作的增长趋势:


importtimeitpop_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= []
foriinrange(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 的耗时。


importtimeitimportrandomy_1= []
y_2= []
print("lst_time         dict_time")
foriinrange(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'forjinrange(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

目录
相关文章
|
7天前
|
存储 JSON 索引
一文让你彻底搞懂 Python 字典是怎么实现的
一文让你彻底搞懂 Python 字典是怎么实现的
29 13
|
7天前
|
存储 索引 Python
深度解密 Python 列表的实现原理
深度解密 Python 列表的实现原理
35 13
|
3天前
|
开发者 索引 Python
探索Python中的列表推导式
【9月更文挑战第33天】本文通过直观的示例和代码片段,深入浅出地介绍了Python中强大的功能——列表推导式。我们将从基础概念出发,逐步深入到高级应用,最后探讨其性能考量。无论你是初学者还是有一定经验的开发者,都能在这篇文章中找到有价值的信息。
14 8
|
2天前
|
数据处理 开发者 Python
Python编程中的列表推导式:简洁而强大的工具
【9月更文挑战第35天】在Python的众多特性中,列表推导式以其简明扼要和强大功能脱颖而出。本文不仅将介绍列表推导式的基础知识,还将探讨其背后的逻辑,并辅以实际代码示例。无论你是初学者还是有经验的开发者,都能从中获取新的见解和应用技巧。
12 5
|
7天前
|
Python
探索Python中的列表推导式
【9月更文挑战第30天】在编程的世界里,简洁和高效总是我们追求的目标。Python的列表推导式正是这样一把利器,它允许我们在一行代码中生成列表,既清晰又高效。本文将深入浅出地介绍列表推导式的基础知识、高级技巧以及如何避免常见的陷阱,让你的代码更加优雅。
|
7天前
|
索引 Python
python列表删除元素
python列表删除元素
16 1
|
3月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【7月更文挑战第22天】在大数据领域,Python算法效率至关重要。本文深入解析时间与空间复杂度,用大O表示法衡量执行时间和存储需求。通过冒泡排序(O(n^2)时间,O(1)空间)与快速排序(平均O(n log n)时间,O(log n)空间)实例,展示Python代码实现与复杂度分析。策略包括算法适配、分治法应用及空间换取时间优化。掌握这些,可提升大数据处理能力,持续学习实践是关键。
67 1
|
4月前
|
存储 机器学习/深度学习 算法
Python算法基础教程
Python算法基础教程
22 0
|
数据采集 SQL 算法
C++、Python、数据结构与算法、计算机基础、数据库教程汇总!
C++、Python、数据结构与算法、计算机基础、数据库教程汇总!
211 0
C++、Python、数据结构与算法、计算机基础、数据库教程汇总!
下一篇
无影云桌面