¿Cómo se implementa la lista de Python?

¿Es una lista vinculada, una matriz? Busqué alrededor y solo encontré personas adivinando. Mi conocimiento de C no es lo suficientemente bueno como para mirar el código fuente.

Es una matriz dinámica . Prueba práctica: la indexación lleva (por supuesto, con diferencias extremadamente pequeñas (¡0.0013 µsecs!)) 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 que IronPython o Jython usaran listas vinculadas: arruinarían el rendimiento de muchas bibliotecas ampliamente utilizadas basadas en el supuesto de que las listas son matrices dinámicas.

El código C es bastante simple, en realidad. Al expandir una macro y eliminar algunos comentarios irrelevantes, se encuentra la estructura básica 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 se sobreasigna. El código para cambiar el tamaño de dicha matriz cuando está lleno 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 extendpor un número arbitrario de elementos en lugar de append'uno por uno).

Consulte también las preguntas frecuentes de Python .

En CPython, las listas son matrices de punteros. Otras implementaciones de Python pueden optar por almacenarlas de diferentes maneras.

Esto depende de la implementación, pero IIRC:

• CPython usa una variedad de punteros
• Jython usa un ArrayList
• IronPython aparentemente también usa una matriz. Puede buscar el código fuente para averiguarlo.

Por lo tanto, todos tienen acceso aleatorio O (1).

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.

Listar la estructura del objeto C

Un objeto de lista en CPython está representado por la siguiente estructura en 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á que asignado puede ser mayor que el tamaño. Esto es para evitar la necesidad de llamar realloccada vez que se agregan nuevos elementos a la lista.

...

Adjuntar

Añadimos un entero a la lista: l.append(1). ¿Lo que pasa?

Seguimos añadiendo un elemento más: l.append(2). list_resizese llama con n + 1 = 2 pero como el tamaño asignado es 4, no es necesario asignar más memoria. Lo mismo sucede cuando agregamos 2 enteros más: l.append(3), l.append(4). El siguiente diagrama muestra lo que tenemos hasta ahora.

...

Insertar

Insertemos un nuevo entero (5) en la posición 1: l.insert(1,5)y veamos qué sucede internamente.

...

Popular

Cuando usted hace estallar el último elemento: l.pop(), listpop()se llama. list_resizese llama dentro listpop()y si el nuevo tamaño es inferior a la mitad del tamaño asignado, la lista se reduce.

Puede 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. Hagamos estallar un elemento más. En list_resize(), size - 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 los espacios 3 y 4 todavía apuntan a algunos enteros, pero lo importante es el tamaño de la lista que ahora es 3.

...

Retire la lista de objetos Python tiene un método para eliminar un elemento específico: l.remove(5).

De acuerdo con la documentación ,

Las listas de Python son realmente matrices de longitud variable, no listas enlazadas al estilo Lisp.

Como otros han dicho anteriormente, las listas (cuando son apreciablemente grandes) se implementan asignando una cantidad fija de espacio y, si ese espacio debe llenar, asignando una mayor cantidad de espacio y copiando los elementos.

Para entender por qué el método está O (1) amortizado, sin pérdida de generalidad, supongamos que hemos insertado elementos a = 2 ^ n, y ahora tenemos que duplicar nuestra tabla al tamaño 2 ^ (n + 1). Eso significa que actualmente estamos haciendo 2 ^ (n + 1) operaciones. Última copia, hicimos 2 ^ n operaciones. Antes de eso hicimos 2 ^ (n-1) ... hasta 8,4,2,1. Ahora, si sumamos estos, obtenemos 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) inserciones totales (es decir, O (1) tiempo amortizado). Además, debe tenerse en cuenta que si la tabla permite eliminaciones, la reducción de la tabla debe realizarse en un factor diferente (por ejemplo, 3x)

Una lista en Python es algo así como una matriz, donde puede almacenar múltiples valores. La lista es mutable, lo que significa que puede cambiarla. Lo más importante que debe saber, cuando creamos una lista, Python crea automáticamente una referencia_id para esa variable de lista. Si lo cambia asignando otras variables, la lista principal cambiará. Probemos con un ejemplo:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Anexamos my_listpero nuestra lista principal ha cambiado. La lista de esa media no se asignó como una lista de copia asignada como referencia.

En CPython, la lista se implementa como matriz dinámica y, por lo tanto, cuando agregamos en ese momento, no solo se agrega una macro, sino que se asigna algo más de espacio para que cada vez no se agregue un nuevo espacio.