¿Cuál es la mejor manera de implementar diccionarios anidados?

¿Cuál es la mejor manera de implementar diccionarios anidados en Python?

Esta es una mala idea, no lo hagas. En su lugar, utilice un diccionario normal y úselo dict.setdefaultcuando corresponda, de modo que cuando falten claves en el uso normal, obtenga el archivo esperado KeyError. Si insistes en tener este comportamiento, aquí te explicamos cómo dispararte en el pie:

Implemente __missing__en una dictsubclase para establecer y devolver una nueva instancia.

Este enfoque ha estado disponible (y documentado) desde Python 2.5 y (particularmente valioso para mí) se imprime como un dict normal , en lugar de la fea impresión de un defaultdict autovivificado:

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)() # retain local pointer to value
        return value                     # faster to return than dict lookup

(La nota self[key]está en el lado izquierdo de la tarea, por lo que aquí no hay recursividad).

y di que tienes algunos datos:

data = {('new jersey', 'mercer county', 'plumbers'): 3,
        ('new jersey', 'mercer county', 'programmers'): 81,
        ('new jersey', 'middlesex county', 'programmers'): 81,
        ('new jersey', 'middlesex county', 'salesmen'): 62,
        ('new york', 'queens county', 'plumbers'): 9,
        ('new york', 'queens county', 'salesmen'): 36}

Aquí está nuestro código de uso:

vividict = Vividict()
for (state, county, occupation), number in data.items():
    vividict[state][county][occupation] = number

Y ahora:

>>> import pprint
>>> pprint.pprint(vividict, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36}}}

Crítica

Una crítica a este tipo de contenedor es que si el usuario escribe mal una clave, nuestro código podría fallar silenciosamente:

>>> vividict['new york']['queens counyt']
{}

Y además ahora tendríamos un condado mal escrito en nuestros datos:

>>> pprint.pprint(vividict, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36},
              'queens counyt': {}}}

Explicación:

Simplemente proporcionamos otra instancia anidada de nuestra clase Vividictcada vez que se accede a una clave pero falta. (Devolver la asignación de valor es útil porque nos evita llamar adicionalmente al captador en el dict y, desafortunadamente, no podemos devolverlo mientras se está configurando).

Tenga en cuenta que esta es la misma semántica que la respuesta más votada pero en la mitad de las líneas de código: la implementación de nosklo:

