Python字典要价多少钱？

Question

如标题所述，Python字典要处理多少费用？创建，插入，更新，删除全部。

渐近时间复杂性本身很有趣，但是它们与例如元组或正常列表的比较方式也很有趣。

Answer 1

dicts（就像sets，当您不需要将值关联到每个键，而只需记录一个键是否存在或不存在时）就进行了非常优化。dict根据N个键或键/值对创建a
O(N)，提取is O(1)，摊销摊销O(1)等。对于任何非微型容器，实际上都无法做得更好。

对于小型容器，您可以使用timeit基于基准的基准轻松检查边界。例如：

$ python -mtimeit -s'empty=()' '23 in empty'
10000000 loops, best of 3: 0.0709 usec per loop
$ python -mtimeit -s'empty=set()' '23 in empty'
10000000 loops, best of 3: 0.101 usec per loop
$ python -mtimeit -s'empty=[]' '23 in empty'
10000000 loops, best of 3: 0.0716 usec per loop
$ python -mtimeit -s'empty=dict()' '23 in empty'
10000000 loops, best of 3: 0.0926 usec per loop

这表明，检查空列表或元组中的成员资格比检查空集合或字典中的成员资格要快20-30纳秒。当每十亿分之一秒很重要时，此信息可能与您相关。往上一点…：

$ python -mtimeit -s'empty=range(7)' '23 in empty'
1000000 loops, best of 3: 0.318 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '23 in empty'
1000000 loops, best of 3: 0.311 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '23 in empty'
10000000 loops, best of 3: 0.109 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '23 in empty'
10000000 loops, best of 3: 0.0933 usec per loop

您会看到，对于7项容器（不包括感兴趣的容器），性能的平衡已经发生了变化，现在dicts和set具有上百纳秒的优势。存在感兴趣的物品时：

$ python -mtimeit -s'empty=range(7)' '5 in empty'
1000000 loops, best of 3: 0.246 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '5 in empty'
1000000 loops, best of 3: 0.25 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '5 in empty'
10000000 loops, best of 3: 0.0921 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '5 in empty'
10000000 loops, best of 3: 0.112 usec per loop

dicts和set并不会带来太多收益，但是tuples和list却能获得很大的收益，即使dicts和set仍然要快得多。

依此类推-
等等-timeit轻松运行微基准测试（严格地说，仅在纳秒确实很重要的极为罕见的情况下才需要保证，但是，这样做很容易，检查OTHER并不困难情况;-)。