ordenamiento - ¿Por qué la lista de elementos de búsqueda es O(1) en Python?
busquedas binarias en python (3)
Cuando dice a = [...] , a es efectivamente un puntero a un PyObject contiene una matriz de punteros a PyObject s.
Cuando solicita a[2] , el intérprete primero sigue el puntero al PyObject la lista, luego agrega 2 a la dirección de la matriz que está dentro y luego devuelve ese puntero. Lo mismo sucede si pides a[0] o a[9999] .
Básicamente, se accede a todos los objetos de Python por referencia en lugar de por valor, incluso literales enteros como 2 . Hay solo algunos trucos en el sistema de punteros para mantener todo esto eficiente. Y los punteros tienen un tamaño conocido, por lo que se pueden almacenar convenientemente en arreglos de estilo C.
Hoy en clase, aprendimos que recuperar un elemento de una lista es O(1) en Python. ¿Por qué es este el caso? Supongamos que tengo una lista de cuatro elementos, por ejemplo:
li = ["perry", 1, 23.5, "s"]
Estos artículos tienen diferentes tamaños en memoria. Por lo tanto, no es posible tomar la ubicación de memoria de li[0] y agregar tres veces el tamaño de cada elemento para obtener la ubicación de memoria de li[3] . Entonces, ¿cómo sabe el intérprete dónde está li[3] sin tener que atravesar la lista para recuperar el elemento?
Respuesta corta: Las listas de Python son arrays.
Respuesta larga: la lista de términos informáticos generalmente significa una lista enlazada individualmente (como se usa en la programación funcional) o una lista enlazada doblemente (como se usa en la programación de procedimientos). Estas estructuras de datos admiten la inserción de O (1) en el encabezado de la lista (funcionalmente) o en cualquier posición que no sea necesario buscar (de manera procesal). Una "lista" de Python no tiene ninguna de estas características. En su lugar, admite (amortizado) O (1) adjuntando al final de la lista (como un C ++ std :: vector o Java ArrayList). Las listas de Python son arreglos realmente redimensionables en términos de CS.
El siguiente comentario de la documentación de Python explica algunas de las características de rendimiento de las "listas" de Python:
También es posible utilizar una lista como una cola, donde el primer elemento agregado es el primer elemento recuperado ("primero en entrar, primero en salir"); sin embargo, las listas no son eficientes para este propósito. Si bien los apéndices y los elementos emergentes del final de la lista son rápidos, hacer inserciones o elementos emergentes desde el principio de una lista es lento (porque todos los demás elementos deben desplazarse en uno).
Una lista en Python se implementa como una matriz de punteros 1 . Entonces, ¿qué sucede realmente cuando creas la lista?
["perry", 1, 23.5, "s"]
es que en realidad estás creando una serie de punteros así:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Cada puntero "apunta" a los objetos respectivos en la memoria, de modo que la cadena "perry" se almacenará en la dirección 0xa3d25342 y el número 1 se almacenará en 0x635423fa , etc.
Dado que todos los punteros son del mismo tamaño, el intérprete puede, de hecho, agregar 3 veces el tamaño de un elemento a la dirección de li[0] para llegar al puntero almacenado en li[3] .
1 Obtenga más detalles en: la boca del caballo (código fuente de CPython en GitHub) .