class AutoVivification(dict):
    """Implementation of perl's autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

Demostración de uso

A continuación se muestra solo un ejemplo de cómo este dict podría usarse fácilmente para crear una estructura de dict anidada sobre la marcha. Esto puede crear rápidamente una estructura de árbol jerárquica tan profunda como desee.

import pprint

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

d = Vividict()

d['foo']['bar']
d['foo']['baz']
d['fizz']['buzz']
d['primary']['secondary']['tertiary']['quaternary']
pprint.pprint(d)

Qué salidas:

{'fizz': {'buzz': {}},
 'foo': {'bar': {}, 'baz': {}},
 'primary': {'secondary': {'tertiary': {'quaternary': {}}}}}

Y como muestra la última línea, se imprime muy bien y en orden para la inspección manual. Pero si desea inspeccionar visualmente sus datos, implementar __missing__para establecer una nueva instancia de su clase en la clave y devolverla es una solución mucho mejor.

Otras alternativas, por el contrario:

dict.setdefault

Aunque el autor de la pregunta cree que esto no está limpio, lo encuentro preferible a Vividictmí mismo.

d = {} # or dict()
for (state, county, occupation), number in data.items():
    d.setdefault(state, {}).setdefault(county, {})[occupation] = number

y ahora:

>>> pprint.pprint(d, width=40)
{'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36}}}

Un error ortográfico fallaría estrepitosamente y no saturaría nuestros datos con mala información:

>>> d['new york']['queens counyt']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'queens counyt'

Además, creo que setdefault funciona muy bien cuando se usa en bucles y no sabes qué obtendrás como claves, pero el uso repetitivo se vuelve bastante engorroso y no creo que nadie quiera seguir con lo siguiente:

d = dict()

d.setdefault('foo', {}).setdefault('bar', {})
d.setdefault('foo', {}).setdefault('baz', {})
d.setdefault('fizz', {}).setdefault('buzz', {})
d.setdefault('primary', {}).setdefault('secondary', {}).setdefault('tertiary', {}).setdefault('quaternary', {})

Otra crítica es que setdefault requiere una nueva instancia, ya sea que se use o no. Sin embargo, Python (o al menos CPython) es bastante inteligente a la hora de manejar nuevas instancias no utilizadas y sin referencia; por ejemplo, reutiliza la ubicación en la memoria:

>>> id({}), id({}), id({})
(523575344, 523575344, 523575344)

Un defaultdict autovivificado

Esta es una implementación de apariencia ordenada, y su uso en un script en el que no estás inspeccionando los datos sería tan útil como implementar __missing__:

from collections import defaultdict

def vivdict():
    return defaultdict(vivdict)

Pero si necesita inspeccionar sus datos, los resultados de un defaultdict autovivificado y poblado con datos de la misma manera se ven así:

>>> d = vivdict(); d['foo']['bar']; d['foo']['baz']; d['fizz']['buzz']; d['primary']['secondary']['tertiary']['quaternary']; import pprint; 
>>> pprint.pprint(d)
defaultdict(<function vivdict at 0x17B01870>, {'foo': defaultdict(<function vivdict 
at 0x17B01870>, {'baz': defaultdict(<function vivdict at 0x17B01870>, {}), 'bar': 
defaultdict(<function vivdict at 0x17B01870>, {})}), 'primary': defaultdict(<function 
vivdict at 0x17B01870>, {'secondary': defaultdict(<function vivdict at 0x17B01870>, 
{'tertiary': defaultdict(<function vivdict at 0x17B01870>, {'quaternary': defaultdict(
<function vivdict at 0x17B01870>, {})})})}), 'fizz': defaultdict(<function vivdict at 
0x17B01870>, {'buzz': defaultdict(<function vivdict at 0x17B01870>, {})})})

Este resultado es bastante poco elegante y los resultados son bastante ilegibles. La solución que se suele dar es volver a convertir de forma recursiva a un dict para la inspección manual. Esta solución no trivial se deja como ejercicio para el lector.

Actuación

Finalmente, veamos el rendimiento. Estoy restando los costos de creación de instancias.

>>> import timeit
>>> min(timeit.repeat(lambda: {}.setdefault('foo', {}))) - min(timeit.repeat(lambda: {}))
0.13612580299377441
>>> min(timeit.repeat(lambda: vivdict()['foo'])) - min(timeit.repeat(lambda: vivdict()))
0.2936999797821045
>>> min(timeit.repeat(lambda: Vividict()['foo'])) - min(timeit.repeat(lambda: Vividict()))
0.5354437828063965
>>> min(timeit.repeat(lambda: AutoVivification()['foo'])) - min(timeit.repeat(lambda: AutoVivification()))
2.138362169265747

Según el rendimiento, dict.setdefaultfunciona mejor. Lo recomiendo encarecidamente para código de producción, en los casos en los que le importe la velocidad de ejecución.

Si necesita esto para uso interactivo (quizás en una computadora portátil IPython), entonces el rendimiento realmente no importa; en cuyo caso, elegiría Vividict para facilitar la lectura de la salida. Comparado con el objeto AutoVivificación (que utiliza __getitem__en lugar de __missing__, que fue creado para este propósito) es muy superior.

Conclusión

Implementar __missing__en una subclase dictpara establecer y devolver una nueva instancia es un poco más difícil que las alternativas, pero tiene los beneficios de

• fácil creación de instancias
• población de datos fácil
• fácil visualización de datos

y debido a que es menos complicado y más eficaz que modificar __getitem__, debería preferirse a ese método.

Sin embargo, tiene desventajas:

• Las búsquedas incorrectas fallarán silenciosamente.
• La búsqueda incorrecta permanecerá en el diccionario.

Por lo tanto, personalmente prefiero setdefaultotras soluciones y lo he hecho en todas las situaciones en las que he necesitado este tipo de comportamiento.

Nov 07 '2013 06:11 Russia Must Remove Putin