有序字典(OrderedDict)的set、get和popitem性能

Question

由于OrderedDict需要维护项目的插入顺序，我想知道Python 2.7中get / set / popitem的性能如何。到目前为止还没有找到任何官方文件。 我猜测get是O（1），set是O（logN），popitem是O（1）。 这里是collection.OrderedDict文档documentation。

- Lin Ma

---

@Kun，感谢并点赞。在提问之前，我参考了一些在线文档和讨论。在你提到的讨论中，似乎得出结论set/get/popitem都是O(1)。但我没有找到任何官方文件说明它们确实是O(1)。顺便说一下，如果你读了我的帖子，我的问题是有关OrderedDict时间复杂度的官方文档在哪里。:) 如果我理解有误，请随时纠正。 - Lin Ma

Answer 1

我刚刚查看了Python Mercurial存储库中有序列表对象的实现(Implementation of python Orderedlist object from Python mercurial repository)。在odictobject.c文件的注释中，他们声明：Python的OrderedDict的一个不变量是它保留了dict方法的时间复杂度，特别是O(1)操作。

- kun

---

谢谢Kun，感谢你的回复。我阅读了代码库以了解它们实现逻辑，并对popitem实现的逻辑有些困惑。我想知道它是如何使用O(1)实现的？通常应该有一个堆或其他类似的数据结构来维护插入顺序，以便从最后或从最前弹出时，它们总是可以找到正确的项？ - Lin Ma

从代码实现来看，我没有看到他们使用堆或其他数据结构，所以我认为你是正确的，他们正在使用O(1)的实现。如果您能更清楚地解释一下他们如何使用O(1)实现这种性能，那就太好了。 :) - Lin Ma

嗨Kun，如果你能就我的问题提供建议，那就太好了。谢谢。 - Lin Ma

你链接的那段代码非常漂亮。 - Chris Conlan

实现使用双向链表。因此，在列表的任一端进行删除的时间复杂度为O(1)。 - sourcedelica