python中in在list和dict中查找效率的对比分析

yipeiwu_com7年前Python基础

首先给一个简单的例子,测测list和dict查找的时间:

import time
query_lst = [-60000,-6000,-600,-60,-6,0,6,60,600,6000,60000]
lst = []
dic = {}
for i in range(100000000):
 lst.append(i)
 dic[i] = 1 
start = time.time()
for v in query_lst:
 if v in lst:
  continue
end1 = time.time()
for v in query_lst:
 if v in dic:
  continue
end2 = time.time()
print "list search time : %f"%(end1-start)
print "dict search time : %f"%(end2-end1)

运行结果:

list search time : 11.836798 
dict search time : 0.000007

通过上例我们可以看到list的查找效率远远低于dict的效率,原因如下:

python中list对象的存储结构采用的是线性表,因此其查询复杂度为O(n),而dict对象的存储结构采用的是散列表(hash表),其在最优情况下查询复杂度为O(1)。

以上这篇python中in在list和dict中查找效率的对比分析就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python实现html转换为pdf报告(生成pdf报告)功能示例

本文实例讲述了Python实现html转换为pdf报告(生成pdf报告)功能。分享给大家供大家参考,具体如下: 1、先说下html转换为pdf:其实支持直接生成,有三个函数pdfkit....

Python实现的生产者、消费者问题完整实例

本文实例讲述了Python实现的生产者、消费者问题。分享给大家供大家参考,具体如下: 生产者、消费者问题,经典的线程同步问题:假设有一个缓冲池(列表),生产者往里面放东西,消费者从里面取...

python+Splinter实现12306抢票功能

本文实例为大家分享了python实现12306抢票功能的具体代码,供大家参考,具体内容如下 源码记录如下: #!/usr/bin/env python # _*_ coding:ut...

python实现RabbitMQ的消息队列的示例代码

最近在研究redis做消息队列时,顺便看了一下RabbitMQ做消息队列的实现。以下是总结的RabbitMQ中三种exchange模式的实现,分别是fanout, direct和topi...

用Python输出一个杨辉三角的例子

关于杨辉三角是什么东西,右转维基百科:杨辉三角 稍微看一下直观一点的图:复制代码 代码如下:        1       1 1      1 2 1     1 3 3 1    1...