70

我指的是模块中的OrderedDictcollections，它是一个有序字典。

如果它具有可订购的附加功能，我意识到这通常可能不是必需的，但即便如此，是否有任何缺点？是不是比较慢？它缺少任何功能吗？我没有看到任何缺失的方法。

简而言之，为什么我不应该总是使用它而不是普通字典？

4

4 回答 4

156

OrderedDict是 的子类dict，需要更多内存来跟踪添加键的顺序。这不是微不足道的。该实现在幕后添加了第二个dict，所有键的双向链接列表（这是记住顺序的部分），以及一堆weakref代理。它并没有慢很多dict，但至少比使用普通.

但是，如果合适，请使用它！这就是它存在的原因:-)

这个怎么运作

基本字典只是一个普通的字典，将键映射到值 - 它根本不是“有序的”。添加一<key, value>对时，将key附加到列表中。列表是记住顺序的部分。

但如果这是一个 Python 列表，删除一个键将花费O(n)两倍的 O(n)时间：在列表中找到键的O(n)时间，以及从列表中删除键的时间。

所以它是一个双向链表。这使得删除一个关键常数 ( O(1)) 时间。但是我们仍然需要找到属于该键的双向链表节点。为了缩短操作O(1)时间，第二个隐藏的 dict 将键映射到双向链表中的节点。

因此，添加一个新<key, value>对需要将该对添加到基本字典，创建一个新的双向链表节点来保存密钥，将该新节点附加到双向链表，并将密钥映射到隐藏字典中的该新节点. 工作量增加了一倍多，但O(1)总体上仍然（预期的情况）时间。

类似地，删除一个存在的键也需要两倍多的工作量，但O(1)总体而言是预期的时间：使用隐藏的字典来查找键的双向链表节点，从列表中删除该节点，然后从两个字典中删除键。

等等，效率很高。

于 2013-09-23T03:04:23.010 回答
8

从 Python 3.7 开始，所有字典都保证是有序的。Python 贡献者确定，切换到 make dictorder 不会对性能产生负面影响。我不知道与Python >= 3.7OrderedDict相比的性能如何dict，但我想它们是可比较的，因为它们都是有序的。

OrderedDict请注意，和的行为仍然存在差异dict。另请参阅：OrderedDict 在 Python 3.7 中会变得多余吗？

于 2018-11-29T09:36:58.530 回答
7

多线程

如果您的字典是在没有锁的情况下从多个线程访问的，尤其是作为同步点。

vanilla dict 操作是原子的，在 Python 中扩展的任何类型都不是。

事实上，我什至不确定 OrderedDict 是线程安全的（没有锁），尽管我不能排除它被非常仔细地编码并满足重入定义的可能性。

小恶魔

如果您创建大量这些字典，则内存使用情况

如果您的代码所做的只是处理这些字典，则 cpu 使用情况

于 2013-10-21T02:10:20.380 回答
3

为什么我不应该总是使用它而不是普通字典

在 Python 2.7 中，正常OrderedDict使用会创建引用循环。因此，任何使用都OrderedDict需要启用垃圾收集器才能释放内存。是的，垃圾收集器在 cPython 中默认开启，但禁用它有其用途。

例如使用 cPython 2.7.14

from __future__ import print_function

import collections
import gc

if __name__ == '__main__':
    d = collections.OrderedDict([('key', 'val')])
    gc.collect()
    del d
    gc.set_debug(gc.DEBUG_LEAK)
    gc.collect()
    for i, obj in enumerate(gc.garbage):
        print(i, obj)

输出

gc: collectable <list 00000000033E7908>
gc: collectable <list 000000000331EC88>
0 [[[...], [...], 'key'], [[...], [...], 'key'], None]
1 [[[...], [...], None], [[...], [...], None], 'key']

即使您只是创建一个空的OrderedDict( d = collections.OrderedDict()) 并且不向其中添加任何内容，或者您​​明确地尝试通过调用clear方法 ( d.clear()before del d) 来清理它，您仍然会得到一个自引用列表：

gc: collectable <list 0000000003ABBA08>
0 [[...], [...], None]

这似乎是这种情况，因为此提交删除了该__del__方法，以防止可能OrderedDict导致无法收集的循环，这可以说是更糟的。如该提交的更改日志中所述：

问题 #9825：从 collections.OrderedDict 的定义中删除了 __del__。这可以防止用户创建的自引用有序字典成为永久无法收集的 GC 垃圾。缺点是删除 __del__ 意味着内部双向链表必须等待 GC 收集，而不是在 refcnt 降至零时立即释放内存。

请注意，在 Python 3 中，对同一问题的修复方式有所不同，并使用弱引用代理来避免循环：

问题 #9825：在 collections.OrderedDict 的定义中使用 __del__ 使用户可以创建自引用的有序字典，这些字典将成为永久不可回收的 GC 垃圾。恢复了使用弱引用代理的 Py3.1 方法，这样一开始就不会创建引用循环。

于 2017-10-25T14:36:40.280 回答