Supongamos que hay una estructura como esta:
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } }
Usando python, estoy tratando de determinar las ventajas / desventajas de dos enfoques diferentes:
{'key1' : { 'key2' : { .... { 'keyn' : 'value' } ... } } } # A. nested dictionary {('key1', 'key2', ...., 'keyn') : 'value'} # B. a dictionary with a tuple used like key
Entonces me interesa saber qué es lo mejor (A o B) en términos de:
Sin entrar en detalles (que son muy dependientes de la implementación de todos modos y pueden ser invalidados por el siguiente genio que aparezca y modifique la implementación del diccionario):
Usted ve, no debería haber ninguna diferencia notable en el rendimiento, aunque alguna diferencia de memoria. Aunque este último no será notable, creo. Un dict de un elemento es de 140 bytes, una tupla de diez elementos también es de 140 bytes (de acuerdo con Python 3.2 sys.getsizeof
). Por lo tanto, incluso con el anidamiento de diez niveles (que ya es poco realista, dice mi instinto), tendría un poco más de un kB de diferencia, posiblemente menos si los dictados nesteds tienen varios elementos (depende del factor de carga exacto). Eso es demasiado para una aplicación de procesamiento de datos que tiene cientos de estructuras de datos en la memoria, pero la mayoría de los objetos no se crean con tanta frecuencia.
Simplemente debe preguntarse qué modelo es más apropiado para su problema. Tenga en cuenta que la segunda forma requiere que tenga todas las claves para un valor disponible a la vez, mientras que la segunda le permite llegar de forma incremental.
Si necesita usar la combinación completa de keyn
para keyn
para obtener un value
, puede voltear el dictado como sugerí a continuación para O (nk * nv) (número de claves * número de valores) o usar el método de la tuple
anterior.
Suponiendo que necesita construir la tuple
en la inserción y nuevamente cuando necesita obtener un valor, ambos serán O (nk) donde nk
es el número de claves.
La versión de dict
anidada podría ser más eficiente si está nested bastante (hay muchos valores que comparten una lista parcial ordenada de claves), y obtener un valor seguirá siendo O (nk), pero probablemente más lento que la tupla versión.
Sin embargo, la inserción será más lenta, aunque no puedo cuantificar su velocidad. Deberá construir al menos una capa de dict
para cada inserción y probar la existencia de dict
en los niveles anteriores.
Hay muchas recetas para los defaultdict
error defaultdict
recursivos que simplificarían la inserción desde una perspectiva de encoding, pero en realidad no aceleraría las cosas.
El método de la tuple
es más simple y más rápido de insertar, pero puede requerir más memoria dependiendo de su anidación.
Respuesta original de antes de conocer los requisitos.
Por qué no
{'key1' : 'value', 'key2' : 'value', .... 'keyn' : 'value' }
Solo almacena una referencia al value
en cada ubicación, no al value
sí mismo, por lo que el uso de la memoria sería menor que la versión dict
anidada, y no mucho más grande que la versión de la tuple
, a menos que tenga un número de value
extremadamente grande.
Para la complejidad de tiempo de las operaciones de tipo estándar de Python, consulte la wiki de Python .
Básicamente, la inserción o la obtención de un artículo en promedio es O (1).
Obtener todas las claves para un valor en promedio sería O (n):
[key for key in mydict if mydict[key] == value]
Sin embargo, si agregar teclas, o buscar todas las teclas, es la operación habitual, su dict
se invierte. Usted quiere:
{'value': [key1, key2, ... keyn]}
De esta manera, puede agregar claves con solo mydict[value].append(newkey)
y obtener todas las claves con solo mydict[value]
y ambas estarán en promedio O (1).
He escrito un pequeño guión para probarlo. Sin embargo, tiene algunas limitaciones, las claves están hechas de números enteros distribuidos linealmente (es decir, range(N)
), mis conclusiones son las siguientes.
Con un anidamiento de 3 niveles, es decir, dict[a][b][c]
vs dict[a,b,c]
donde cada subíndice va de 0 a 99, encuentro lo siguiente:
Con valores grandes ( list(x for x in range(100)
))
> memory.py nested Uso de memoria: 1049.0 MB > memory.py flat Uso de memoria: 1149.7 MB
y con pequeños valores ( []
):
> memory.py nested Uso de memoria: 134.1 MB > memory.py flat Uso de memoria: 234.8 MB
#!/usr/bin/env python3 import resource import random import itertools import sys import copy from os.path import basename from collections import defaultdict # constants index_levels = [100, 100, 100] value_size = 100 # try values like 0 def memory_usage(): return resource.getrusage(resource.RUSAGE_SELF).ru_maxrss _object_mold = list(x for x in range(value_size)) # performance hack def create_object(): return copy.copy(_object_mold) # automatically create nested dict # http://code.activestate.com/recipes/578057-recursive-defaultdict/ f = lambda: defaultdict(f) my_dict = defaultdict(f) # options & usage try: dict_mode = sys.argv[1] if dict_mode not in ['flat', 'nested']: # ugly hack raise Error() except: print("Usage: {} [nested | flat]".format(basename(sys.argv[0]))) exit() index_generator = [range(level) for level in index_levels] if dict_mode == "flat": for index in itertools.product(*index_generator): my_dict[index] = create_object() elif dict_mode == "nested": for index in itertools.product(*index_generator): sub_dict = my_dict for sub_index in index[:-1]: # iterate into lowest dict sub_dict = sub_dict[sub_index] sub_dict[index[-1]] = create_object() # finally assign value print("Memory usage: {:.1f} MB".format(memory_usage() / 1024**2))
Realicé pruebas de bucle, recuperación e inserción para un diccionario nested y un diccionario con una tupla. Son un nivel profundo, 2000.000 valores. También realicé la recuperación y la inserción de la tupla con la tupla ya creada.
Estos son los resultados. Creo que realmente no se pueden vincular conclusiones con el desarrollo estándar.
–
keydictinsertion: Mean +- std dev: 615 ms +- 42 ms keydictretrieval: Mean +- std dev: 475 ms +- 77 ms keydictlooping: Mean +- std dev: 76.2 ms +- 7.4 ms nesteddictinsertion: Mean +- std dev: 200 ms +- 7 ms nesteddictretrieval: Mean +- std dev: 256 ms +- 32 ms nesteddictlooping: Mean +- std dev: 88.5 ms +- 14.4 ms Test were the tuple was already created for the keydict keydictinsertionprepared: Mean +- std dev: 432 ms +- 26 ms keydictretrievalprepared: Mean +- std dev: 267 ms +- 14 ms
–
Como puede ver, el indicador nested es a menudo más rápido que el dictado con una sola tecla. Incluso cuando se le dio a la pieza clave una tupla directamente sin el paso de creación de la tupla, la inserción fue mucho más lenta. Parecía que la creación adicional de un dictado interno no es tanto costo. Defaultdict tiene probablemente una implementación rápida. La recuperación era en realidad casi igual cuando no tenía que crear una tupla, lo mismo que con el bucle.
La prueba se realiza con perf desde la línea de comando. Los scripts están abajo.
>>>>>>> nesteddictinsertion python -m perf timeit -v -s " from collections import defaultdict " " d = defaultdict(dict) for i in range(2000): for j in range(1000): d[i][j] = 1 " >>>>>>> nesteddictlooping python -m perf timeit -v -s " from collections import defaultdict d = defaultdict(dict) for i in range(2000): for j in range(1000): d[i][j] = 1 " " for i, inner_dict in d.items(): for j, val in inner_dict.items(): i j val " >>>>>>> nesteddictretrieval python -m perf timeit -v -s " from collections import defaultdict d = defaultdict(dict) for i in range(2000): for j in range(1000): d[i][j] = 1 " " for i in range(2000): for j in range(1000): d[i][j] " >>>>>>> keydictinsertion python -m perf timeit -v -s " from collections import defaultdict " " d = {} for i in range(2000): for j in range(1000): d[i, j] = 1 " >>>>>>> keydictinsertionprepared python -m perf timeit -v -s " from collections import defaultdict keys = [(i, j) for i in range(2000) for j in range(1000)] " " d = {} for key in keys: d[key] = 1 " >>>>>>> keydictlooping python -m perf timeit -v -s " from collections import defaultdict d = {} for i in range(2000): for j in range(1000): d[i, j] = 1 " " for key, val in d.items(): key val " >>>>>>> keydictretrieval python -m perf timeit -v -s " from collections import defaultdict d = {} for i in range(2000): for j in range(1000): d[i, j] = 1 " " for i in range(2000): for j in range(1000): d[i, j] " >>>>>>> keydictretrievalprepared python -m perf timeit -v -s " from collections import defaultdict d = {} keys = [(i, j) for i in range(2000) for j in range(1000)] for key in keys: d[key] = 1 " " for key in keys: d[key] "