Rendimiento de la lista de tipos de datos integrados de Python y el dictado del diccionario
Realización de operaciones comunes sobre el tipo de datos lista:
1. Adquisición y asignación de valores por índice (v=a[i], a[i]=v)
p>
Debido a las características de acceso aleatorio de la lista, el tiempo de ejecución de estas dos operaciones no tiene nada que ver con el tamaño de la lista, ambas son O(1)
2. La longitud máxima de la lista se puede calcular a partir de append() y _add _() " "
list.append(v) tiene un tiempo de ejecución de O(1)
lista = lista [v] y tiene un tiempo de ejecución de O(n k) , porque se va a agregar una nueva lista, donde k es la longitud de la lista a agregar
Ejemplo: 4 formas de generar una lista de los primeros n enteros
Como se muestra en la figura:
Podemos calcular el tiempo consumido por estas cuatro funciones, como se muestra a continuación
Ejecución resultados:
Podemos ver que la operación de estos cuatro métodos Los tiempos varían mucho, siendo la prueba 1 que usa concatenación de listas la más lenta y la prueba 4 que usa el rango de listas la más rápida, una diferencia de casi 200 veces en velocidad.
En la figura siguiente, resumimos el rendimiento de las operaciones básicas de lista:
En la figura anterior, podemos ver que pop() elimina elementos del final de la lista en un La velocidad de O (1) y la velocidad de pop (i) para eliminar elementos del medio de la lista es O (n).
Debido a que eliminar un elemento del medio moverá todos los elementos después del elemento eliminado hacia adelante en uno, esto asegura que la lista esté indexada y asignada valores muy rápidamente, alcanzando O(1).
Tipo de datos del diccionario:
El diccionario es diferente de la lista. dict busca valores según claves, mientras que la lista busca valores según índices.
El diccionario se usa más comúnmente para obtener valores y establecer asignaciones, su rendimiento es O (1) y la operación contener (en) puede determinar si existe una clave en el diccionario, su rendimiento también es O ( ), pero el rendimiento del valor clave también es O(1)
Tipo de datos Dict:
El diccionario se usa más comúnmente para la obtención de valores y el conjunto de asignaciones, y su rendimiento también es O(1). 1)
Compare las operaciones de entrada de list y dict:
Diseñe una prueba de rendimiento para verificar la comparación que requiere mucho tiempo entre la recuperación de valores en list y la recuperación de valores en dict . El siguiente programa:
Si es el siguiente:
Observe que la complejidad del funcionamiento de la lista es O(n)
PD: Puede acceder al sitio web oficial de complejidad del algoritmo de Python:
https://wiki.python.org/moin/TimeComplexity.