Como a lista do Python é implementada?

É uma lista vinculada, uma matriz? Eu procurei e só encontrei pessoas adivinhando. Meu conhecimento em C não é bom o suficiente para examinar o código fonte.

É uma matriz dinâmica . Prova prática: a indexação leva (obviamente com diferenças extremamente pequenas (0,0013 µseg!)) Ao mesmo tempo, independentemente do í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

Eu ficaria surpreso se o IronPython ou o Jython usassem listas vinculadas - elas arruinariam o desempenho de muitas bibliotecas amplamente usadas, construídas com a suposição de que as listas são matrizes dinâmicas.

O código C é bem simples, na verdade. Expandindo uma macro e removendo alguns comentários irrelevantes, está a estrutura básica listobject.h, que define uma 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_HEADcontém uma contagem de referência e um identificador de tipo. Portanto, é um vetor / array que atribui uma classificação geral. O código para redimensionar um array tal quando está cheia está em listobject.c. Na verdade, ele não duplica a matriz, mas cresce alocando

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

de acordo com a capacidade de cada vez, onde newsizeestá o tamanho solicitado (não necessariamente allocated + 1porque você pode, extendpor um número arbitrário de elementos, em vez de appendselecioná-los um por um).

Veja também as Perguntas frequentes sobre Python .

No CPython, listas são matrizes de ponteiros. Outras implementações do Python podem optar por armazená-las de maneiras diferentes.

Isso depende da implementação, mas o IIRC:

• CPython usa uma matriz de ponteiros
• O Jython usa um ArrayList
• Aparentemente, o IronPython também usa uma matriz. Você pode procurar o código fonte para descobrir.

Assim, todos eles têm acesso aleatório O (1).

Eu sugeriria o artigo de Laurent Luce "Implementação da lista Python" . Foi realmente útil para mim, porque o autor explica como a lista é implementada no CPython e usa excelentes diagramas para esse fim.

Estrutura do objeto C de lista

Um objeto de lista no CPython é representado pela seguinte estrutura C. ob_itemé uma lista de ponteiros para os elementos da lista. alocado é o número de slots alocados na memória.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

É importante observar a diferença entre os slots alocados e o tamanho da lista. O tamanho de uma lista é o mesmo que len(l). O número de slots alocados é o que foi alocado na memória. Frequentemente, você verá que o alocado pode ser maior que o tamanho. Isso evita a necessidade de chamar realloccada vez que um novo elemento é anexado à lista.

...

Acrescentar

Anexamos um inteiro para a lista: l.append(1). O que acontece?

Continuamos adicionando um elemento a mais: l.append(2). list_resizeé chamado com n + 1 = 2, mas como o tamanho alocado é 4, não há necessidade de alocar mais memória. O mesmo acontece quando adicionamos mais 2 números inteiros: l.append(3), l.append(4). O diagrama a seguir mostra o que temos até agora.

...

Inserir

Vamos inserir um novo número inteiro (5) na posição 1: l.insert(1,5)e ver o que acontece internamente.

...

Pop

Quando você coloca o último elemento: l.pop(), listpop()é chamado. list_resizeé chamado dentro listpop()e se o novo tamanho for menor que a metade do tamanho alocado, a lista será reduzida.

Você pode observar que o slot 4 ainda aponta para o número inteiro, mas o importante é o tamanho da lista que agora é 4. Vamos exibir mais um elemento. Em list_resize(), size - 1 = 4 - 1 = 3 é menos da metade dos slots alocados, portanto a lista é reduzida para 6 slots e o novo tamanho da lista agora é 3.

Você pode observar que os slots 3 e 4 ainda apontam para alguns números inteiros, mas o importante é o tamanho da lista, que agora é 3.

...

Remover Python lista objeto tem um método para remover um elemento específico: l.remove(5).

De acordo com a documentação ,

As listas do Python são realmente matrizes de tamanho variável, não listas vinculadas no estilo Lisp.

Como já mencionado anteriormente, as listas (quando consideravelmente grandes) são implementadas alocando uma quantidade fixa de espaço e, se esse espaço for preenchido, alocando uma quantidade maior de espaço e copiando os elementos.

Para entender por que o método é O (1) amortizado, sem perda de generalidade, assuma que inserimos a = 2 ^ n elementos e agora precisamos dobrar nossa tabela para 2 ^ (n + 1). Isso significa que atualmente estamos realizando 2 ^ (n + 1) operações. Última cópia, fizemos 2 ^ n operações. Antes disso, fizemos 2 ^ (n-1) ... até 8,4,2,1. Agora, se somarmos isso, obtemos 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) total de inserções (ou seja, O (1) tempo amortizado). Além disso, deve-se notar que, se a tabela permitir exclusões, a redução da tabela deverá ser feita em um fator diferente (por exemplo, 3x)

Uma lista no Python é algo como uma matriz, na qual você pode armazenar vários valores. A lista é mutável, o que significa que você pode alterá-la. O mais importante que você deve saber, quando criamos uma lista, o Python cria automaticamente um reference_id para essa variável de lista. Se você a alterar atribuindo outras variáveis, a lista principal será alterada. Vamos tentar com um exemplo:

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_listmas nossa lista principal mudou. A lista desse meio não atribuiu como uma lista de cópias atribuir como referência.

No CPython, a lista é implementada como matriz dinâmica e, portanto, quando acrescentamos naquele momento, não apenas uma macro é adicionada, mas um pouco mais de espaço é alocado, de modo que toda vez que um novo espaço não deve ser adicionado.