python - recorrer - Acceso eficiente a diccionarios arbitrariamente profundos.

lista dentro de un diccionario python

Question

Supongamos que tengo un diccionario de varios niveles como este

mydict = {
''first'': {
''second'': {
''third'': {
''fourth'': ''the end''
}
}
}
}

Me gustaría acceder así

test = get_entry(mydict, ''first.second.third.fourth'')

Lo que tengo hasta ahora es

def get_entry(dict, keyspec):
keys = keyspec.split(''.'')
result = dict[keys[0]]
for key in keys[1:]:
result = dict[key]
return result

¿Hay formas más eficientes de hacerlo? De acuerdo con% timeit, el tiempo de ejecución de la función es 1.26us, mientras se accede al diccionario de la manera estándar como esta

foo = mydict[''first''][''second''][''third''][''fourth'']

lleva 541ns. Estoy buscando maneras de recortarlo a un rango de 800 ns si es posible.

Gracias

Answer 1

Actualicé la respuesta de Cómo usar un punto "." para acceder a los miembros del diccionario? para usar una conversión inicial que luego funcionará para los diccionarios anidados:

Puede usar la siguiente clase para permitir la indexación de puntos de los diccionarios:

class dotdict(dict):
"""dot.notation access to dictionary attributes"""
__getattr__ = dict.get
__setattr__ = dict.__setitem__
__delattr__ = dict.__delitem__

Sin embargo, esto solo es compatible con el anidamiento si todos los diccionarios anidados también son de tipo dotdict . Ahí es donde entra la siguiente función auxiliar:

def dct_to_dotdct(d):
if isinstance(d, dict):
d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
return d

Esta función debe ejecutarse una vez en su diccionario anidado, y el resultado puede ser indexado utilizando la indexación de puntos.

Aquí hay unos ejemplos:

In [13]: mydict
Out[13]: {''first'': {''second'': {''third'': {''fourth'': ''the end''}}}}
In [14]: mydict = dct_to_dotdct(mydict)
In [15]: mydict.first.second
Out[15]: {''third'': {''fourth'': ''the end''}}
In [16]: mydict.first.second.third.fourth
Out[16]: ''the end''

Una nota sobre el rendimiento: esta respuesta es lenta en comparación con el acceso al diccionario estándar, solo quería presentar una opción que realmente utilizara el "acceso de punto" a un diccionario.

Answer 2

Aquí hay una solución similar a la de chrisz, pero no tiene que hacer nada para su dictamen anterior. :

class dictDotter(dict):
def __getattr__(self,key):
val = self[key]
return val if type(val) != dict else dictDotter(val)

