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

• Para la sobrecarga de memoria: cada objeto tiene cierta sobrecarga (por ejemplo, refcount y tipo; un objeto vacío es de 8 bytes y una tupla vacía de 28 bytes), pero las tablas hash necesitan almacenar hash, clave y valor, y usualmente usan más depósitos de los que se necesitan actualmente para evitar la colision Por otro lado, las tuplas no se pueden redimensionar y no tienen colisiones, es decir, una tupla N puede simplemente asignar N punteros a los objetos contenidos y hacerse. Esto conduce a notables diferencias en el consumo de memoria.
• Para la complejidad de búsqueda e inserción (los dos son idénticos a este respecto): ya sea una cadena o una tupla, las colisiones son bastante improbables en la implementación del dictado de CPython y se resuelven de manera muy eficiente. Más claves (debido a que usted aplana el espacio de claves combinando las claves en tuplas) puede parecer boost la probabilidad de colisiones, más claves también conducen a más depósitos (AFAIK, la implementación actual intenta mantener el factor de carga entre 2/3), lo cual a su vez hace menos probable la colisión. Además, no necesita más hash (bueno, una llamada a la función más y un poco de ajuste de nivel C para el hash de la tupla, pero eso es negativo) para obtener un valor.

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

Prueba de consumo de memoria

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

Preguntas abiertas

• ¿Por qué está pasando esto?
• ¿Cambiaría esto con diferentes índices, por ejemplo, no consecutivos?

Guión

 #!/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)) 

Pruebas de rendimiento

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