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

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

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

введите описание изображения здесь


python dictionary collections ordereddictionary lru
person python    schedule 17.11.2015    source источник

Ответы (1)


arrow_upward
9
arrow_downward

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

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

Действительно используется двусвязный список, это указано в строке документации исходного файла. Получение представления о том, насколько вдвойне связанные списки работают и, просматривая источник, вы поймете, как именно это работает:

# 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].
person Dimitris Fasarakis Hilliard    schedule 17.11.2015
comment
Спасибо, это, конечно, очень полезно. - person python; 17.11.2015
comment
Не могли бы вы уточнить последние три строки, в которых говорится о sentinel element. - person python; 17.11.2015
comment
Стражи — это, по сути, фиктивные узлы, используемые для обозначения начала и конца связанных списков в целях оптимизации. Для них есть множество ресурсов [1, 2, 3] и это скорее теоретический аспект. Последнее просто указывает, каким должно быть содержимое каждого узла. - person Dimitris Fasarakis Hilliard; 17.11.2015