Как записывается элемент Python OrderedDict?

Question

Как OrderedDict в Python помнит весь порядок элементов? Какова производительность накладных расходов? Для таких проблем, как реализация LRU, я нашел это очень мощным и очень простым в реализации, но какова производительность? Как он помнит порядок ключей, которые были сначала вставлены?

Использует ли они Dict() и Double Linked List для запоминания ключей, как показано на рисунке ниже? Я буду очень признателен, если вы сможете передать свое сообщение на простом языке, а не поделиться какой-то исследовательской статьей.

Answer 1

Лучше всего о том, что вы можете посмотреть на источник для OrderedDict, чтобы получить хорошее представление о нем.

Это фактически реализовано в чистом питоне! Это означает, что вы можете скопировать его, переопределить и, как правило, причудливо мутировать его столько, сколько хотите, пока не поймете это.

Он использует двусвязный список, это указано в docstring исходного файла. Получение сцепление how doublylinked lists work и при просмотре источника, вы получите хороший повесить, как именно это работает:

# An inherited dict maps keys to values. 
# The inherited dict provides __getitem__, __len__, __contains__, and get. 
# The remaining methods are order-aware. 
# Big-O running times for all methods are the same as regular dictionaries. 

# The internal self.__map dict maps keys to links in a doubly linked list. 
# The circular doubly linked list starts and ends with a sentinel element. 
# The sentinel element never gets deleted (this simplifies the algorithm). 
# Each link is stored as a list of length three: [PREV, NEXT, KEY].