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

Question

实现嵌套字典的最佳方法是什么？我有一个数据结构，实质上相当于一个嵌套字典。假设它看起来是这样的：{'new jersey': {'mercer county': {'plumbers': 3,                                   'programmers': 81},                 'middlesex county': {'programmers': 81,                                      'salesmen': 62}},  'new york': {'queens county': {'plumbers': 9,                                 'salesmen': 36}}}现在，维护和创建它是非常痛苦的；每次我有一个新的州/县/专业时，我都必须通过讨厌的尝试/捕捉块创建底层字典。此外，如果我想遍历所有的值，我必须创建恼人的嵌套迭代器。我还可以使用元组作为键，如下所示：{('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

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

实施__missing__在.上dict类来设置和返回一个新实例。

这种方法是可用的。(并记录在案)自从Python2.5之后，和(对我来说特别有价值)很漂亮的指纹就像个普通的白痴，而不是丑陋的打印一个自动形象的默认：

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无论何时访问密钥，但缺少密钥。(返回值赋值很有用，因为它避免了我们在DECT上额外调用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 pprintclass 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)

一个自动生动的默认设置

这是一个整洁的实现，在没有检查数据的脚本中使用与实现相同的功能__missing__:

from collections import defaultdictdef 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>, {})}), 'pr
mary': 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>, {})})})

这个输出是相当不雅致的，结果是非常不可读的。通常给出的解决方案是递归地将其转换为DECT，以便进行手动检查。这个非平凡的解决方案是留给读者的练习。

性能

最后，让我们看看性能。我正在减去实例化的成本。

>>> 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其他的解决方案，在我需要这种行为的每一种情况下都有。

Answer 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] = 4a[1][3][3] = 5a[1][2]['test'] = 6print a

产出：

{1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}

Answer 3

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

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