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

逃离我推掉我的手 2023-07-10 11:09 141阅读 0赞

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

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

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

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

# !/user/bin/env python
    # coding:utf-8
    import timeit
    import random
    
    for i in range(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: None for j in range(i)}# 构造键值为数字0~(i-1)的字典
        dict_time = t.timeit(number=1000)# 返回字典包含操作所需时间
    
        print("%d, %10.3f, %10.3f" % (i, list_time, dict_time))

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]  
可以看出，字典一直更快；且随着规模的增加，列表的包含操作在耗时上的增长是线性的，即O(n)；对于字典，即使规模增加，包含操作的耗时也是恒定的，即O(1)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301214142537.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA==,size_16,color_FFFFFF,t_70