python - 实现嵌套字典的最佳方法是什么？

我有一个实质上相当于嵌套字典的数据结构。假设它看起来像这样:

{'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()。

最佳答案

这是一个坏主意，请不要这样做。相反，请使用常规词典，并在适当的地方使用dict.setdefault，因此，在正常使用情况下丢失键时，您将获得预期的KeyError。如果您坚持要采取这种行为，请按照以下步骤射击自己:
在__missing__子类上实现dict以设置和返回新实例。
从Python 2.5开始，这种方法就已经可以使用(and documented)了，(对我来说特别有值(value))，它的打印效果与普通字典一样，而不是自动生成的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]在分配的左侧，因此此处没有递归。)
并说您有一些数据:

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}}}

批评
对这种类型的容器的批评是，如果用户拼错了 key ，我们的代码可能会无声地失败:

>>> 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上调用getter，不幸的是，我们无法在设置它时返回它。)
请注意，这些与最受支持的答案具有相同的语义，但是代码行的一半-nosklo的实现:

用法示范
下面只是一个示例，说明如何轻松地使用此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在循环中使用时效果很好，并且您不知道要为 key 得到什么，但是重复使用变得非常繁重，而且我认为没有人愿意遵守以下规定:

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

此输出非常微不足道，并且结果非常不可读。通常给出的解决方案是递归转换回字典以进行手动检查。这个非平凡的解决方案留给读者练习。
表现
最后，让我们看一下性能。我要减去实例化的成本。

>>> 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__)相比，AutoVivification对象要优越得多。
结论
在子类的__missing__上实现dict以设置和返回新实例比替代方法稍微困难一些，但具有以下优点:

简单实例化

简单数据填充

轻松查看数据

并且由于它比修改__getitem__更为简单，并且性能更高，因此应优先于该方法。
但是，它有缺点:

错误的查找将静默失败。

错误的查询将保留在词典中。

因此，与其他解决方案相比，我个人更喜欢setdefault，并且在每种情况下都需要这种行为。