处理 Python 字典的成本有多高？

Question

正如标题所述，处理 Python 字典的成本有多高？创建、插入、更新、删除，全部。

渐近时间复杂度本身很有趣，而且它们与元组或普通列表的比较方式也很有趣。

原文由 Deniz Dogan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

dicts （就像 set s 当你不需要将一个值关联到每个键而只是记录一个键是否存在时）是非常优化的。 Creating a dict from N keys or key/value pairs is O(N) , fetching is O(1) , putting is O(1) , and so forth .对于任何非微型容器，真的不能做任何更好的事情！

对于微型容器，您可以使用基于 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 使得运行微基准测试变得非常容易（严格来说，只有在纳秒确实很重要的极少数情况下才能保证，但是，很容易做到，它是检查其他情况没有太大困难；-)。

原文由 Alex Martelli 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

字典是 Python 中最重要的调整部分之一，因为它们是语言的基础。例如，类的成员和栈帧中的变量都在内部存储在字典中。如果它们是正确的数据结构，它们将是一个不错的选择。

根据性能在列表和字典之间进行选择似乎很奇怪：它们做不同的事情。也许你可以告诉我们更多关于你试图解决的问题。

原文由 Ned Batchelder 发布，翻译遵循 CC BY-SA 2.5 许可协议