¿Cómo se implementa la lista de Python?

arrays linked-list

Question

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

Answer 1

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

Para entender por qué el método es O (1) amortizado, sin pérdida de generalidad, supongamos que hemos insertado a = 2 ^ n elementos, y ahora tenemos que duplicar nuestra tabla a 2 ^ (n + 1) tamaño. Eso significa que actualmente estamos haciendo 2 ^ (n + 1) operaciones. Última copia, hicimos 2 ^ n operaciones. Antes de eso hicimos 2 ^ (n-1) ... todo el camino hasta 8,4,2,1. Ahora, si sumamos esto, 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 hacerse en un factor diferente (p. Ej., 3x)

Answer 2

De acuerdo con la documentation ,

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

Answer 3

El código C es bastante simple, en realidad. Ampliando una macro y podando 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_HEAD contiene un recuento de referencias y un identificador de tipo. Entonces, es un vector / matriz que sobreasigna. El código para cambiar el tamaño de una matriz cuando está lleno está en listobject.c . En realidad, no duplica el conjunto, pero crece asignando

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

a la capacidad cada vez, donde newsize es el tamaño solicitado (no necesariamente allocated + 1 porque puede extend por un número arbitrario de elementos en lugar de append uno por uno).

Ver también las docs.python.org/2/faq/design.html#how-are-lists-implemented .

Answer 4

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

Answer 5

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

Answer 6

Esto depende de la implementación, pero IIRC:

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

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

Answer 7

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.

Lista objeto C estructura

Un objeto de lista en CPython está representado por la siguiente estructura C. ob_item es 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 asignado;

} PyListObject;

Es importante notar la diferencia entre las ranuras asignadas 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 la asignación puede ser mayor que el tamaño. Esto es para evitar tener que llamar a realloc cada vez que se añaden nuevos elementos a la lista.

...

Adjuntar

Agregamos un número entero a la lista: l.append (1). ¿Lo que pasa?

Continuamos agregando un elemento más: l.append (2). list_resize se llama con n + 1 = 2, pero dado que el tamaño asignado es 4, no hay necesidad de 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

Inserte un nuevo entero (5) en la posición 1: l.insert (1,5) y observe lo que sucede internamente.

...

Popular

Cuando aparece el último elemento: l.pop (), se llama a listpop (). list_resize se llama inside listpop () y si el nuevo tamaño es menor que la mitad del tamaño asignado, la lista se reduce.

Puede observar que la ranura 4 aún apunta al 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 las ranuras asignadas por lo que la lista se reduce a 6 ranuras y el nuevo tamaño de la lista es ahora 3.

Puede observar que las ranuras 3 y 4 aún apuntan a algunos enteros, pero lo importante es el tamaño de la lista que ahora es 3.

...

Remove Python list object tiene un método para eliminar un elemento específico: l.remove (5).