python - 来自元组的任意嵌套字典

Question

给定一个以元组作为键(以及数字/标量作为值)的字典，转换为嵌套字典的 Pythonic 方法是什么？问题在于，从输入到输入，元组的长度是任意的。

下面，d1、d2 和 d3 演示了递增的嵌套:

from itertools import product

d1 = dict(zip(product('AB', [0, 1]), range(2*2)))
d2 = dict(zip(product('AB', [0, 1], [True, False]), range(2*2*2)))
d3 = dict(zip(product('CD', [0, 1], [True, False], 'AB'), range(2*2*2*2)))

它们生成的嵌套版本将是:

# For d1
{'A': {0: 0, 1: 1}, 'B': {0: 2, 1: 3}}

# For d2
{'A': {0: {True: 0, False: 1}, 1: {True: 2, False: 3}},
 'B': {0: {True: 4, False: 5}, 1: {True: 6, False: 7}}}

# Beginning of result for d3
{
'C': {
    0: {
        True: {
            'A': 0
            'B': 1
        },
        False: {
            'A': 2,
            'B': 3
        },
    1: # ...

---

我的尝试:我喜欢这个初始化空数据结构的技巧，它在许多其他 SO 答案中给出:

from collections import defaultdict

def nested_dict():
    return defaultdict(nested_dict)

但是我很难实现这个，因为级别的数量是不确定的。我可以使用类似的东西:

def nest(d: dict) -> dict:
    res = nested_dict()
    for (i, j, k), v in d.items():
        res[i][j][k] = v
    return res

但这只对d2有效，因为它的键有3个级别(i，j，k)以上。

这是我尝试解决这个问题的方法，但我猜还有更简单的方法。

def set_arbitrary_nest(keys, value):
    """
    >>> keys = 1, 2, 3
    >>> value = 5
    result --> {1: {2: {3: 5}}}
    """

    it = iter(keys)
    last = next(it)
    res = {last: {}}
    lvl = res
    while True:
        try:
            k = next(it)
            lvl = lvl[last]
            lvl[k] = {}
            last = k
        except StopIteration:
            lvl[k] = value
            return res

>>> set_arbitrary_nest([1, 2, 3], 5)
{1: {2: {3: 5}}}

Answer 1

只需遍历每个键，并使用键的最后一个元素以外的所有元素来添加字典。保留对如此设置的最后一个字典的引用，然后使用键元组中的最后一个元素在输出字典中实际设置一个键值对:

def nest(d: dict) -> dict:
    result = {}
    for key, value in d.items():
        target = result
        for k in key[:-1]:  # traverse all keys but the last
            target = target.setdefault(k, {})
        target[key[-1]] = value
    return result

你可以使用 functools.reduce()处理字典遍历工作:

from functools import reduce

def nest(d: dict) -> dict:
    result = {}
    traverse = lambda r, k: r.setdefault(k, {})
    for key, value in d.items():
        reduce(traverse, key[:-1], result)[key[-1]] = value
    return result

我使用了 dict.setdefault() 而不是自动激活 defaultdict(nested_dict) 选项，因为这会生成一个不会进一步隐式添加键的常规字典当它们还不存在时。

演示:

>>> from pprint import pprint
>>> pprint(nest(d1))
{'A': {0: 0, 1: 1}, 'B': {0: 2, 1: 3}}
>>> pprint(nest(d2))
{'A': {0: {False: 1, True: 0}, 1: {False: 3, True: 2}},
 'B': {0: {False: 5, True: 4}, 1: {False: 7, True: 6}}}
>>> pprint(nest(d3))
{'C': {0: {False: {'A': 2, 'B': 3}, True: {'A': 0, 'B': 1}},
       1: {False: {'A': 6, 'B': 7}, True: {'A': 4, 'B': 5}}},
 'D': {0: {False: {'A': 10, 'B': 11}, True: {'A': 8, 'B': 9}},
       1: {False: {'A': 14, 'B': 15}, True: {'A': 12, 'B': 13}}}}

请注意，上述解决方案是一个干净的 O(N) 循环(N 是输入字典的长度)，而 Ajax1234 提出的 groupby 解决方案必须对输入进行排序才能工作，使其成为 O(NlogN) 解决方案。这意味着对于具有 1000 个元素的字典，groupby() 将需要 10.000 步来生成输出，而 O(N) 线性循环仅需要 1000 步。对于一百万个 key ，这会增加到 2000 万步，等等。

此外，Python 中的递归...很慢，因为 Python 无法将此类解决方案优化为迭代方法。函数调用相对昂贵，因此使用递归会带来显着的性能成本，因为您会大大增加函数调用的数量并扩展帧堆栈操作。

计时赛表明这有多重要；使用您的示例 d3 和 100k 运行，我们很容易看到 5 倍的速度差异:

>>> from timeit import timeit
>>> timeit('n(d)', 'from __main__ import create_nested_dict as n, d3; d=d3.items()', number=100_000)
8.210276518017054
>>> timeit('n(d)', 'from __main__ import nest as n, d3 as d', number=100_000)
1.6089267160277814