y solo x=dictDotter(originalDict) le permitirá obtener puntos arbitrarios (`x.first.second ...). Notaré que esto es dos veces más lento que la solución chrisz, y su es 9 veces más lento que el tuyo (en mi máquina, aproximadamente).

Por lo tanto, si insiste en hacer que esto funcione, @tdelaney parece haber proporcionado la única mejora real del rendimiento.

Otra opción que funciona mejor que lo que tienes (en términos de tiempo de ejecución):

class dictObjecter:
def __init__(self,adict):
for k,v in adict.items():
self.__dict__[k] = v
if type(v) == dict: self.__dict__[k] = dictObjecter(v)

lo que hará que un objeto salga de tu dictado, por lo que la notación con puntos es habitual. Esto mejorará el tiempo de ejecución a 3 veces lo que tiene , así que no está mal, pero al costo de revisar su dictamen y reemplazarlo con otra cosa.

Aquí está el código de prueba total:

from timeit import timeit
class dictObjecter:
def __init__(self,adict):
for k,v in adict.items():
self.__dict__[k] = v
if type(v) == dict: self.__dict__[k] = dictObjecter(v)
class dictDotter(dict):
def __getattr__(self,key):
val = self[key]
return val if type(val) != dict else dictDotter(val)
def get_entry(dict, keyspec):
keys = keyspec.split(''.'')
result = dict[keys[0]]
for key in keys[1:]:
result = result[key]
return result
class dotdict(dict):
"""dot.notation access to dictionary attributes"""
__getattr__ = dict.get
__setattr__ = dict.__setitem__
__delattr__ = dict.__delitem__
def dct_to_dotdct(d):
if isinstance(d, dict):
d = dotdict({k: dct_to_dotdct(v) for k, v in d.items()})
return d
x = {''a'':{''b'':{''c'':{''d'':1}}}}
y = dictDotter(x)
z = dct_to_dotdct(x)
w = dictObjecter(x)
print(''{:15} : {}''.format(''dict dotter'',timeit(''y.a.b.c.d'',globals=locals(),number=1000)))
print(''{:15} : {}''.format(''dot dict'',timeit(''z.a.b.c.d'',globals=locals(),number=1000)))
print(''{:15} : {}''.format(''dict objecter'',timeit(''w.a.b.c.d'',globals=locals(),number=1000)))
print(''{:15} : {}''.format(''original'',timeit("get_entry(x,''a.b.c.d'')",globals=locals(),number=1000)))
print(''{:15} : {:.20f}''.format(''best ref'',timeit("x[''a''][''b''][''c''][''d'']",globals=locals(),number=1000)))

Proporcioné la última búsqueda regular como una mejor referencia. Los resultados en un subsistema Ubuntu de Windows:

dict dotter : 0.0035500000003594323
dot dict : 0.0017939999997906853
dict objecter : 0.00021699999979318818
original : 0.0006629999998040148
best ref : 0.00007999999979801942

por lo tanto, el dictamen está objetivado es 3 veces más lento que una búsqueda en un diccionario regular. Entonces, si la velocidad es importante, ¿por qué querría esto?

Answer 3

Obtuve un aumento del 20% en el rendimiento al ajustar un poco el código, pero un enorme aumento del 400% al usar un caché para cadenas divididas. Eso solo hace una diferencia si usas la misma especificación varias veces. Aquí están las implementaciones de muestra y un script de perfil para probar.

test.py

mydict = {
''first'': {
''second'': {
''third'': {
''fourth'': ''the end''
}
}
}
}
# original
def get_entry(dict, keyspec):
keys = keyspec.split(''.'')
result = dict[keys[0]]
for key in keys[1:]:
result = result[key]
return result
# tighten up code
def get_entry_2(mydict, keyspec):
for key in keyspec.split(''.''):
mydict = mydict[key]
return mydict
# use a cache
cache = {}
def get_entry_3(mydict, keyspec):
global cache
try:
spec = cache[keyspec]
except KeyError:
spec = tuple(keyspec.split(''.''))
cache[keyspec] = spec
for key in spec:
mydict = mydict[key]
return mydict
if __name__ == "__main__":
test = get_entry(mydict, ''first.second.third.fourth'')
print(test)

perfil.py

from timeit import timeit
print("original get_entry")
print(timeit("get_entry(mydict, ''first.second.third.fourth'')",
setup="from test import get_entry, mydict"))
print("get_entry_2 with tighter code")
print(timeit("get_entry_2(mydict, ''first.second.third.fourth'')",
setup="from test import get_entry_2, mydict"))
print("get_entry_3 with cache of split spec")
print(timeit("get_entry_3(mydict, ''first.second.third.fourth'')",
setup="from test import get_entry_3, mydict"))
print("just splitting a spec")
print(timeit("x.split(''.'')", setup="x=''first.second.third.fourth''"))

El tiempo en mi máquina es

original get_entry
4.148535753000033
get_entry_2 with tighter code
3.2986323120003362
get_entry_3 with cache of split spec
1.3073233439990872
just splitting a spec
1.0949148639992927

Observe que dividir la especificación es una operación comparativamente costosa para esta función. Es por eso que el almacenamiento en caché ayuda.

Answer 4

Puedes usar reduce ( functools.reduce en python3):

import operator
def get_entry(dct, keyspec):
return reduce(operator.getitem, keyspec.split(''.''), dct)

Tiene un aspecto más agradable pero con un poco menos de rendimiento.

Tu versión timeit:

>>> timeit("get_entry_original(mydict, ''first.second.third.fourth'')",
"from __main__ import get_entry_original, mydict", number=1000000)
0.5646841526031494

con reducir:

>>> timeit("get_entry(mydict, ''first.second.third.fourth'')",
"from __main__ import get_entry, mydict")
0.6140949726104736

Como se ha dicho, la división consume casi tanto poder de la CPU como obtener la clave en dict:

def split_keys(keyspec):
keys = keyspec.split(''.'')
timeit("split_keys(''first.second.third.fourth'')",
"from __main__ import split_keys")
0.28857898712158203

Simplemente mueva la división de get_entry función get_entry :

def get_entry(dct, keyspec_list):
return reduce(operator.getitem, keyspec_list, dct)
timeit("get_entry(mydict, [''first'', ''second'', ''third'', ''fourth''])",
"from __main__ import get_entry, mydict")
0.37825703620910645

Answer 5

Realmente hay una sola solución. Reconstruye tu diccionario. Pero hazlo solo una vez.

def recursive_flatten(mydict):
d = {}
for k, v in mydict.items():
if isinstance(v, dict):
for k2, v2 in recursive_flatten(v).items():
d[k + ''.'' + k2] = v2
else:
d[k] = v
return d

In [786]: new_dict = recursive_flatten(mydict); new_dict
Out[786]: {''first.second.third.fourth'': ''the end''}

(Algunas pruebas más)

In [788]: recursive_flatten({''x'' : {''y'' : 1, ''z'' : 2}, ''y'' : {''a'' : 5}, ''z'' : 2})
Out[788]: {''x.y'': 1, ''x.z'': 2, ''y.a'': 5, ''z'': 2}
In [789]: recursive_flatten({''x'' : 1, ''y'' : {''x'' : 234}})
Out[789]: {''x'': 1, ''y.x'': 234}

Cada acceso se convierte en tiempo constante de aquí en adelante.

Ahora, simplemente acceda a su valor usando new_dict[''first.second.third.fourth''] . Debería funcionar para cualquier diccionario anidado arbitrariamente que no contenga una auto-referencia.

Tenga en cuenta que cada solución tiene su parte justa de compensaciones, esto no es una excepción. A menos que esté disparando millones de consultas a sus datos, de modo que el procesamiento previo sea una sobrecarga aceptable, entonces esto es todo. Con las otras soluciones, solo está esquivando el problema en lugar de resolverlo, que es tratar con la estructura del diccionario. OTOH, si va a hacer esto una vez en muchas estructuras de datos similares, no tiene sentido realizar un proceso previo solo para una consulta, en cuyo caso puede preferir una de las otras soluciones.

Answer 6

Tenía la misma necesidad, así que creé el Prodict .

Para su caso, puede hacerlo en una línea:

mydict = {
''first'': {
''second'': {
''third'': {
''fourth'': ''the end''
}
}
}
}
dotdict = Prodict.from_dict(mydict)
print(dotdict.first.second.third.fourth) # "the end"

Después de eso, use dotdict como un dict, porque es una subclase de dict:

dotdict.first == dotdict[''first''] # True

También puede agregar más claves dinámicamente con notación de puntos:

dotdict.new_key = ''hooray''
print(dotdict.new_key) # "hooray"

Funciona incluso si las nuevas claves son diccionarios anidados:

dotdict.it = {''just'': ''works''}
print(dotdict.it.just) # "works"

Por último, si define sus claves de antemano, obtendrá la finalización automática y la conversión automática de tipos:

class User(Prodict):
user_id: int
name: str
user = User(user_id="1", "name":"Ramazan")
type(user.user_id) # <class ''int''>
# IDE will be able to auto complete ''user_id'' and ''name'' properties

ACTUALIZACIÓN :

Este es el resultado de la prueba para el mismo código escrito por @kabanus:

x = {''a'': {''b'': {''c'': {''d'': 1}}}}
y = dictDotter(x)
z = dct_to_dotdct(x)
w = dictObjecter(x)
p = Prodict.from_dict(x)
print(''{:15} : {}''.format(''dict dotter'', timeit(''y.a.b.c.d'', globals=locals(), number=10000)))
print(''{:15} : {}''.format(''prodict'', timeit(''p.a.b.c.d'', globals=locals(), number=10000)))
print(''{:15} : {}''.format(''dot dict'', timeit(''z.a.b.c.d'', globals=locals(), number=10000)))
print(''{:15} : {}''.format(''dict objecter'', timeit(''w.a.b.c.d'', globals=locals(), number=10000)))
print(''{:15} : {}''.format(''original'', timeit("get_entry(x,''a.b.c.d'')", globals=locals(), number=10000)))
print(''{:15} : {:.20f}''.format(''prodict getitem'', timeit("p[''a''][''b''][''c''][''d'']", globals=locals(), number=10000)))
print(''{:15} : {:.20f}''.format(''best ref'', timeit("x[''a''][''b''][''c''][''d'']", globals=locals(), number=10000)))

Y resultados:

dict dotter : 0.04535976458466595
prodict : 0.02860781018446784
dot dict : 0.019078164088831673
dict objecter : 0.0017378700050722368
original : 0.006594238310349346
prodict getitem : 0.00510931794975705289
best ref : 0.00121740293554022105

Como puede ver, su rendimiento es entre "dict dotter" y "dot dict". Cualquier sugerencia de mejora de rendimiento será apreciada.

Answer 7

¡El código debe ser menos iterativo y más dinámico!

datos

mydict = {
''first'': {
''second'': {
''third'': {
''fourth'': ''the end''
}
}
}
}

Función

def get_entry(dict, keyspec):
for keys in keyspec.split(''.''):
dict = dict[keys]
return dict

llamar a la función

res = get_entry(mydict, ''first.second.third.fourth'')

¡Esto llevará menos tiempo para ejecutarse, incluso si se trata de una ejecución de código dinámico!