Python列表和集合的效率大比拼
作者:Python编程学习圈 发布时间:2021-09-04 14:10:16
程序运行效率
程序的运行效率分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个程序的运行速度,而空间复杂度主要衡量一个程序所需要的额外存储空间。
一个程序执行所耗费的时间,从理论上说,是不能算出来的,只有你把程序放在机器上跑起来,才能知道,不同机器不同时间得出的结果可能不一样。但是我们需要每个程序都上机测试吗?显然不现实,所以才有了时间复杂度这个分析方式。实际中我们计算时间复杂度时,其实并不一定要计算精确的执行次数,而只需要大概执行次数,一般会使用大O渐进表示法,平时执行次数为1次的我们就可以说时间复杂度是O(1),需要n次的就可以说时间复杂度是O(n)。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少个字节的空间,因为这个实际运行过程中很难计算,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。
Python组合数据类型中常用的主要有元组、列表、集合和字典,每种数据类型不同操作的时间复杂度可以参考Python的官方链接,网页中有详细的说明,
https://wiki.python.org/moin/TimeComplexity
元组和列表都属于序列类型,他们存储机制基本一致;集合和字典也是基本相同,唯一的区别就是集合每个元素没有对应的值。接下来我们以集合和列表为例看看他们的查找效率和存储开销。
数据查找效率
关于集合和列表数据查找效率差距到底有多大?先看一组实例:
import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time() # 测试在列表中进行查找
for num in nums:
if num in list_test:
count_list += 1
t2 = time.time()
for num in nums: # 测试在集合中进行查找
if num in set_test:
count_set += 1
t3 = time.time() # 测试在集合中进行查找
print('找到个数,列表:{},集合:{}'.format(count_list, count_set))
print('使用时间,列表:{:.4f}s'.format(t2 - t1))
print('使用时间,集合:{:.4f}s'.format(t3 - t2))
输出结果为:
找到个数,列表:515,集合:515
使用时间,列表:7.7953s
使用时间,集合:0.0010s
从上面例子可以清楚地看出,集合的查找效率远远高于列表,因此在不同的应用场景下,一定要选择合适的数据类型,在小数据量下看不出来性能区别,一旦换到大数据量下,就会变得差异性很大。
数据存储开销
集合的查找效率比列表要快得多,主要就是他们的存储原理不一样,集合需要消耗更多的空间来存储额外的信息,用空间开销来换时间效率,接下来我们通过getsizeof()函数看看他们存储开销的差异,getiszeof()函数是python的sys模块中用来获取对象内存大小的函数,返回的大小以字节为单位。
import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大小:', sys.getsizeof(list_test))
print('集合占用大小:', sys.getsizeof(set_test))
输出结果为:
列表占用大小:9000112
集合占用大小:33554656
从结果可以看出,同样的数据内容,集合存储的开销是列表的好几倍。
来源:https://developer.51cto.com/article/714424.html
猜你喜欢
- Todo清单需要实现的功能有添加任务、删除任务、编辑任务,操作要关联数据库。任务需要绑定用户,部门。用户需要绑定部门。{#自己编写一个基类模
- 前言thinkphp3.1.2 需要使用cli方法运行脚本折腾了一天才搞定3.1.2的版本真的很古老解决增加cli.php入口文件defin
- 很开心可以和导师阿坚在08gui大赛中一起去完成《fight》的图标设计,在这个过程中真的是受益匪浅!这里我谈一下在这个过程的一些小小心得。
- 本文实例讲述了python计算一个序列的平均值的方法。分享给大家供大家参考。具体如下:def average(seq, total=0.0)
- PHP count() 函数实例计算 car 节点的子节点个数:<?php $xml=<<<XML<cars&
- 我们使用的是QWebview模块,这里也主要是展示下QWebview的用法。之前在网上找了半天的解析网页的内容,都不是很清楚。这是核心代码:
- 任何一位数据库程序员都会有这样的体会:高通信量的数据库驱动程序中,一条糟糕的SQL查询语句可对整个应用程序的运行产生严重的影响,其不仅消耗掉
- server application error--IIS故障故障现象:Server Application Error The serve
- 工厂模式(Factory Pattern)是什么工厂模式是一种创建型模式,它提供了一种创建对象的最佳方式。在工厂模式中,我们在创建对象时不会
- 大家做网站,特别是自己写的代码,常常担心被一些黑客入侵服务器,从而导致网站代码被盗,给自己带来一些损失。那么我们怎么样做,就算黑客盗了你的代
- 获取一组radio被选中项的值var item = $(’input[@name=items][@checke
- 如何在生产上部署Django?Django的部署可以有很多方式,采用nginx+uwsgi的方式是其中比较常见的一种方式。uwsgi介绍uW
- 不论你做什么样的设计,色彩都是一个不容忽视的问题。色彩以一种“隐蔽”的方式传达的各种信息,这些信息会影响观看者的心理和感受,左右他们的判断和
- 正则表达式(Regular Expression,在代码中常简写为regex、regexp或RE)是计算机科学的一个概念。正则表达式使用单个
- 偶然在Google发现了他们的用户体验设计原则,因此翻译作一下记录。1.以人为本 —他们的生活、他们的工作和他们的梦想2.珍惜每一毫秒的时间
- 1、授权机制的主要作用是什么?授权机制的基本作用是给某个主机上的用户对某个数据库以select,insert,update和detete的权
- 创建列表sample_list = ['a',1,('a','b')]Python 列表操作
- 本文将介绍在InterDev中实现网上商店购物车功能的方法,具体步骤如下:一、 数据库结构:产品数据表(Products): 存放产品信息产
- 一、何谓ASP缓存/为什么要缓存当你的web站点采用asp技术建立的初期,可能感觉到的是asp * 页技术带来的便利性,以及随意修改性、自如
- 还有种片面的观点认为,做网站设计与平面差不多,比如老罗发布的这则招聘中提到:年薪十万招擅长做下列网站设计风格的平面设计师一名。在专业角度,网