Python字典的处理成本如何？

Question

如标题所述，Python 字典在操作过程中的开销有多大？包括创建、插入、更新和删除等操作。

虽然渐近时间复杂度本身很有趣，但也要考虑它们与元组或普通列表等其他数据结构的比较。

- Deniz Dogan

---

相关：https://dev59.com/IkXRa4cB1Zd3GeqPu9WJ - Nick Dandoulakis

Answer 1

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 让运行微基准测试变得非常容易（严格来说，只有在那些纳秒确实很重要的极为罕见的情况下才需要保证，但是容易做到，检查其他情况也不是太困难;-)。

- Alex Martelli

---

非常有趣！但是当我运行以下代码时： $ python -m timeit -s 'empty=();23 in empty' 10000000 次循环，3 次取最优结果：每次循环耗时 0.0221 微秒意思是，两个语句被组合成一个（使用分号）。 - Nanda Kishore

Answer 2

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

基于性能来选择列表和字典似乎有些奇怪：它们执行不同的操作。也许您可以告诉我们更多关于您尝试解决的问题。

- Ned Batchelder

---

实际问题在于，在Django中，“querysets”是不可变的，而我需要从查询集中获取每个对象的几乎所有信息，但它们都需要是可变的，而它们却不是。 - Deniz Dogan

我不确定你的意思：从查询集返回的对象是可变的：你可以修改它们，然后调用.save()等函数。 - Ned Batchelder

那么我如何向一个datetime对象添加一个值为1的属性hello呢？ - Deniz Dogan

datetime 对象是不可变的，我相信这与 Django 无关。(1) 你为什么需要这样做？(2) 你不需要这样做，重写你的代码以解决它。(3) 或许尝试使用一个包装对象？ - David Z

谢谢。我刚意识到我甚至没有添加属性，我只是修改了一个已经存在的属性。我使用的是bicycle['hello']而不是bicycle.hello，这就是我的问题所在...我应该开始喝咖啡了。 - Deniz Dogan

Answer 3

今天是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

- z0rberg's