纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

叶庭云   2021-06-07 我要评论
想了解Python字典和列表性能之间的比较的相关内容吗叶庭云在本文为您仔细讲解Python列表和字典的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Python列表和字典性能对比,Python列表,python字典下面大家一起来学习吧

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


相关文章

猜您喜欢

  • Unity Shader实现线框 Unity Shader实现线框效果的制作步骤

    想了解Unity Shader实现线框效果的制作步骤的相关内容吗小盖子在本文为您仔细讲解Unity Shader实现线框的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Unity,Shader实现线框,Unity,Shader线框下面大家一起来学习吧..
  • Python天气查询 Python实现天气查询软件

    想了解Python实现天气查询软件的相关内容吗数据山谷在本文为您仔细讲解Python天气查询的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Python天气查询软件,python查询工具下面大家一起来学习吧..

网友评论

Copyright 2020 www.fresh-weather.com 【世纪下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式