La mejor respuesta
Al contrario de lo que su nombre implica, las listas de Python son en realidad matrices, un hecho que nunca deja de molestarme (no «No me gustan los nombres engañosos). Específicamente, son matrices dinámicas con una sobreasignación exponencial, lo que permite que código como el siguiente tenga una complejidad lineal:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Curiosamente, la sobreasignación en CPython es extremadamente conservador, porque asigna 1.125 * new\_size + 6 (o + 3 cuando la matriz es menor que 9 elementos). Esa constante 1.125 es bastante poco común y, como dije, es muy conservadora y, por lo tanto, parece asumir que la serie de Las llamadas anexas no son tan comunes. Las implementaciones de matrices dinámicas usualmente usan constantes como 2 o 1.5 (acabo de verificar la implementación de std :: vector en gcc / clang y usa 2, creo recordar que la implementación del compilador de Microsoft usa 1.5 ). No sé de dónde provienen las constantes + 3 y + 6, pero supongo que quienquiera que haya escrito esto de alguna manera descubrió que + 3 era la mejor política para las matrices pequeñas, que + 6 era la mejor para matrices bastante pequeñas ( digamos, menos de 100) y que realmente no importaba en absoluto para arreglos grandes, así que ¿por qué no mantenerlo?
Las implementaciones alternativas como Jython y IronPython parecen usar cualquier clase de arreglo dinámico nativo que sea su subyacente (respectivamente Java y C #) proporciona, por lo que tienen las mismas características de rendimiento (las clases subyacentes precisas parecen ser ArrayList para Jython y C # List para IronPython).
Alguien preguntó en los comentarios cómo era posible tener matrices de elementos de tipos heterogéneos ([1, «hola»] es una Lista válida en Python). La respuesta a esa pregunta es que las matrices almacenan técnicamente punteros en lugar de los objetos en sí mismos, lo que permite que la matriz contenga solo elementos de un tamaño específico. Tener punteros por todas partes en la implementación subyacente es una característica común de los lenguajes tipados dinámicamente y, de hecho, de cualquier idioma que intente fingir que no tiene punteros.
Respuesta
Como dijo Adrien Lucas Ecoffet, las listas de python no son más que matrices de longitud variable. Busco en el código fuente de cpython y, al expandir la macro, la estructura básica se define como:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
He eliminado los comentarios aquí, consulte el original código aquí. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD contiene un recuento de referencias y un identificador de tipo. que sobreasigna. El código para cambiar el tamaño de una matriz de este tipo cuando «está llena está en listobject.c . Sobreasigna memoria para evitar llamar a list\_resize demasiado tiempo. El patrón de crecimiento de la lista es: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
Para ver todos los métodos enumerados de implementación de listas de Python, incluidos agregar, insertar, eliminar, extender y otros, consulte esta excelente publicación de blog.