Cel mai bun răspuns
Contrar a ceea ce implică numele lor, listele Python sunt de fapt tablouri, fapt care nu încetează să mă enerveze „Nu-mi plac numele înșelătoare). În mod specific, sunt tablouri dinamice cu supraalocare exponențială, care permite codului ca următoarele să aibă complexitate liniară:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Interesant, supraalocarea în CPython este extrem de conservator, deoarece alocă 1.125 * new\_size + 6 (sau + 3 când matricea este mai mică de 9 elemente). Această constantă 1.125 este destul de neobișnuită și, așa cum am spus, este foarte conservatoare și, astfel, pare să presupună că seria Apelați apelurile nu sunt atât de obișnuite. Implementările matricelor dinamice folosesc de obicei constantă ca 2 sau 1.5 (tocmai am verificat implementarea std :: vector în gcc / clang și folosește 2, parcă îmi amintesc că implementarea compilatorului Microsoft utilizează 1.5 ). Nu știu de unde a venit constanta + 3 și + 6, dar presupun că oricine a scris acest lucru a aflat cumva că + 3 a fost cea mai bună politică pentru matrice mici, că + 6 a fost cel mai bun pentru tablouri destul de mici ( să spunem, mai puțin de 100) și că într-adevăr nu a contat deloc pentru matricele mari, așa că de ce să nu o păstrăm.
Implementările alternative precum Jython și IronPython par să folosească orice clasă de matrice dinamică nativă care stau la baza lor limbajul (respectiv Java și C #) oferă, deci au aceleași caracteristici de performanță (clasele subiacente precise par a fi ArrayList pentru Jython și C # List pentru IronPython).
Cineva a întrebat în comentarii cum a fost posibil a avea matrici de elemente de tipuri eterogene ([1, „salut”] este o listă validă în Python). Răspunsul la această întrebare este că matricea stochează punctele tehnice mai degrabă decât obiectele în sine, ceea ce permite matricei să conțină doar elemente de o dimensiune specifică. A avea indicii peste tot în implementarea subiacentă este o caracteristică comună a limbajelor tipizate dinamic și, de fapt, a oricărui limbaj care încearcă să pretindă că nu are indicatori.
Răspuns
Așa cum a spus Adrien Lucas Ecoffet, listele de python nu sunt altceva decât tablouri cu lungime variabilă. Am săpat în codul sursă al cpython și extind macro-ul, structura de bază este definită ca:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Am tăiat comentariile aici, consultați originalul cod aici. 6c2e2de5ab8e Include / listobject.h
PyObject\_VAR\_HEAD conține un număr de referințe și un identificator de tip. Deci, acesta este un vector / matrice că peste alocă. Codul pentru redimensionarea unei astfel de matrice atunci când este complet este în listobject.c . Alocă în exces memoria pentru a evita apelarea list\_resize prea mult timp. Modelul de creștere din listă este: 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
Pentru a vedea toate metodele listate de implementare a listelor Python, inclusiv adăugați, inserați, eliminați, extindeți și altele, vă rugăm să consultați această postare excelentă pe blog.