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 层 key ”，或“在特殊位置应用 if 条件”。因此，我想提出一个简单的问题:在 Python 中对双嵌套字典的值求和的最佳方法是什么？

Answer 1

总的来说，我认为您当前的方法是好的。我的建议是尽可能多地消除字典查找。一起迭代键和值应该和迭代键一样快，所以您不妨将它们组合起来。如果您这样做，则不需要最后调用 d[w1][w2][w3]，也不需要临时 key 查找。所以像这样:

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 类型。我会继续寻找!