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

Question

我有一个基本上相当于嵌套字典的数据结构。假设它是这样的：

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

Answer 1

What is the best way to implement nested dictionaries in Python?

这是个坏主意，别这么做。取而代之的是，使用一个常规字典并在apropos中使用dict.setdefault，这样当在正常使用中缺少键时，您就得到了期望的KeyError。如果你坚持要做出这种行为，下面是如何射中自己的脚：

在dict子类上实现__missing__，以设置并返回新实例。

自Python 2.5以来，这种方法就一直可用，(and documented)，而且（对我来说特别有价值）它的打印效果很好，就像普通的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]在赋值的左边，所以这里没有递归。）

假设你有一些数据：

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上额外调用getter，不幸的是，我们无法在设置时返回它。）

注意，这些语义与最高投票率的答案相同，但在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

尽管询问者认为这不干净，但我发现它比我自己更可取。

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)

自动激活的默认指令

这是一个外观整洁的实现，在不检查数据的脚本中使用与实现__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笔记本，也许）那么性能并不重要-在这种情况下，我会与生动的输出可读性。与autovivation对象（使用__getitem__而不是__missing__）相比，autovivation对象（这个目的）它是非常优越的。

结论

在子类dict上实现__missing__以设置并返回新实例比其他方法稍微困难一些，但有以下好处

• 易于实例化
• 方便的数据填充
• 轻松查看数据

而且，由于它比修改__getitem__更简单、性能更好，因此应该优先使用该方法。

然而，它也有缺点：

• 错误的查找将无声地失败。
• 错误的查找将保留在字典中。

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

Answer 2

就因为我没见过这么小的一个，这是一个你喜欢的嵌套，没有汗水：

# yo dawg, i heard you liked dicts                                                                      
def yodict():
    return defaultdict(yodict)

Answer 3

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