是否有任何不使用OrderedDict的理由? [英] Are there any reasons not to use an OrderedDict?

问题描述

我指的是collections模块，这是一个有序的字典.

I'm referring to the OrderedDict from the collections module, which is an ordered dictionary.

如果它具有可订购的附加功能，我意识到这通常不是必需的，但是即使如此，是否还有不利之处?慢一点吗?是否缺少任何功能?我没有看到任何丢失的方法.

If it has the added functionality of being orderable, which I realize may often not be necessary but even so, are there any downsides? Is it slower? Is it missing any functionality? I didn't see any missing methods.

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

In short, why shouldn't I always use this instead of a normal dictionary?

推荐答案

OrderedDict是dict的子类，并且需要更多内存来跟踪键的添加顺序.这不是小事.该实现在幕后添加了第二个dict，以及所有键的双向链接列表(这是记住顺序的部分)，以及一堆weakref代理.这不是很多慢一点，但至少使用普通的dict使内存翻了一番.

OrderedDict is a subclass of dict, and needs more memory to keep track of the order in which keys are added. This isn't trivial. The implementation adds a second dict under the covers, and a doubly-linked list of all the keys (that's the part that remembers the order), and a bunch of weakref proxies. It's not a lot slower, but at least doubles the memory over using a plain dict.

但是如果合适，请使用它！这就是为什么它在那里:-)

But if it's appropriate, use it! That's why it's there :-)

基本dict只是将键映射到值的普通dict-根本不是有序的".添加<key, value>对时，将key追加到列表中.列表是记住订单的部分.

The base dict is just an ordinary dict mapping keys to values - it's not "ordered" at all. When a <key, value> pair is added, the key is appended to a list. The list is the part that remembers the order.

但是，如果这是Python列表，则删除键将花费O(n)时间两次:O(n)时间在列表中查找键，而O(n)时间将其删除.列表中的键.

But if this were a Python list, deleting a key would take O(n) time twice over: O(n) time to find the key in the list, and O(n) time to remove the key from the list.

因此，它是一个双向链接列表.这使得删除键的时间保持恒定(O(1)).但是我们仍然需要找到属于该键的双向链接列表节点.为了使该操作也变得O(1)，第二个-隐藏的-dict将键映射到双向链接列表中的节点.

So it's a doubly-linked list instead. That makes deleting a key constant (O(1)) time. But we still need to find the doubly-linked list node belonging to the key. To make that operation O(1) time too, a second - hidden - dict maps keys to nodes in the doubly-linked list.

因此，添加新的<key, value>对需要将其添加到基本字典，创建一个新的双向链接列表节点来保存密钥，将该新节点附加到双向链接列表中，并将密钥映射到该字符串上.隐藏字典中的新节点.工作量是原来的两倍多，但总的时间还是O(1)(预期的情况).

So adding a new <key, value> pair requires adding the pair to the base dict, creating a new doubly-linked list node to hold the key, appending that new node to the doubly-linked list, and mapping the key to that new node in the hidden dict. A bit over twice as much work, but still O(1) (expected case) time overall.

类似地，删除存在的密钥也是工作量的两倍多，但总的预计时间为O(1):使用隐藏的字典查找密钥的双向链接列表节点，从列表中删除该节点，然后删除这两个字典的关键.

Similarly, deleting a key that's present is also a bit over twice as much work but O(1) expected time overall: use the hidden dict to find the key's doubly-linked list node, delete that node from the list, and remove the key from both dicts.

等等.非常有效.

这篇关于是否有任何不使用OrderedDict的理由?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！