2.7. Diccionarios¶
La segunda estructura de datos principal de Python es el diccionario. Como usted probablemente recordará, los diccionarios difieren de las listas en que usted puede acceder a los ítems de un diccionario mediante una clave en lugar de una posición. Más adelante en este libro verá que hay muchas maneras de implementar un diccionario. Lo que es más importante notar ahora mismo es que las operaciones para obtener y asignar ítems en un diccionario son
operación |
Eficiencia O-grande |
---|---|
copiar |
O(n) |
obtener ítem |
O(1) |
asignar ítem |
O(1) |
eliminar ítem |
O(1) |
pertenencia (in) |
O(1) |
iteración |
O(n) |
Para nuestro último experimento de desempeños, compararemos el desempeño de la operación de pertenencia entre listas y diccionarios. En el proceso confirmaremos que el operador de pertenencia para las listas es
Repetiremos el mismo experimento para un diccionario que contiene números como claves. En este experimento deberíamos notar que la determinación de si un número está en el diccionario no sólo es mucho más rápida, sino que el tiempo que se tarda la comprobación debería permanecer constante a medida que el diccionario se hace más grande.
El Programa 6 implementa esta comparación. Observe que estamos realizando exactamente la misma operación, número in contenedor
. La diferencia es que en la línea 7 x
es una lista, y en la línea 9 x
es un diccionario.
Programa 6
1import timeit
2import random
3
4for i in range(10000,1000001,20000):
5 t = timeit.Timer("random.randrange(%d) in x"%i,
6 "from __main__ import random,x")
7 x = list(range(i))
8 tiempo_lista = t.timeit(number=1000)
9 x = {j:None for j in range(i)}
10 tiempo_diccionario = t.timeit(number=1000)
11 print("%d,%10.3f,%10.3f" % (i, tiempo_lista, tiempo_diccionario))
La Figura 4 resume los resultados de la ejecución del Programa 6. Usted puede ver que el diccionario es consistentemente más rápido. Para el tamaño de lista más pequeño (de 10,000 elementos), un diccionario es 89.4 veces más rápido que una lista. ¡Para el tamaño de la lista más grande (de 990,000 elementos) el diccionario es 11,603 veces más rápido! Usted también puede ver que el tiempo que tarda el operador de pertencia en el caso de la lista crece linealmente con el tamaño de la misma. Esto verifica la afirmación de que el operador de pertencia en una lista es
Dado que Python es un lenguaje en evolución, siempre hay cambios que suceden entre bastidores. La información más reciente sobre el rendimiento de las estructuras de datos de Python se puede encontrar en el sitio web de Python. Desde que se escribió este texto, la wiki de Python tiene una agradable página de complejidades de tiempo que se puede consultar en la página titulada Time Complexity Wiki.
Autoevaluación
- lista.pop(0)
- Cuando usted quita el primer elemento de una lista, todos los demás elementos de la lista deben desplazarse hacia adelante.
- lista.pop()
- Eliminar un elemento del final de la lista es una operación constante.
- lista.append()
- Añadir al final de la lista es una operación constante
- lista[10]
- Indizar una lista es una operación constante
- todas las anteriores son O(1)
- Hay una operación que requiere que todos los demás elementos de lista se muevan.
Q-1: ¿Cuál de las operaciones sobre listas que se muestran a continuación no es O(1)?
- 'x' in miDiccionario
in es una operación constante para un diccionario porque no tiene que iterar pero hay una respuesta mejor.- del miDiccionario['x']
- Borrar un elemento de un diccionario es una operación constante, pero hay una respuesta mejor.
- miDiccionario['x'] == 10
- La asignación a una clave de diccionario es constante pero hay una respuesta mejor.
- miDiccionario['x'] = miDiccionario['x'] + 1
- La reasignación a una clave de diccionario es constante pero hay una respuesta mejor.
- todas las anteriores son O(1)
- Las únicas operaciones de diccionario que no son O(1) son aquéllas que requieren iteración.
Q-2: ¿Cuál de las operaciones sobre diccionarios que se muestran a continuación es O(1)?