专栏首页python3Python 中list ,set,di

Python 中list ,set,di

很多时候我们可能要频繁的进行元素的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-Dict&Set类型

    'Adam' ==> 95 'Lisa' ==> 85 'Bart' ==> 59

    py3study
  • 【C语言】求1+2!+3!+...+20

    py3study
  • python(四)

          在python里面  set是基本数据类型的一种集合的类型,他有可变的集合(set())和不可变的(frozenset)两种,包括集合set,集合s...

    py3study
  • 祝贺西安电子科技大学腾讯创新俱乐部成立十周年

    前言 以“快乐创新,Q出未来”为口号,以“做优秀产品,办精品活动”为宗旨,西安电子科技大学腾讯创新俱乐部十岁了!在历任主席团成员及所有西电TICer们的共同努力...

    腾讯高校合作
  • PostgreSQL 烤面包的味道好极了 TOAST

    在传统的数据库中,DBA最恨 听到的词就是,我要使用 BLOB 字段,或者类似的类型来处理,huge的数据,他可能是一段图形的在转换后的“乱码”,也可能是某个...

    AustinDatabases
  • AB实验人群定向HTE模型2 - Causal Tree with Trigger

    这篇论文是在 Recursive Partitioning for Heterogeneous Casual Effects 的基础上加入了两个新元素:

    风雨中的小七
  • 数据库高并发解决方法总结

    一个项目刚开始的时候是为了实现基本功能,随着版本和功能的迭代,大数据和高并发成了软件设计必须考虑的问题!

    lyb-geek
  • 【DB笔试面试505】基于存储层的容灾复制方案有哪些?

    基于存储设备的数据复制技术的核心是利用存储阵列自身的盘阵对盘阵的数据块复制技术实现对生产数据的远程拷贝,从而实现生产数据的灾难保护。在主数据中心发生灾难时,可以...

    小麦苗DBA宝典
  • react 和 redux 入门

    本文作者:IMWeb 王少飞 原文出处:IMWeb社区 未经同意,禁止转载 react的核心思想:组件封装。 页面的所有元素都是可以封装成组件 rea...

    IMWeb前端团队
  • 腾讯云分布式数据库 DCDB 架构解密

    腾讯云金融级数据库 CDB for TDSQL (Cloud DataBase for Tecent Distribute SQL)是一个适用于 OLTP 场景...

    胡彬

扫码关注云+社区

领取腾讯云代金券