比较列表和字典的包含操作性能-python

《Python数据结构与算法分析》（第二版）
《Python基础教程》（第三版）

列表的包含操作时间复杂度：O(n)
字典的包含操作时间复杂度：O(1)

首先创建一个包含一些数的列表，然后取一些随机数， 看看它们是否在列表中。随着列表变长，判断一个数是否在列表的时间也就越长。

对于以数字为键的字典，重复上述过程。但是随着字典变大时，判断数字是否在字典中的耗时基本不变，而且比列表快得多。

# !/user/bin/env python# coding:utf-8import timeitimport randomfor iinrange(10000,1000001,20000):
    t= timeit.Timer("random.randrange(%d) in x "% i,# random.randrange()是生成随机整数的标准函数"from __main__ import random, x")# randrange([start], stop, [step]) 从range(start, stop, step)中随机地选择一个数

    x=list(range(i))# 构造包含数字0~(i-1)的列表
    list_time= t.timeit(number=1000)# 返回列表包含操作所需时间

    x={j:Nonefor jinrange(i)}# 构造键值为数字0~(i-1)的字典
    dict_time= t.timeit(number=1000)# 返回字典包含操作所需时间print("%d, %10.3f, %10.3f"%(i, list_time, dict_time))

测试结果：

可以看出，字典一直更快；且随着规模的增加，列表的包含操作在耗时上的增长是线性的，即O(n)；对于字典，即使规模增加，包含操作的耗时也是恒定的，即O(1)。