我找到了source code,它似乎是O(1),因为它基本上是一个链表和一个字典的更新。虽然我不确定。
你怎么看?谢谢!
您可以检查OrderedDict.move_to_end()
的纯Python实现,这相当于C实现:
def move_to_end(self, key, last=True):
'''Move an existing element to the end (or beginning if last is false).
Raise KeyError if the element does not exist.
'''
link = self.__map[key]
link_prev = link.prev
link_next = link.next
soft_link = link_next.prev
link_prev.next = link_next
link_next.prev = link_prev
root = self.__root
if last:
last = root.prev
link.prev = last
link.next = root
root.prev = soft_link
last.next = link
else:
first = root.next
link.prev = root
link.next = first
first.prev = soft_link
root.next = link
基本上,此方法在字典self.__map
中查找链接列表中的链接,并更新链接及其邻居的上一个和下一个指针。
由于上述所有操作都需要恒定的时间,因此OrderedDict.move_to_end()
的复杂性也是不变的。