Python字典有多贵？

Question

正如标题所述,Python字典需要处理多少钱？创建,插入,更新,删除,所有这些.

渐近时间复杂性本身很有趣,但它们与例如元组或正常列表的比较.

Answer 1

dicts(就像set你不需要将一个值与每个键相关联,而只是记录一个键是否存在时)是非常优化的.dict从N个键或键/值对创建O(N),取出是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和sets具有数百纳秒的优势.当感兴趣的项目存在时:

$ 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仍然快得多,但是dicts和sets并没有获得太大的收益,但是元组和列表确实如此.

等等 - timeit使得微基准测试变得非常简单(严格来说,只有那些非常罕见的情况下才能保证纳秒很重要,但是,很容易做到,检查其他方面并不困难)案件;-).

Answer 2

字典是Python中调优较多的部分之一,因为它们是语言的重要组成部分.例如,类的成员和堆栈框架中的变量都存储在字典内部.如果它们是正确的数据结构,它们将是一个不错的选择.

根据表现在列表和词典之间进行选择似乎很奇怪:它们做了不同的事情.也许您可以告诉我们您正在尝试解决的问题.