dict对象,高效的关联式容器

Python 中的 dict 对象是一种 关联式容器 对象,用于保存由  ( key )到  ( value )的映射关系。 借助关联式容器,程序可快速定位到与指定  相关联的 dict 对象在 Python 程序中使用频率非常高,如果应用不当将严重影响程序的执行效率。

本节,我们先从 dict 对象常用操作入手,回顾它的 基本用法 ;接着结合其他内建容器对象,研究 dict 关键操作的 执行效率 ; 最后以 dict 对象 内部结构 收尾,详细讲解其内部 哈希表 的实现要点,以及其中几个关键 性能考量 。 相信通过本节学习,读者将对 dict 实现原理了如指掌,这对用好 dict 对象至关重要。

基本用法

我们用一个 dict 对象来保存培训班学员的成绩,先创建一个空对象:

>>> scores = {}
>>> scores
{}

那么,一个什么都不放的 dict 对象需要占用多少内存呢? 根据前面章节,我们知道对象头部字段是必不可少的。 可我们很惊讶地发现,一个空的 dict 对象居然要占用 240 字节的内存!

>>> import sys
>>> sys.getsizeof(scores)
240

这是为什么呢?后续我们将从 dict 内部的哈希表中寻找答案。现在我们接着回顾 dict 的基本用法。

现在将 jim 的成绩保存保存到 dict 对象中:

>>> scores['jim'] = 70
>>> scores
{'jim': 70}
>>> sys.getsizeof(scores)
240

数据插入后,我们发现 dict 对象内存使用量保存不变。 看来, dict 对象也有一种类似 list 对象的 预分配机制 。

现在,接着存入 lilylucy 以及 tom 的成绩。 我们发现, dict 还没达到扩容条件,内存大小保存不变:

>>> scores['lily'] = 75
>>> scores['lucy'] = 80
>>> scores['tom'] = 90
>>> scores['alice'] = 95
>>> scores
{'jim': 70, 'lily': 75, 'lucy': 80, 'tom': 90, 'alice': 95}
>>> sys.getsizeof(scores)
240

借助 dict 对象,我们可以快速检索出某位学员的成绩。例如,获取 tom 的成绩:

>>> scores['tom']
90

”快速“不是一个精确的形容词,到底多快呢? 这里先给出答案,由于 dict 对象底层由哈希表实现, 查找操作平均时间复杂度是 \(O(1)\) 。 当然了,在哈希不均匀的情况下,最坏时间复杂度是 \(O(n)\) ,但一般情况下很难发生。

当然了,如果有某位学员(例如 lily)转学了,可通过 pop 方法将其剔除:

>>> scores.pop('lily')
75
>>> scores
{'jim': 70, 'lucy': 80, 'tom': 90, 'alice': 95}

哈希表结构决定了 dict 的删除操作也很快,平均时间复杂度也是 \(O(1)\) 。 实际上, dict 插入、删除、查找的平均时间复杂度都是 \(O(1)\) ,最坏时间复杂度是 \(O(n)\)。 因此,哈希函数的选择就至关重要,一个好的哈希函数应该将键尽可能 均匀 地映射到哈希空间中,最大限度地避免 哈希冲突 。

执行效率

我们知道 dict 对象搜索操作时间复杂度为 \(O(1)\) ,远远好于 list 对象的 \(O(n)\) 。 这意味着什么了?为得到一个更准确、直观的感受,我们编写一个测试程序,分别测试不同规模 dict 、 list 对象完成 1000 次搜索所需的时间:

import random
import time

# 随机数生成器
randint = lambda: random.randint(-2**30+1, 2**30-1)

def count_targets(items, targets):
    '''
    计算目标对象出现个数
        items: 待搜索容器
        targets: 待搜索目标元素列表
    '''

    found = 0

    for target in targets:
        if target in items:
            found += 1

    return found

def generate_random_dict(n):
    '''
    生成随机数字典
    '''

    dict_items = {}
    while len(dict_items) < n:
        dict_items[randint()] = True

    return dict_items

def generate_random_list(n):
    '''
    生成随机数列表
    '''

    return [
        randint()
        for _ in range(0, n)
    ]

def test_for_scale(scale, targets):
    '''
    执行一个样例
        scale: 测试容器规模
        targets: 待搜索元素列表
    '''

    # 生成指定规模的随机数容器
    dict_items = generate_random_dict(scale)
    list_items = generate_random_list(scale)

    # 测试dict搜索所需时间
    start_ts = time.time()
    count_targets(dict_items, targets)
    dict_time = time.time() - start_ts

    # 测试list搜索所需时间
    start_ts = time.time()
    count_targets(list_items, targets)
    list_time = time.time() - start_ts

    # 打印结果
    print('Scale:', scale)
    print('Dict:', dict_time)
    print('List:', list_time)
    print()

def main():
    # 每次测试搜索1000次
    # 生成1000个随机数作为搜索目标
    targets = generate_random_list(1000)

    # 以不同规模运行测试函数
    for scale in [1000, 10000, 100000, 1000000]:
        test_for_scale(scale, targets)

if __name__ == '__main__':
main()

测试程序代码逻辑并不复杂,请结合注释阅读理解,这里不再赘述。测试程序执行后,输出内容大致如下:

Scale: 1000
Dict: 0.00012683868408203125
List: 0.03683590888977051

Scale: 10000
Dict: 0.00017213821411132812
List: 0.3484950065612793

Scale: 100000
Dict: 0.00021696090698242188
List: 3.6795387268066406

Scale: 1000000
Dict: 0.0003829002380371094
List: 48.04447102546692

我们将测试结果制作表格, dict 和 list 的表现一目了然:

容器规模

增长系数

dict消耗时间

dict增长系数

list消耗时间

list增长系数

1000

1

0.000129s

1

0.036s

1

10000

10

0.000172s

1.33

0.348s

9.67

100000

100

0.000216s

1.67

3.679s

102.19

1000000

1000

0.000382s

2.96

48.044s

1335.56

从表格中,我们看到:当容器规模增长 1000 倍, dict 搜索时间几乎保持不变,但 list 搜索时间增长了差不多 1000 倍。 当规模达到 10 万时,1000 次 list 搜索花了接近一分钟时间,而 dict 只需 382 微秒! dict 对象完成一次搜索只需 0.382 微秒,也就是说一秒钟可以完成 200 多万次搜索!

dict 对象到底用了什么黑科技呢?接下来,我们一起从它的内部结构中寻找答案。 点击 更多章节,获取更多细节!

更多章节

洞悉 Python 虚拟机运行机制,探索高效程序设计之道!

到底如何才能提升我的 Python 开发水平,向更高一级的岗位迈进? 如果你有这些问题或者疑惑,请订阅我们的专栏,阅读更多章节:

https://cdn.fasionchan.com/python-source-course-qrcode.png

附录

订阅更新,获取更多学习资料,请关注我们的 微信公众号

微信搜索:小菜学编程

创作不易,如果觉得我们写得还行,就请我们喝杯咖啡吧😋

微信搜索:小菜学编程