由于OrderedDict需要维护项目的插入顺序,我想知道Python 2.7中get / set / popitem的性能如何。到目前为止还没有找到任何官方文件。
我猜测get是O(1),set是O(logN),popitem是O(1)。
这里是collection.OrderedDict文档documentation。
Python的OrderedDict的一个不变量是它保留了dict方法的时间复杂度,特别是O(1)操作。
popitem
实现的逻辑有些困惑。我想知道它是如何使用O(1)
实现的?通常应该有一个堆或其他类似的数据结构来维护插入顺序,以便从最后或从最前弹出时,它们总是可以找到正确的项? - Lin MaO(1)
的实现。如果您能更清楚地解释一下他们如何使用O(1)
实现这种性能,那就太好了。 :) - Lin Ma
O(1)
。但我没有找到任何官方文件说明它们确实是O(1)
。顺便说一下,如果你读了我的帖子,我的问题是有关OrderedDict时间复杂度的官方文档在哪里。:) 如果我理解有误,请随时纠正。 - Lin Ma