¿Cómo se implementa la lista de Python?
¿Es una lista enlazada, una matriz? Busqué por ahí y solo encontré gente adivinando. Mi conocimiento de C no es lo suficientemente bueno como para mirar el código fuente.
En realidad, el código C es bastante simple. Al expandir una macro y eliminar algunos comentarios irrelevantes, la estructura básica está en listobject.h, que define una lista como:
typedef struct {
PyObject_HEAD
Py_ssize_t ob_size;
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
*/
Py_ssize_t allocated;
} PyListObject;
PyObject_HEADcontiene un recuento de referencia y un identificador de tipo. Entonces, es un vector/matriz que sobreasigna. El código para cambiar el tamaño de dicha matriz cuando está llena está en listobject.c. En realidad, no duplica la matriz, sino que crece asignando
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;
a la capacidad cada vez, donde newsizeestá el tamaño solicitado (no necesariamente allocated + 1porque puede hacerlo extendcon un número arbitrario de elementos en lugar de appendhacerlos uno por uno).
Consulte también las preguntas frecuentes sobre Python .
Es una matriz dinámica . Prueba práctica: la indexación lleva (por supuesto, con diferencias extremadamente pequeñas (¡0,0013 µs!)) el mismo tiempo independientemente del índice:
...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop
...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop
Me sorprendería si IronPython o Jython usaran listas enlazadas: arruinarían el rendimiento de muchas bibliotecas ampliamente utilizadas creadas bajo el supuesto de que las listas son matrices dinámicas.
Oct 12 '2010 18:10
Sugeriría el artículo de Laurent Luce "Implementación de la lista de Python" . Fue realmente útil para mí porque el autor explica cómo se implementa la lista en CPython y utiliza excelentes diagramas para este propósito.
Estructura de lista de objetos C
Un objeto de lista en CPython está representado por la siguiente estructura C.
ob_itemes una lista de punteros a los elementos de la lista. asignado es el número de ranuras asignadas en la memoria.typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject;Es importante notar la diferencia entre los espacios asignados y el tamaño de la lista. El tamaño de una lista es el mismo que
len(l). El número de ranuras asignadas es lo que se ha asignado en la memoria. A menudo verás que el tamaño asignado puede ser mayor que el tamaño. Esto es para evitar la necesidad de llamarrealloccada vez que se agrega un nuevo elemento a la lista.
...
Adjuntar
Agregamos un número entero a la lista:
l.append(1). ¿Lo que sucede?
Seguimos añadiendo un elemento más:
l.append(2).list_resizese llama con n+1 = 2 pero debido a que el tamaño asignado es 4, no hay necesidad de asignar más memoria. Lo mismo sucede cuando sumamos 2 números enteros más:l.append(3),l.append(4). El siguiente diagrama muestra lo que tenemos hasta ahora.
...
Insertar
Insertemos un nuevo número entero (5) en la posición 1:
l.insert(1,5)y observemos lo que sucede internamente.
...
Estallido
Cuando sacas el último elemento:
l.pop(),listpop()se llama.list_resizese llama adentrolistpop()y si el nuevo tamaño es menor que la mitad del tamaño asignado, entonces la lista se reduce.Puedes observar que la ranura 4 todavía apunta al número entero, pero lo importante es el tamaño de la lista que ahora es 4. Extraigamos un elemento más. En
list_resize(), el tamaño – 1 = 4 – 1 = 3 es menos de la mitad de los espacios asignados, por lo que la lista se reduce a 6 espacios y el nuevo tamaño de la lista ahora es 3.Puede observar que las ranuras 3 y 4 todavía apuntan a algunos números enteros, pero lo importante es el tamaño de la lista, que ahora es 3.
...
Eliminar objeto de lista de Python tiene un método para eliminar un elemento específico:
l.remove(5).
