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中对双嵌套字典的值进行求和的最佳方法是什么？

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 ——我发现它通常可以使普通循环至少获得 4 倍的加速for。

另外，请针对您的原始代码进行测试。我认为我上面的推理是成立的，但仍然有点推测。我也很好奇其他人的建议。就您目前的工作规模而言，这可能是一个挑战！（出于好奇，使用当前代码需要多长时间？）

更新：我测试了这个，它确实更快，尽管只有一点点：

>>> %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。问题是你不能使用dicts 并且仍然获得你想要的迭代加速，因为 cython 必须处理 Python 对象开销。所以你必须实现你自己的哈希表！

我经常想知道为什么 cython 没有提供这个问题的解决方案；也许有一种numpy可用的类型。我会继续寻找！