Diccionario arbitrariamente nested de tuplas

Dado un diccionario con tuplas como claves (y números / escalares como valores), ¿qué es una forma Pythonic para convertir a un diccionario nested? El problema es que, de entrada a entrada, las tuplas son de una longitud arbitraria.

A continuación, d1 , d2 y d3 demuestran una creciente anidación:

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

Y sus versiones anidadas resultantes serían:

 # 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: # ... 

Mis bashs: Me gusta este truco para inicializar una estructura de datos vacía, que se da en una serie de otras respuestas de SO:

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

Pero estoy teniendo problemas para implementar esto porque el número de niveles es incierto. Podría usar algo como:

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

Pero esto solo funcionaría para d2 porque sus claves tienen 3 niveles (i, j, k) arriba.

Aquí está mi bash de una solución para generalizar esto, pero supongo que hay una ruta más simple.

 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}}} 

Simplemente haga un bucle sobre cada clave, y use todos menos el último elemento de la clave para agregar diccionarios. Mantenga una referencia al último diccionario así establecido, luego use el último elemento en la tupla de claves para establecer un par clave-valor en el diccionario de salida:

 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 

Podría usar functools.reduce() para manejar el trabajo de desplazamiento hacia abajo de los diccionarios:

 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() lugar de la opción defaultdict(nested_dict) auto-vivication, ya que esto produce un diccionario regular que no agregará claves implícitamente cuando aún no existan.

Manifestación:

 >>> 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}}}} 

Tenga en cuenta que la solución anterior es un bucle O (N) limpio (donde N es la longitud del diccionario de entrada), mientras que una solución groupby según lo propuesto por Ajax1234 tiene que ordenar la entrada para que funcione, lo que hace que sea una solución O (NlogN). Eso significa que para un diccionario con 1000 elementos, un groupby() necesitaría 10,000 pasos para producir la salida, mientras que un bucle lineal O (N) solo toma 1000 pasos. Para un millón de llaves, esto aumenta a 20 millones de pasos, etc.

Además, la recursión en Python es … lenta, ya que Python no puede optimizar tales soluciones a un enfoque iterativo. Las llamadas de función son relativamente caras, por lo que el uso de la recursión puede conllevar costos de rendimiento significativos a medida que aumenta considerablemente el número de llamadas de función y por las operaciones de la stack de marcos de extensión.

Una contrarreloj muestra cuánto importa esto; Al usar sus ejecuciones de muestra d3 y 100k, vemos fácilmente una diferencia de velocidad de 5x:

 >>> 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 

Puedes usar itertools.groupby con recursion:

 from itertools import groupby def create_nested_dict(d): _c = [[a, [(c, d) for (_, *c), d in b]] for a, b in groupby(sorted(d, key=lambda x:x[0][0]), key=lambda x:x[0][0])] return {a:b[0][-1] if not any([c for c, _ in b]) else create_nested_dict(b) for a, b in _c} 

 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))) print(create_nested_dict(d1.items())) print(create_nested_dict(d2.items())) print(create_nested_dict(d3.items())) 

Salida:

 {'A': {0: 0, 1: 1}, 'B': {0: 2, 1: 3}} {'A': {0: {False: 1, True: 0}, 1: {False: 3, True: 2}}, 'B': {0: {False: 5, True: 4}, 1: {False: 7, True: 6}}} {'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}}}}