¿Qué tan caros son los diccionarios de Python para manejar?

Question

Como dice el título, ¿qué tan caros son los diccionarios de Python para manejar? Creación, inserción, actualización, eliminación, todo.

Las complejidades de tiempo asintóticas son interesantes por sí mismas, pero también cómo se comparan con, p. tuplas o listas normales.

Answer 1

dicts (al igual que set s cuando no es necesario asociar un valor a cada tecla, simplemente registrar si una clave está presente o ausente) están bastante optimizadas. Crear un dict desde N teclas o pares de clave/valor es O(N), ir a buscar es O(1), poner se amortiza O(1), y así sucesivamente. ¡Realmente no puedo hacer nada sustancialmente mejor para ningún contenedor no pequeño!

Para contenedores pequeños, puede verificar fácilmente los límites con timeit-puntos de referencia basados. Por ejemplo:

$ python -mtimeit -s'empty=()' '23 in empty' 
10000000 loops, best of 3: 0.0709 usec per loop 
$ python -mtimeit -s'empty=set()' '23 in empty' 
10000000 loops, best of 3: 0.101 usec per loop 
$ python -mtimeit -s'empty=[]' '23 in empty' 
10000000 loops, best of 3: 0.0716 usec per loop 
$ python -mtimeit -s'empty=dict()' '23 in empty' 
10000000 loops, best of 3: 0.0926 usec per loop 

esto demuestra que el control de la pertenencia a listas vacías o tuplas es más rápido, por una diferencia de 20-30 nanosegundos, que el control de la pertenencia a conjuntos vacíos o predice; cuando importa cada nanosegundo, esta información puede ser relevante para usted. Subiendo un poco ...:

$ python -mtimeit -s'empty=range(7)' '23 in empty' 
1000000 loops, best of 3: 0.318 usec per loop 
$ python -mtimeit -s'empty=tuple(range(7))' '23 in empty' 
1000000 loops, best of 3: 0.311 usec per loop 
$ python -mtimeit -s'empty=set(range(7))' '23 in empty' 
10000000 loops, best of 3: 0.109 usec per loop 
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '23 in empty' 
10000000 loops, best of 3: 0.0933 usec per loop 

se ve que para el 7-contenedores artículos (no incluyendo el de interés) el equilibrio entre rendimiento ha cambiado, y ahora predice y conjuntos tienen las ventajas de cientos de nanosegundos . Cuando el elemento de interés está presente:

$ python -mtimeit -s'empty=range(7)' '5 in empty' 
1000000 loops, best of 3: 0.246 usec per loop 
$ python -mtimeit -s'empty=tuple(range(7))' '5 in empty' 
1000000 loops, best of 3: 0.25 usec per loop 
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '5 in empty' 
10000000 loops, best of 3: 0.0921 usec per loop 
$ python -mtimeit -s'empty=set(range(7))' '5 in empty' 
10000000 loops, best of 3: 0.112 usec per loop 

dicts y conjuntos no ganan mucho, pero tuplas y hacer la lista, a pesar de que predice y conjunto siguen siendo muy rápido.

Y así sucesivamente - timeit hace que sea trivialmente fácil ejecutar micro-puntos de referencia (estrictamente hablando, garantizado solo para situaciones extremadamente raras donde los nanosegundos sí importan, pero lo suficientemente fácil de hacer que no es grande dificultad para verificar OTROS casos ;-).

Answer 2

Los diccionarios son una de las partes más afinadas de Python, ya que son la base de gran parte del lenguaje. Por ejemplo, los miembros de una clase y las variables en un marco de pila se almacenan internamente en los diccionarios. Serán una buena opción si son la estructura de datos correcta.

Elegir entre listas y dictados según el rendimiento parece extraño: hacen cosas diferentes. Tal vez puedas decirnos más sobre el problema que estás tratando de resolver.