Python：求三层字典的值之和

Question

给定一个三层嵌套的字典，最快的求和方法是什么？这是我的当前方案：

from collections import defaultdict

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ]

def sum_three_deep_dict_values(dicts):
    '''Read in two dicts and return a dictionary that contains their outer-joined keys and value sums'''
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
    for d in dicts:
        for w1, val_dict in d.iteritems():          
            for w2 in val_dict.iterkeys():              
                for w3 in val_dict[w2].iterkeys():
                    combined[w1][w2][w3] += d[w1][w2][w3]
    return combined

print sum_three_deep_dict_values(dicts)

这里期望的输出是{'a': {'b': {'c': 5, 'e': 3}}}。目标是将两个字典具有相同键的值相加（例如这里的d[a][b][c]），并在输出字典中包含另一个字典中的其余键值对。

在SO上有许多关于如何对嵌套字典的值求和的问题，但是昨晚我阅读它们时，每一个都涉及一些奇怪的特殊情况或参数，比如“组合/忽略第n层键”，或者“在特殊位置应用if条件”。因此，我想提出一个简单的问题：Python中对双重嵌套字典的值求和的最佳方法是什么？

- duhaime

---

第一层和第二层可以有多个键吗？ - Julien Spronck

哦，是的。我的实际密钥大小分别为第一层100,000; 第二层1,000,000; 第三层100,000,000。 - duhaime

预期输出是一个字典，有两层深度，与原始字典具有相同的键，但最后一个值是第三层中值的总和。 - Julien Spronck

预期的输出是{'a': {'b': {'c': 5, 'e': 3}}}吗？ - Matt

是的，@Matt，抱歉之前我没有说。我更新了问题以讨论预期输出。Julien，预期输出字典有三层键，就像输入字典一样。最后一个值应该被求和。 - duhaime

好的...另外，你当前的方式有什么问题吗？ - Julien Spronck

Answer 1

我认为你目前的方法总体上是不错的。我的建议是尽可能减少字典查找次数。同时遍历键和值应该与只遍历键一样快，因此你可以将它们合并起来。如果这样做，最终调用d [w1] [w2] [w3]和中间的键查找都是不必要的。因此可以像这样：

def sum_three_deep_dict_values(dicts):
    '''Read in two dicts and return a dictionary that contains 
       their outer-joined keys and value sums'''
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
    for layer0 in dicts:
        for k1, layer1 in layer0.iteritems():
            for k2, layer2 in layer1.iteritems():
                for k3, count in layer2.iteritems():
                    combined[k1][k2][k3] += count
    return combined

我稍微改变了你的命名方案。

如果你在测试上述内容后仍然担心速度问题，可能需要考虑其他数据结构或第三方库。但在此之前，请尝试使用PyPy——我发现它通常可以将普通for循环的速度提高至少4倍。

此外，请对比一下你的原始代码进行测试。我认为我的推理是正确的，但还有些推测性。我也很想听听别人的建议。在你工作的规模下，这可能是一个挑战！（出于好奇，你用当前的代码需要多长时间？）

更新：我测试过了，确实更快，但只是略微快了一点：

>>> %timeit sum_three_deep_original(dicts)
1000 loops, best of 3: 1.38 ms per loop
>>> %timeit sum_three_deep_edited(dicts)
1000 loops, best of 3: 1.26 ms per loop

我猜您需要提高应用程序的速度。我曾试用了PyPy，并通过cython编译它（但没有进行任何修改或类型注释）。结果，PyPy可提升66%的速度。再次使用纯Python（这次稍微更改了一些参数）：

:~ $ python -c 'from tdsum import test; test()'
1.63905096054

使用cython编译:

:~ $ python -c 'from tdsum import test; test()'
1.224848032

使用PyPy：

:~ $ pypy -c 'from tdsum import test; test()'
0.427165031433

我希望真正的Cython版本使用自定义数据结构，能够显著优于PyPy。问题在于，您不能使用 dict 并仍然获得所需的迭代加速，因为Cython必须处理Python对象开销。因此，您需要实现自己的哈希表！我经常想知道为什么Cython没有解决这个问题的方案；也许有一个可用的 numpy 类型。我会继续寻找！

- senderle

---

不错的解决方案和建议。 - erip

Answer 2

这里有一个解决方案，使用压平函数和展开函数，适用于任意深度嵌套问题。该解决方案适用于您的输入，但没有进行过更多测试：

from collections import Counter

def flatten(d, parent=None):
    for k, v in d.items():
        keys = (k,) if parent is None else parent + (k,)
        if isinstance(v, dict):
            yield from flatten(v, keys)
        else:
            yield keys, v

def puffup(c):
    top = {}
    for k, v in c.items():
        current = top # reset walk
        for ki in k[:-1]:
            if ki not in current:
                current[ki] = {}
        current[k[-1]] = v
    return top

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ]
c = Counter()
for d in dicts:
    c += dict(flatten(d))
print(puffup(c))
# {'a': {'b': {'c': 5, 'e': 3}}}

我刚看到你在寻找最快的解决方案。虽然更加灵活，但这个方法比上面的答案慢大约2.5倍，而且输入参数也没怎么调整。

- RodericDay