如何最佳实现嵌套字典？

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

- YGA

Answer 1

如何在Python中实现嵌套字典？

这是一个不好的思路，不要这样做。相反，使用普通字典，并在适当时使用dict.setdefault，这样在正常使用下丢失键时您将获得预期的KeyError。如果您坚持要获取此行为，则可以这样做：

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

自Python 2.5以来，这种方法已经可用（并记录），并且非常有价值，因为它可以像普通字典一样漂亮地打印，而不是autovivified 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

(Note self[key] is on the left-hand side of assignment, so there's no recursion here.)

并且假设你有一些数据：

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类的实例。（返回值赋值很有用，因为它避免了我们在字典上额外调用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

使用演示

以下只是一个例子，展示了如何轻松使用此字典来创建一个嵌套的字典结构。这可以快速创建一个树形结构，您可以按照需要将其深度扩展。

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

这个输出结果非常不优雅，而且结果很难读懂。通常的解决方法是递归地将其转换回字典以进行手动检查。这个复杂的解决方案留给读者作为练习。

性能

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

>>> 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__），它要优秀得多。

结论

在子类化的dict上实现__missing__以设置和返回新实例比其他方法略微困难，但具有以下优点：

易于实例化

易于填充数据

易于查看数据

由于它比修改__getitem__方法更简单且更高效，因此应优先考虑使用该方法。

然而，它也有缺点：

坏的查找将会默默失败。

错误的查找结果将会保留在字典中。

因此，我个人更喜欢使用setdefault而不是其他解决方案，并且在我需要这种行为的每种情况下都使用它。

- Russia Must Remove Putin

---

非常好的回答！有没有办法为 Vividict 指定有限深度和叶子类型？例如，对于一个可以用 d['primary']['secondary']['tertiary'].append(element) 填充的字典的字典的字典的列表，可以指定 3 和 list。我可以为每个深度定义 3 种不同的类，但我希望找到更清晰的解决方案。 - Eric Duminil

@EricDuminil d['primary']['secondary'].setdefault('tertiary', []).append('element') - ?? 感谢夸奖，但让我诚实地说 - 我从来没有使用过__missing__ - 我总是使用setdefault。我应该更新我的结论/介绍... - Russia Must Remove Putin

@AaronHall 正确的行为是，如果需要，代码应该创建一个字典。在这种情况下，通过覆盖先前分配的值来实现。 - nehem

@AaronHall，你能帮我理解“不良查找将保留在字典中”是什么意思吗？因为我正在考虑使用这个解决方案。非常感谢。谢谢。 - nehem

@AaronHall 这个问题在嵌套超过两层深度时会导致 setdefault 失败。看起来 Python 中没有任何结构可以像描述的那样提供真正的活化功能。我不得不采用两种声明方法，一种是 get_nested，另一种是 set_nested，它们接受字典引用和嵌套属性列表。 - nehem

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

print a

输出：

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

- nosklo

---

有人在转向Python 3.x时遇到过这个问题吗？https://stackoverflow.com/questions/54622935/problem-loading-autovivification-file-when-moving-from-python-2-7-to-3-6-keyerr - jason

@jason pickle 在不同版本的 Python 之间表现很差。避免使用它来存储您想要保留的数据。仅将其用于缓存和可以随意转储和重新生成的内容。而不是作为长期存储或序列化方法。 - nosklo

你用什么来存储这些对象？我的自动引用对象只包含pandas数据框和字符串。 - jason

@jason 根据数据的不同，我喜欢使用JSON、csv文件，甚至是sqlite数据库来存储它。 - nosklo

Answer 3

只是因为我没有见过这么小的字典，这里有一个可以嵌套到你想要的程度的字典，非常简单：

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

- paint can

---

实际上你只需要 yodict = lambda: defaultdict(yodict)。 - martineau

被接受的版本是 dict 的子类，所以为了完全等价，我们需要让 x = Vdict(a=1, b=2) 起作用。 - wberry

@wberry：无论接受的答案中包含什么，作为dict的子类并不是由OP所要求的要求之一，他只是询问了实现它们的“最佳方法”--而且，在Python中这并不重要。 - martineau

Answer 4

你可以创建一个YAML文件并使用PyYaml读取它。

第一步：创建一个名为“employment.yml”的YAML文件：

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(...)。

- Pete

---

YAML 绝对是我输入大量深度嵌套数据（以及配置文件、数据库模拟等）的首选。如果 OP 不想让多余的文件困扰，只需在某个文件中使用常规 Python 字符串，并使用 YAML 解析该字符串即可。 - klozovin

创建YAML字符串的想法很好：这比反复使用“tempfile”模块要干净得多。 - Pete

Answer 5

由于您拥有星型模式的设计，您可能希望将其更像关系表而不是字典进行结构化。

import collections

class Jobs( object ):
    def __init__( self, state, county, title, count ):
        self.state= state
        self.count= county
        self.title= title
        self.count= count

facts = [
    Jobs( 'new jersey', 'mercer county', 'plumbers', 3 ),
    ...

def groupBy( facts, name ):
    total= collections.defaultdict( int )
    for f in facts:
        key= getattr( f, name )
        total[key] += f.count

这种方法可以在不需要SQL开销的情况下创建类似数据仓库的设计。

- S.Lott

Answer 6

如果嵌套级别较小，我会使用collections.defaultdict来实现：

from collections import defaultdict

def nested_dict_factory(): 
  return defaultdict(int)
def nested_dict_factory2(): 
  return defaultdict(nested_dict_factory)
db = defaultdict(nested_dict_factory2)

db['new jersey']['mercer county']['plumbers'] = 3
db['new jersey']['mercer county']['programmers'] = 81

像这样使用defaultdict可以避免很多混乱的setdefault()、get()等操作。

- user26294

---

+1：defaultdict 是我所有时间里最喜欢的 Python 新增功能之一。不再需要使用 .setdefault() 了！ - John Fouhy

Answer 7

这是一个返回任意深度嵌套字典的函数：

from collections import defaultdict
def make_dict():
    return defaultdict(make_dict)

像这样使用：

d=defaultdict(make_dict)
d["food"]["meat"]="beef"
d["food"]["veggie"]="corn"
d["food"]["sweets"]="ice cream"
d["animal"]["pet"]["dog"]="collie"
d["animal"]["pet"]["cat"]="tabby"
d["animal"]["farm animal"]="chicken"

可以使用类似以下的方法来遍历所有内容：

def iter_all(d,depth=1):
    for k,v in d.iteritems():
        print "-"*depth,k
        if type(v) is defaultdict:
            iter_all(v,depth+1)
        else:
            print "-"*(depth+1),v

iter_all(d)

这会打印出：

- food
-- sweets
--- ice cream
-- meat
--- beef
-- veggie
--- corn
- animal
-- pet
--- dog
---- labrador
--- cat
---- tabby
-- farm animal
--- chicken

您最终可能希望使新项目无法添加到字典中。将所有这些defaultdict递归地转换为普通的dict很容易。

def dictify(d):
    for k,v in d.iteritems():
        if isinstance(v,defaultdict):
            d[k] = dictify(v)
    return dict(d)

- JnBrymn

Answer 8

我认为setdefault非常有用；它会检查键是否存在，如果不存在则添加：

d = {}
d.setdefault('new jersey', {}).setdefault('mercer county', {})['plumbers'] = 3

setdefault 总是返回相关的键，因此实际上您是在原地更新 'd' 的值。

当涉及到迭代时，如果Python中不存在生成器，我相信您可以轻松编写一个：

def iterateStates(d):
    # Let's count up the total number of "plumbers" / "dentists" / etc.
    # across all counties and states
    job_totals = {}

    # I guess this is the annoying nested stuff you were talking about?
    for (state, counties) in d.iteritems():
        for (county, jobs) in counties.iteritems():
            for (job, num) in jobs.iteritems():
                # If job isn't already in job_totals, default it to zero
                job_totals[job] = job_totals.get(job, 0) + num

    # Now return an iterator of (job, number) tuples
    return job_totals.iteritems()

# Display all jobs
for (job, num) in iterateStates(d):
    print "There are %d %s in total" % (job, num)

- andygeers

---

我喜欢这个解决方案，但是当我尝试使用以下代码时：count.setdefault(a, {}).setdefault(b, {}).setdefault(c, 0) += 1，会出现“增强赋值的表达式非法”的错误提示。 - dfrankow

Answer 9

正如其他人建议的那样，关系型数据库可能更适合您。您可以使用内存中的sqlite3数据库作为数据结构来创建表并查询它们。

import sqlite3

c = sqlite3.Connection(':memory:')
c.execute('CREATE TABLE jobs (state, county, title, count)')

c.executemany('insert into jobs values (?, ?, ?, ?)', [
    ('New Jersey', 'Mercer County',    'Programmers', 81),
    ('New Jersey', 'Mercer County',    'Plumbers',     3),
    ('New Jersey', 'Middlesex County', 'Programmers', 81),
    ('New Jersey', 'Middlesex County', 'Salesmen',    62),
    ('New York',   'Queens County',    'Salesmen',    36),
    ('New York',   'Queens County',    'Plumbers',     9),
])

# some example queries
print list(c.execute('SELECT * FROM jobs WHERE county = "Queens County"'))
print list(c.execute('SELECT SUM(count) FROM jobs WHERE title = "Programmers"'))

这只是一个简单的例子。您可以为州、县和职位定义单独的表格。

- Roberto Bonvallet

Answer 10

您可以使用Addict：https://github.com/mewwts/addict

>>> from addict import Dict
>>> my_new_shiny_dict = Dict()
>>> my_new_shiny_dict.a.b.c.d.e = 2
>>> my_new_shiny_dict
{'a': {'b': {'c': {'d': {'e': 2}}}}}

- JnBrymn