Melhor resposta
Ao contrário do que o nome indica, as listas Python são, na verdade, matrizes, um fato que nunca para de me incomodar (eu não “como nomes enganosos). Especificamente, são matrizes dinâmicas com superalocação exponencial, o que permite que códigos como os seguintes tenham complexidade linear:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Curiosamente, superalocação em CPython é extremamente conservador, porque aloca 1.125 * new\_size + 6 (ou + 3 quando o array é menor que 9 elementos). Essa constante de 1.125 é bastante incomum e, como eu disse, é muito conservadora e, portanto, parece assumir que a série de chamadas de acréscimo não são comuns. Implementações de matrizes dinâmicas geralmente usam constantes como 2 ou 1.5 (acabei de verificar a implementação de std :: vector em gcc / clang e usa 2, acho que me lembro que a implementação do compilador da Microsoft usa 1.5 ) Eu não sei de onde as constantes + 3 e + 6 vieram, mas meu palpite é que quem escreveu isso de alguma forma descobriu que + 3 era a melhor política para ter pequenos arrays, que + 6 era melhor para arrays bem pequenos ( digamos, menos de 100) e que realmente não importava para grandes arrays, então por que não apenas mantê-lo.
Implementações alternativas como Jython e IronPython parecem usar qualquer classe de matriz dinâmica nativa de sua base linguagem (respectivamente Java e C #) fornece, então eles têm as mesmas características de desempenho (as classes subjacentes precisas parecem ser ArrayList para Jython e C # List para IronPython).
Alguém perguntou nos comentários como isso era possível ter matrizes de elementos de tipos heterogêneos ([1, “olá”] é uma lista válida em Python). A resposta a essa pergunta é que os arrays armazenam tecnicamente ponteiros em vez dos próprios objetos, o que permite que o array contenha apenas elementos de um tamanho específico. Ter ponteiros em todos os lugares na implementação subjacente é um recurso comum de linguagens tipadas dinamicamente e, na verdade, de qualquer linguagem que tenta fingir que não tem ponteiros.
Resposta
Como disse Adrien Lucas Ecoffet, as listas python nada mais são do que arrays de comprimento variável. Eu procuro no código-fonte do cpython e, expandindo a macro, a estrutura básica é definida como:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Limpei os comentários aqui, consulte o original codifique aqui. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD contém uma contagem de referência e um identificador de tipo. Portanto, é um vetor / matriz que superaloca. O código para redimensionar tal array quando estiver cheio está em listobject.c . Ele superaloca memória para evitar chamar list\_resize muitas vezes. O padrão de crescimento da lista é: 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 os métodos listados de implementação de listas Python, incluindo anexar, inserir, remover, estender e outros, consulte esta excelente postagem no blog.