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

很多时候我们可能要频繁的进行元素的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吧！

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python list多级排序知识点总结

    在python3的sorted中去掉了cmp参数,转而推荐"key+lambda"的方式来排序. 如果需要对python的list进行多级排序.有如下的数据: list_num = [[12,3],[18,34],[18,10],[12,45],[18,10],[8,34]] 需要从小到大的排序.先比较第一个数,如果第一个数相等的话比较第二个数.代码如下: #默认的sort函数会先对第一个比较,如果第一个相等再比较第二个 print(sorted(list_num)) //OUTPUT

  • Python List列表对象内置方法实例详解

    本文实例讲述了Python List列表对象内置方法.分享给大家供大家参考,具体如下: 前言 在上一篇中介绍了Python的序列和String类型的内置方法,本篇继续学习作为序列类型成员之一的List类型的内置方法. 软件环境 系统 UbuntuKylin 14.04 软件 Python 2.7.3 IPython 4.0.0 列表List 列表是一种容器,存放内存对象的引用.即是任意内存对象的有序集合,不同的类型对象可以存放在同一个列表中.通过索引来访问其中的元素.可以任意的嵌套.伸长.异构.

  • Python列表list常用内建函数实例小结

    本文实例总结了Python列表list常用内建函数.分享给大家供大家参考,具体如下: >>> x = list(range(10)) >>> import random >>> random.shuffle(x) #打乱顺序 >>> x [2, 4, 5, 9, 3, 7, 8, 0, 6, 1] >>> max(x) #返回最大值 9 >>> min(x) #返回最小值 0 >>>

  • Python中的list与tuple集合区别解析

    Python中内置了list集合与tuple集合,在list集合中可以实现元素的添加.修改.插入.以及删除.tuple集合看似与list类似,但两者还是有很大的区别. 在tuple集合中,一旦元素被存储,以后就不能修改,删除了,这比list集合安全许多,所以能用tuple就用tuple.以下是list集合代码实现. L=['Java','Python','C++'] #注意,这里用的是中括号来表示list集合 L.append('PhP')#元素的添加 print(L[-1])#查找最后一个元素

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

    很多时候我们可能要频繁的进行元素的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,10

  • 对python中xlsx,csv以及json文件的相互转化方法详解

    最近需要各种转格式,这里对相关代码作一个记录,方便日后查询. xlsx文件转csv文件 import xlrd import csv def xlsx_to_csv(): workbook = xlrd.open_workbook('1.xlsx') table = workbook.sheet_by_index(0) with codecs.open('1.csv', 'w', encoding='utf-8') as f: write = csv.writer(f) for row_num

  • 浅谈python中统计计数的几种方法和Counter详解

    1) 使用字典dict() 循环遍历出一个可迭代对象中的元素,如果字典没有该元素,那么就让该元素作为字典的键,并将该键赋值为1,如果存在就将该元素对应的值加1. lists = ['a','a','b',5,6,7,5] count_dict = dict() for item in lists: if item in count_dict: count_dict[item] += 1 else: count_dict[item] = 1 2) 使用defaultdict() defaultdi

  • python中urllib.request和requests的使用及区别详解

    urllib.request 我们都知道,urlopen()方法能发起最基本对的请求发起,但仅仅这些在我们的实际应用中一般都是不够的,可能我们需要加入headers之类的参数,那需要用功能更为强大的Request类来构建了 在不需要任何其他参数配置的时候,可直接通过urlopen()方法来发起一个简单的web请求 发起一个简单的请求 import urllib.request url='https://www.douban.com' webPage=urllib.request.urlopen(

  • 基于Python中单例模式的几种实现方式及优化详解

    单例模式 单例模式(Singleton Pattern)是一种常用的软件设计模式,该模式的主要目的是确保某一个类只有一个实例存在.当你希望在整个系统中,某个类只能出现一个实例时,单例对象就能派上用场. 比如,某个服务器程序的配置信息存放在一个文件中,客户端通过一个 AppConfig 的类来读取配置文件的信息.如果在程序运行期间,有很多地方都需要使用配置文件的内容,也就是说,很多地方都需要创建 AppConfig 对象的实例,这就导致系统中存在多个 AppConfig 的实例对象,而这样会严重浪

  • 对python中的for循环和range内置函数详解

    如下所示: 1.for循环和range内置函数配合使用 range函数生成一个从零开始的列表, range(4)表示list:0123 range(1,11,2)表示从1开始到11-1为止步长为2的list:13579 即range(i)表示从0开始到i-1的列表,range(m,n)表示从m开始到n-1的列表,range(m,n,t)表示从m开始步长为t到n-1的列表 ''' print('第一次循环输出:') for i in range(4): print(i) print('第二次循环输

  • 对python中的float除法和整除法的实例详解

    从python2.2开始,便有两种除法运算符:"/"."//".两者最大区别在: python2.2前的版本和python2.2以后3.0以前的版本的默认情况下,"/"所做的除法是以一种两个数或者多个数出现一个浮点数结果就以浮点数的形式表示,即float除法 "//"所做的除法则不相同,"//"不管两者出现任何数,都以整除结果为准,不对小数部分进行处理,直接抛弃,也就是整除法 以下是笔者在编译器测试的数据,

  • 对Python中一维向量和一维向量转置相乘的方法详解

    在Python中有时会碰到需要一个一维列向量(n*1)与另一个一维列向量(n*1)的转置(1*n)相乘,得到一个n*n的矩阵的情况.但是在python中, 我们发现,无论是".T"还是"np.transpose"都无法实现一维向量的转置,相比之下,Matlab一句" a' "就能实现了. 那怎么实现呢?我找了个方法.请看: 即,我们把向量reshape一下,如此便实现了一维向量与一维向量转置相乘为矩阵的目的. 若大家有其他方法望告知. 以上这篇对

  • 对python中的*args与**kwgs的含义与作用详解

    在定义函数的时候参数通常会使用 *args与**kwgs,形参与实参的区别不再赘述,我们来解释一下这两个的作用. *args是非关键字参数,用于元组,**kw是关键字参数 例如下面的代码 def foo(*args,**kwargs): print 'args is',args print 'kwargs is',kwargs foo(1,2) foo(k=1,w=2,a=3,r=4,g=5,s=6) foo(1,2,a=1,b=2,c=2) foo('a',1,None,a=1,b='2',c

  • 对python中的乘法dot和对应分量相乘multiply详解

    向量点乘 (dot) 和对应分量相乘 (multiply) : >>> a array([1, 2, 3]) >>> b array([ 1., 1., 1.]) >>> np.multiply(a,b) array([ 1., 2., 3.]) >>> np.dot(a,b) 6.0 矩阵乘法 (dot) 和对应分量相乘 (multiply) : >>> c matrix([[1, 2, 3]]) >>

随机推荐