Python 中list ,set,dict的大规模查找效率对比详解

yipeiwu_com6年前Python基础

很多时候我们可能要频繁的进行元素的find 或in操作,本人一直天真的以为python的list做了hash,通过红黑树来高效查找···直到今天我真正来测试它和set,dict的查找效率时,才发现自已想太多了!!!!

先看代码:

__author__ = 'jmh081701'
import numpy
import time
l=[]
sl=set()
dl=dict()
r=numpy.random.randint(0,10000000,100000)
for i in range(0,100000):
  l.append(r[i])
  sl.add(r[i])
  dl.setdefault(r[i],1)
#生成3种数据结构供查找,常规的list,集合sl,字典dl.里面的元素都是随机生成的,为什么要随机生成元素?这是防止某些结构对有序数据的偏向导致测试效果不客观。

start=time.clock()
for i in range(100000):
  t=i in sl
end=time.clock()
print("set:",end-start)
#计算通过set来查找的效率
start=time.clock()
for i in range(100000):
  t=i in dl
end=time.clock()
print("dict:",end-start)
#计算通过dict的效率
start=time.clock()
for i in range(100000):
  t=i in l
end=time.clock()
print("list:",end-start)
#计算通过list的效率

结果:

set: 0.01762632617301519
dict: 0.021149536796960248
······
···
··

呵呵呵呵···list等了20分钟都没出结果。

所以···结果一览无余啊。

查找效率:set>dict>list

单次查询中:看来list 就是O(n)的;而set做了去重,本质应该一颗红黑树(猜测,STL就是红黑树),复杂度O(logn);dict类似对key进行了hash,然后再对hash生成一个红黑树进行查找,其查找复杂其实是O(logn),并不是所谓的O(1)。O(1)只是理想的实现,实际上很多hash的实现是进行了离散化的。dict比set多了一步hash的过程,so 它比set慢,不过差别不大。

so,如果是要频繁的查找,请使用set吧!

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

django rest framework 实现用户登录认证详解

django rest framework 实现用户登录认证详解

1、安装 pip install djangorestframework 2、创建项目及应用 创建项目 创建应用 目录结构如图 3、设置settings.py 设置数据库...

Python 微信之获取好友昵称并制作wordcloud的实例

Python 微信之获取好友昵称并制作wordcloud的实例

最近看到网上有人用Python获取微信的一些信息,感觉挺有意思,对于我一个Python刚入门的人来说,正需要一些代码片段来激起我的兴趣,所以自己也写了一些,废话不多说,直接上代码!!!...

在PyCharm中实现关闭一个死循环程序的方法

在PyCharm中实现关闭一个死循环程序的方法

由于刚刚学习python,对PyCharm也不是很熟悉,在成功运行多个死循环程序而没有关闭它的情况下,PyCharm成功的经常无响应,反应缓慢,一度怀疑是电脑出问题了,经过多次试验,嗯,...

python实现写数字文件名的递增保存文件方法

如下所示: col = [] img = "test1" img1 = "test2" col.append(img) col.append(img1) data=np....

Python中使用pypdf2合并、分割、加密pdf文件的代码详解

朋友需要对一个pdf文件进行分割,在网上查了查发现这个pypdf2可以完成这些操作,所以就研究了下这个库,并做一些记录。首先pypdf2是python3版本的,在之前的2版本有一个对应p...