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吧！
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持小牛知识库。
-
本文向大家介绍python中in在list和dict中查找效率的对比分析，包括了python中in在list和dict中查找效率的对比分析的使用技巧和注意事项，需要的朋友参考一下 首先给一个简单的例子，测测list和dict查找的时间： 运行结果： 通过上例我们可以看到list的查找效率远远低于dict的效率，原因如下： python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n
-
本文向大家介绍浅谈二分法查找和原始算法查找的效率对比，包括了浅谈二分法查找和原始算法查找的效率对比的使用技巧和注意事项，需要的朋友参考一下 我就废话不多说了，大家还是直接看代码吧！ 查找结果： 总结： 总结过我们可以看出，二分法查找几乎是不耗时，所以方法是很重要的 补充知识：顺序查找与二分查找时间复杂度的比较 注意要点：通过System.currentTimeMills();来获取当前时间，来计算
-
本文向大家介绍python中dict和list的区别,dict的内部实现？相关面试题，主要包含被问及python中dict和list的区别,dict的内部实现？时的应答技巧和注意事项，需要的朋友参考一下 参考回答： dict查找速度快,占用的内存较大,list查找速度慢,占用内存较小,dict不能用来存储有序集合。Dict用{}表示,list用[]表示。 dict是通过hash表实现的,dict为
-
本文向大家介绍在JavaScript Power Set中查找集合的功率集，包括了在JavaScript Power Set中查找集合的功率集的使用技巧和注意事项，需要的朋友参考一下 集合S的幂集是S的所有子集的集合，包括空集和S本身。集合S的幂集表示为。 例如 如果S = {x，y，z}，则子集为- 我们需要编写一个JavaScript函数，该函数将数组作为唯一参数。该功能应找到并返回输入阵列的
-
本文向大家介绍Python中内置数据类型list,tuple,dict,set的区别和用法，包括了Python中内置数据类型list,tuple,dict,set的区别和用法的使用技巧和注意事项，需要的朋友参考一下 Python语言简洁明了，可以用较少的代码实现同样的功能。这其中Python的四个内置数据类型功不可没，他们即是list, tuple, dict, set。这里对他们进行一个简明的总
-
上一篇文章出现了个明显的知识点错误，不过感谢有个网友的提出，及时进行了修改。也希望各位多多包涵。 注：(2019年09月01日15:28:00) 在修改文章的时候，发现自己两年前写的像屎一样, 忍不住还在群里吐槽一番。 目录