Каков наилучший способ реализации вложенных словарей в Python?
Реализация __missing__ в подклассе dict для установки и возврата нового экземпляра.
Этот подход был доступен (и задокументирован) начиная с Python 2.5, и (что особенно ценно для меня) он довольно печатает, как обычный dict , вместо уродливой печати автоколонна по умолчанию:
class Vividict(dict):
def __missing__(self, key):
value = self[key] = type(self)() # retain local pointer to value
return value # faster to return than dict lookup
(Примечание self[key] находится слева от назначения, поэтому здесь нет рекурсии.)
и скажем, у вас есть некоторые данные:
data = {('new jersey', 'mercer county', 'plumbers'): 3,
('new jersey', 'mercer county', 'programmers'): 81,
('new jersey', 'middlesex county', 'programmers'): 81,
('new jersey', 'middlesex county', 'salesmen'): 62,
('new york', 'queens county', 'plumbers'): 9,
('new york', 'queens county', 'salesmen'): 36}
Вот наш код использования:
vividict = Vividict()
for (state, county, occupation), number in data.items():
vividict[state][county][occupation] = number
А сейчас:
>>> import pprint
>>> pprint.pprint(vividict, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
'programmers': 81},
'middlesex county': {'programmers': 81,
'salesmen': 62}},
'new york': {'queens county': {'plumbers': 9,
'salesmen': 36}}}
Критика
Критика этого типа контейнера заключается в том, что если пользователь неправильно введет ключ, наш код может завершиться сбоем:
>>> vividict['new york']['queens counyt']
{}
И, кроме того, теперь в наших данных будет округ с ошибкой:
>>> pprint.pprint(vividict, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
'programmers': 81},
'middlesex county': {'programmers': 81,
'salesmen': 62}},
'new york': {'queens county': {'plumbers': 9,
'salesmen': 36},
'queens counyt': {}}}
Пояснение:
Мы просто предоставляем другой вложенный экземпляр нашего класса Vividict всякий раз, когда к ключу обращаются, но пропускают. (Возвращение присваивания значения полезно, потому что оно позволяет избежать дополнительного вызова метода get для dict, и, к сожалению, мы не можем вернуть его, когда оно устанавливается.)
Обратите внимание, что это та же семантика, что и у ответа с наибольшим количеством голосов, но в половине строк кода - реализация nosklo:
class AutoVivification(dict):
"""Implementation of perl's autovivification feature."""
def __getitem__(self, item):
try:
return dict.__getitem__(self, item)
except KeyError:
value = self[item] = type(self)()
return value
Демонстрация использования
Ниже приведен лишь пример того, как этот дикт можно легко использовать для создания вложенной структуры диктов на лету. Это может быстро создать иерархическую древовидную структуру настолько глубоко, насколько вам захочется.
import pprint
class Vividict(dict):
def __missing__(self, key):
value = self[key] = type(self)()
return value
d = Vividict()
d['foo']['bar']
d['foo']['baz']
d['fizz']['buzz']
d['primary']['secondary']['tertiary']['quaternary']
pprint.pprint(d)
Какие выходы:
{'fizz': {'buzz': {}},
'foo': {'bar': {}, 'baz': {}},
'primary': {'secondary': {'tertiary': {'quaternary': {}}}}}
И как показывает последняя строка, она довольно красиво печатается и для ручного осмотра. Но если вы хотите визуально проверить свои данные, реализация __missing__ для установки нового экземпляра его класса для ключа и возврата его является гораздо лучшим решением.
Другие альтернативы для контраста:
dict.setdefault
Хотя спрашивающий считает, что это не чисто, я считаю, что это предпочтительнее, чем Vividict.
d = {} # or dict()
for (state, county, occupation), number in data.items():
d.setdefault(state, {}).setdefault(county, {})[occupation] = number
и сейчас:
>>> pprint.pprint(d, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
'programmers': 81},
'middlesex county': {'programmers': 81,
'salesmen': 62}},
'new york': {'queens county': {'plumbers': 9,
'salesmen': 36}}}
Неправильный орфографический шум будет сбоить и не загромождать наши данные неверной информацией:
>>> d['new york']['queens counyt']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'queens counyt'
Кроме того, я думаю, что setdefault прекрасно работает, когда используется в циклах, и вы не знаете, что вы получите за ключи, но повторное использование становится довольно обременительным, и я не думаю, что кто-то захочет поддерживать следующее:
d = dict()
d.setdefault('foo', {}).setdefault('bar', {})
d.setdefault('foo', {}).setdefault('baz', {})
d.setdefault('fizz', {}).setdefault('buzz', {})
d.setdefault('primary', {}).setdefault('secondary', {}).setdefault('tertiary', {}).setdefault('quaternary', {})
Другая критика заключается в том, что setdefault требует нового экземпляра, независимо от того, используется он или нет. Тем не менее, Python (или, по крайней мере, CPython) достаточно умен для обработки неиспользуемых и не связанных ссылок на новые экземпляры, например, он повторно использует местоположение в памяти:
>>> id({}), id({}), id({})
(523575344, 523575344, 523575344)
Авто-оживленный defaultdict
Это аккуратная реализация, и использование в скрипте, на котором вы не проверяете данные, было бы так же полезно, как и реализация __missing__:
from collections import defaultdict
def vivdict():
return defaultdict(vivdict)
Но если вам нужно проверить ваши данные, результаты автоматически оживленного дефолта по умолчанию, заполненного данными таким же образом, будут выглядеть так:
>>> d = vivdict(); d['foo']['bar']; d['foo']['baz']; d['fizz']['buzz']; d['primary']['secondary']['tertiary']['quaternary']; import pprint;
>>> pprint.pprint(d)
defaultdict(<function vivdict at 0x17B01870>, {'foo': defaultdict(<function vivdict
at 0x17B01870>, {'baz': defaultdict(<function vivdict at 0x17B01870>, {}), 'bar':
defaultdict(<function vivdict at 0x17B01870>, {})}), 'primary': defaultdict(<function
vivdict at 0x17B01870>, {'secondary': defaultdict(<function vivdict at 0x17B01870>,
{'tertiary': defaultdict(<function vivdict at 0x17B01870>, {'quaternary': defaultdict(
<function vivdict at 0x17B01870>, {})})})}), 'fizz': defaultdict(<function vivdict at
0x17B01870>, {'buzz': defaultdict(<function vivdict at 0x17B01870>, {})})})
Этот вывод довольно не элегантный, а результаты совершенно нечитаемы. Обычно решение состоит в том, чтобы рекурсивно преобразовать обратно в диктовку для ручной проверки. Это нетривиальное решение оставлено читателю в качестве упражнения.
Performance
Наконец, давайте посмотрим на производительность. Я вычитаю затраты на инстанцирование.
>>> import timeit
>>> min(timeit.repeat(lambda: {}.setdefault('foo', {}))) - min(timeit.repeat(lambda: {}))
0.13612580299377441
>>> min(timeit.repeat(lambda: vivdict()['foo'])) - min(timeit.repeat(lambda: vivdict()))
0.2936999797821045
>>> min(timeit.repeat(lambda: Vividict()['foo'])) - min(timeit.repeat(lambda: Vividict()))
0.5354437828063965
>>> min(timeit.repeat(lambda: AutoVivification()['foo'])) - min(timeit.repeat(lambda: AutoVivification()))
2.138362169265747
По производительности dict.setdefault работает лучше всего. Я настоятельно рекомендую его для производственного кода в тех случаях, когда вам важна скорость выполнения.
Если вам нужно это для интерактивного использования (возможно, в записной книжке IPython), тогда производительность не имеет значения - в этом случае я бы выбрал Vividict для удобочитаемости вывода. По сравнению с объектом AutoVivification (который использует __getitem__ вместо __missing__, который был создан для этой цели) он намного превосходит.
Заключение * +1101 * Реализация __missing__ на подклассе dict для установки и возврата нового экземпляра немного сложнее, чем альтернативы, но имеет преимущества
легкая реализация
легкая совокупность данных
простой просмотр данных
и поскольку он менее сложен и более производителен, чем изменение __getitem__, его следует отдать предпочтению этому методу.
Тем не менее, у него есть недостатки:
Плохой поиск потерпит молчание.
Плохой поиск останется в словаре.
Таким образом, я лично предпочитаю setdefault другим решениям, и имею в каждой ситуации, где мне нужно такое поведение.