Вопрос-Ответ

What is the best way to implement nested dictionaries?

Какой лучший способ реализовать вложенные словари?

У меня есть структура данных, которая по сути представляет собой вложенный словарь. Допустим, это выглядит так:

{'new jersey': {'mercer county': {'plumbers': 3,
'programmers': 81},
'middlesex county': {'programmers': 81,
'salesmen': 62}},
'new york': {'queens county': {'plumbers': 9,
'salesmen': 36}}}

Теперь поддерживать и создавать это довольно болезненно; каждый раз, когда у меня появляется новый штат / округ / профессия, мне приходится создавать словари нижнего уровня с помощью неприятных блоков try / catch. Более того, мне приходится создавать раздражающие вложенные итераторы, если я хочу просмотреть все значения.

Я также мог бы использовать кортежи в качестве ключей, например:

{('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}

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

В принципе, иногда мне хочется думать о вложенном словаре как о плоском словаре, а иногда мне действительно хочется думать о нем как о сложной иерархии. Я мог бы обернуть все это в класс, но, похоже, кто-то, возможно, уже сделал это. В качестве альтернативы, похоже, для этого могут быть какие-то действительно элегантные синтаксические конструкции.

Как я мог бы сделать это лучше?

Дополнение: я в курсе, setdefault() но на самом деле это не способствует чистому синтаксису. Кроме того, каждый создаваемый вами вложенный словарь по-прежнему должен быть setdefault() настроен вручную.

Переведено автоматически
Ответ 1

Какой лучший способ реализовать вложенные словари в Python?


Это плохая идея, не делайте этого. Вместо этого используйте обычный словарь и используйте dict.setdefault где следует, поэтому, когда ключи отсутствуют при обычном использовании, вы получаете ожидаемое KeyError. Если вы настаиваете на таком поведении, вот как прострелить себе ногу:

Реализуйте __missing__ в dict подклассе, чтобы установить и вернуть новый экземпляр.

Этот подход доступен (и задокументирован) начиная с Python 2.5, и (что особенно ценно для меня) он печатается точно так же, как обычный dict, вместо уродливой печати автоматически активированного defaultdict:

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] находится в левой части assignment , поэтому рекурсии здесь нет.)

и скажите, что у вас есть какие-то данные:

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 всякий раз, когда ключ доступен, но отсутствует. (Возврат присвоения значения полезен, потому что это позволяет избежать дополнительного вызова средства получения в 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

Демонстрация использования

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

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)

Но если вам нужно проверить свои данные, результаты автоматически обновленного defaultdict, заполненного данными таким же образом, выглядят следующим образом:

>>> 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>, {})})})

Этот вывод довольно неэлегантен, и результаты совершенно нечитабельны. Обычно предлагается рекурсивное преобразование обратно в dict для проверки вручную. Это нетривиальное решение оставлено в качестве упражнения для читателя.

Производительность

Наконец, давайте посмотрим на производительность. Я вычитаю затраты на создание экземпляра.

>>> 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 для удобства чтения выходных данных. По сравнению с объектом автозаполнения (который использует __getitem__ вместо __missing__, который был создан для этой цели) он намного лучше.

Заключение

Реализация __missing__ на подклассе dict для установки и возврата нового экземпляра немного сложнее, чем альтернативные варианты, но имеет преимущества


  • простое создание экземпляра

  • простое заполнение данных

  • удобный просмотр данных

и поскольку он менее сложный и более производительный, чем модификация __getitem__, ему следует отдать предпочтение перед этим методом.

Тем не менее, у него есть недостатки:


  • Неудачный поиск завершится безрезультатно.

  • Неверный поиск останется в словаре.

Таким образом, я лично предпочитаю setdefault другим решениям и использую в каждой ситуации, когда мне требовалось подобное поведение.

Ответ 2
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

Тестирование:

a = AutoVivification()

a[1][2][3] = 4
a[1][3][3] = 5
a[1][2]['test'] = 6

print a

Вывод:

{1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}
Ответ 3

Просто потому, что я не видел такого маленького, вот dict, который может быть настолько вложенным, насколько вам нравится, не парьтесь:

# yo dawg, i heard you liked dicts                                                                      
def yodict():
return defaultdict(yodict)
Ответ 4

Вы могли бы создать файл YAML и прочитать его с помощью PyYAML.

Шаг 1: Создайте файл YAML "employment.yml":

new jersey:
mercer county:
pumbers: 3
programmers: 81
middlesex county:
salesmen: 62
programmers: 81
new york:
queens county:
plumbers: 9
salesmen: 36

Шаг 2: Прочитайте это на Python

import yaml
file_handle = open("employment.yml")
my_shnazzy_dictionary = yaml.safe_load(file_handle)
file_handle.close()

и теперь у my_shnazzy_dictionary есть все ваши значения. Если вам нужно было сделать это на лету, вы можете создать YAML в виде строки и передать ее в yaml.safe_load(...).

python dictionary