Migliore risposta
Contrariamente a quanto suggerisce il loro nome, le liste Python sono in realtà array, un fatto che non smette mai di infastidirmi (non “mi piacciono i nomi fuorvianti). In particolare, sono array dinamici con sovrallocazione esponenziale, che consente a codice come il seguente di avere complessità lineare:
lst = []
for i in xrange(0, 100000):
lst.append(i)
È interessante notare che leccessiva allocazione in CPython è estremamente conservativo, perché alloca 1.125 * new\_size + 6 (o + 3 quando larray è più piccolo di 9 elementi). Quella costante 1.125 è piuttosto rara e, come ho detto, è molto conservativa e quindi sembra assumere quella serie di le chiamate append non sono così comuni. Le implementazioni di array dinamici di solito usano costanti come 2 o 1.5 (ho appena controllato limplementazione di std :: vector in gcc / clang e usa 2, mi sembra di ricordare che limplementazione del compilatore Microsoft usa 1.5 ). Non so da dove provengano le costanti + 3 e + 6, ma la mia ipotesi è che chiunque labbia scritto in qualche modo abbia scoperto che + 3 era la migliore politica da avere per piccoli array, che + 6 era il migliore per array piuttosto piccoli ( diciamo, meno di 100) e che in realtà non importava affatto per i grandi array, quindi perché non tenerlo.
Implementazioni alternative come Jython e IronPython sembrano usare qualunque classe di array dinamico nativo loro sottostante linguaggio (rispettivamente Java e C #) fornito, quindi hanno le stesse caratteristiche prestazionali (le classi sottostanti precise sembrano essere ArrayList per Jython e C # List per IronPython).
Qualcuno nei commenti ha chiesto come sia stato possibile avere array di elementi di tipi eterogenei ([1, “ciao”] è un elenco valido in Python). La risposta a questa domanda è che gli array memorizzano tecnicamente i puntatori piuttosto che gli oggetti stessi, il che consente allarray di contenere solo elementi di una dimensione specifica. Avere puntatori ovunque nellimplementazione sottostante è una caratteristica comune dei linguaggi tipizzati dinamicamente, e in effetti di qualsiasi linguaggio che cerca di fingere di non avere puntatori.
Risposta
Come detto da Adrien Lucas Ecoffet, gli elenchi di python non sono altro che array di lunghezza variabile. Scavo nel codice sorgente di cpython e, espandendo la macro, la struttura di base è definita come:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Ho ridotto i commenti qui, fai riferimento alloriginale codice qui. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD contiene un conteggio dei riferimenti e un identificatore di tipo. Quindi, “un vettore / matrice che oltre alloca. Il codice per ridimensionare un array di questo tipo quando è pieno si trova in listobject.c . Alloca eccessivamente la memoria per evitare di chiamare list\_resize troppe volte. Il modello di crescita dellelenco è: 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
Per vedere tutti i metodi elencati di implementazione di elenchi di elenchi Python, inclusi aggiungere, inserire, rimuovere, estendere e altri, fare riferimento a questo eccellente post sul blog.