Python字典的开销有多大？

Question

正如标题所说，Python 字典的处理成本有多高？包括创建、插入、更新和删除这些操作。

虽然时间复杂度的理论分析很有趣，但更重要的是它们和元组或普通列表相比如何。

Answer 1

今天是2022年7月6日，我想更新一下被接受答案中的性能数据。我使用的是AMD 5900HS处理器，在低功耗模式下，但仍然连接着电源，使用的是Python 3.10.4，操作系统是Windows 10。

python -mtimeit -s"empty=()" "23 in empty"
20000000 loops, best of 5: 16.9 nsec per loop

python -mtimeit -s"empty=set()" "23 in empty"
20000000 loops, best of 5: 18.1 nsec per loop

python -mtimeit -s"empty=[]" "23 in empty"
20000000 loops, best of 5: 15.1 nsec per loop

python -mtimeit -s"empty=dict()" "23 in empty"
10000000 loops, best of 5: 21.7 nsec per loopop




python -mtimeit -s"empty=range(7)" "23 in empty"
10000000 loops, best of 5: 30.9 nsec per loop

python -mtimeit -s"empty=tuple(range(7))" "23 in empty"
5000000 loops, best of 5: 60 nsec per loop

python -mtimeit -s"empty=set(range(7))" "23 in empty"
20000000 loops, best of 5: 16.6 nsec per loop

python -mtimeit -s"empty=dict.fromkeys(range(7))" "23 in empty"
20000000 loops, best of 5: 18.6 nsec per loop



python -mtimeit -s'empty=range(7)' '5 in empty'
5000000 loops, best of 5: 43 nsec per loop

python -mtimeit -s"empty=tuple(range(7))" "5 in empty"
5000000 loops, best of 5: 46.7 nsec per loop

python -mtimeit -s"empty=set(range(7))" "5 in empty"
20000000 loops, best of 5: 16.6 nsec per loop

python -mtimeit -s"empty=dict.fromkeys(range(7))" "5 in empty"
10000000 loops, best of 5: 18.5 nsec per loop

Answer 2

字典是Python中一个非常重要的部分，因为它们在语言的很多地方都发挥着作用。例如，一个类的成员和栈帧中的变量都是通过字典来存储的。如果字典适合你的需求，它们会是一个不错的选择。

在性能方面选择列表和字典似乎有点奇怪，因为它们的用途不同。也许你可以告诉我们更多关于你想解决的问题。

Answer 3

dicts（字典）就像set（集合），当你只需要记录某个键是否存在，而不需要给每个键关联一个值时，它们的性能优化得非常好。从N个键或者键/值对创建一个dict的时间复杂度是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个项目的容器（不包括你关注的那个），性能的平衡发生了变化，现在字典和集合的优势达到了数百纳秒。当你关注的项目确实存在时：

$ 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

字典和集合的优势不大，但元组和列表的表现却提升了，尽管字典和集合依然快得多。

依此类推，timeit让你轻松运行微基准测试（严格来说，这只适用于那些极少数纳秒真的重要的情况，但因为操作简单，所以检查其他情况也没什么大不了的；-）。