Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is a time complexity of move_to_end operation for OrderedDict in Python 3?

I've found the source code and it seems to be O(1), since it's basically an update of a linked list and a dict. Though I'm not sure.

What do you think? Thank you!

like image 427
tkrishtop Avatar asked Feb 21 '19 13:02

tkrishtop


1 Answers

You can check the pure Python implementation of OrderedDict.move_to_end(), which is equivalent to the C implementation:

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

Basically, this method looks up a link in a linked list in a dictionary self.__map and updates the previous and next pointers for the link and its neighbors.
Since all of the operations above take constant time, the complexity of OrderedDict.move_to_end() is constant as well.

like image 112
Eugene Yarmash Avatar answered Sep 18 '22 14:09

Eugene Yarmash