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

Question

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

Я имею в виду OrderedDict С collections модуль.

если он имеет дополнительную функциональность упорядочивания, которая, как я понимаю, часто не нужна, но даже так, есть ли какие-либо недостатки? Это медленнее? Отсутствует ли какая-либо функциональность? Я не видел никаких недостающих методов.

короче, Почему не стоит Я всегда использую это вместо обычного словаря?

742 3

python dictionary python-3.x ordereddictionary

3 ответов:

Comments

Ничего не найдено.

Tim Peters · Accepted Answer · 2013-10-02 03:22:54

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

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

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

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

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

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

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

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

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

Dima Tisnek · Accepted Answer · 2013-10-21 05:10:20

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

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

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

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

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

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

использование ЦП, если весь ваш код делает это munge эти словари

Day · Accepted Answer · 2017-10-25 18:11:18

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

В Python 2.7, нормальный 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]
это, кажется, было так с тех пор этот коммит удалены __del__ метод для предотвращения потенциала для OrderedDict причиной безнадежной циклы, которые, возможно, хуже. Как отмечено в журнале изменений для этого commit:

выпуск #9825: удалено _ _ del__ из определения коллекций.OrderedDict. Это предотвращает создание пользователем самореферентных упорядоченных словарей из становится постоянно не собираемым мусором GC. Недостатком является то, что удаление _ _ del_ _ означает, что внутренний двусвязный список должен ждать Коллекция GC, а не освобождение памяти сразу же, когда refcnt капли обнулить.

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

проблема №9825: использование _ _ del__ в определении коллекций.OrderedDict сделал это возможно для пользователя, чтобы создать автореферентное упорядоченные словари которые становятся постоянно не собираемым мусором GC. Восстановил Py3. 1 подход использования прокси weakref так что ссылка циклы никогда не создаются во-первых.