Есть ли причины не использовать упорядоченный словарь?

Ответ 1

OrderedDict является подклассом dict и требует больше памяти для отслеживания порядка добавления ключей. Это не тривиально. Реализация добавляет второй dict под обложки и двусвязный список всех ключей (часть, которая помнит порядок), и пучок прокси-серверов weakref. Это не лот медленнее, но, по крайней мере, удваивает память с помощью простого dict.

Но если это уместно, используйте его! Вот почему он там: -)

Как это работает

Базовый dict - это просто обычный ключ сопоставления ключей для значений - он вообще не "упорядочен". Когда добавляется пара <key, value>, в список добавляется key. Список - это часть, которая запоминает заказ.

Но если это список Python, удаление, клавиша займет время O(n) дважды: O(n) время, чтобы найти ключ в списке, и O(n) время, чтобы удалить из списка.

Таким образом, вместо этого он представляет собой двусвязный список. Это позволяет удалить константу ключа (O(1)). Но нам все равно нужно найти двусвязный список node, принадлежащий ключу. Чтобы сделать это время O(1), второй - скрытый - dict сопоставляет ключи узлам в двусвязном списке.

Таким образом, добавление новой пары <key, value> требует добавления пары к базовому dict, создания нового дважды связанного списка node для хранения ключа, добавления этого нового node к двусвязному списку и сопоставления ключ к этому новому node в скрытом dict. Немного в два раза больше работы, но все же O(1) (ожидаемый случай) время в целом.

Аналогично, удаление существующего ключа также немного превышает вдвое больше работы, но O(1) ожидаемое время в целом: используйте скрытый файл dict, чтобы найти ключевой дважды связанный список node, удалить node из список и удалите ключ из обоих dicts.

Etc. Это довольно эффективно.

Ответ 2

многопоточность

если ваш словарь доступен из нескольких потоков без блокировки, особенно в качестве точки синхронизации.

Операции vanilla dict являются атомарными, а любой тип, расширенный в Python, не является.

Фактически, я даже не уверен, что OrderedDict является потокобезопасным (без блокировки), хотя Я не могу упустить возможность того, что он был очень тщательно закодирован и удовлетворяет определению реентерации.

меньшие дьяволы

использование памяти, если вы создаете тонны этих словарей

Использование cpu, если весь ваш код выполняет munge эти словари

Ответ 3

почему я не должен использовать это вместо обычного словаря

В Python 2.7 использование normal OrderedDict приведет к созданию эталонных циклов. Поэтому для использования OrderedDict требуется, чтобы сборщик мусора был включен, чтобы освободить память. Да, сборщик мусора включен по умолчанию в cPython, но отключение его использует его.

например. С cPython 2.7.14

from __future__ import print_function

import collections
import gc

if __name__ == '__main__':
    d = collections.OrderedDict([('key', 'val')])
    gc.collect()
    del d
    gc.set_debug(gc.DEBUG_LEAK)
    gc.collect()
    for i, obj in enumerate(gc.garbage):
        print(i, obj)

выходы

gc: collectable <list 00000000033E7908>
gc: collectable <list 000000000331EC88>
0 [[[...], [...], 'key'], [[...], [...], 'key'], None]
1 [[[...], [...], None], [[...], [...], None], 'key']

Даже если вы просто создаете пустой OrderedDict (d = collections.OrderedDict()) и ничего не добавляете к нему или явно пытаетесь его очистить, вызывая метод clear (d.clear() до del d), вы все равно получите один список саморегуляции:

gc: collectable <list 0000000003ABBA08>
0 [[...], [...], None]

Это, по-видимому, имело место, так как this commit удалил метод __del__, чтобы предотвратить возможность OrderedDict вызывают нецелесообразные циклы, которые, возможно, хуже. Как отмечено в списке изменений для этой фиксации:

Проблема # 9825: удалена __del__ из определения collection.OrderedDict. Это предотвращает создание пользовательских саморегуляции упорядоченных словарей из превращаясь в постоянный безвозвратный мусор GC. Недостатком является то, что удаление __del__ означает, что внутренний двусвязный список должен ждать Сбор GC, а не освобождение памяти сразу, когда refcnt падает к нулю.

Обратите внимание, что в Python 3 fix для той же проблемы было сделано по-другому и использует proxree-proxy для избежания циклов:

Проблема № 9825: Использование __del__ в определении коллекций. Записан возможно для пользователя создавать саморегулированные упорядоченные словари которые становятся постоянно безнадежным мусором GC. Обновлен Py3.1 подход использования слабых proxy-прокси, чтобы ссылочные циклы никогда не создавались в первую очередь.