Bedste svar
I modsætning til hvad deres navn antyder, er Python-lister faktisk arrays, en kendsgerning der aldrig ophører med at irritere mig (jeg ved ikke “T kan lide vildledende navne). Specifikt er de dynamiske arrays med eksponentiel overallokering, som gør det muligt for kode som følgende at have lineær kompleksitet:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Interessant nok er overallokering i CPython er ekstremt konservativ, fordi den tildeler 1.125 * new\_size + 6 (eller + 3 når arrayet er mindre end 9 elementer). Denne 1.125 konstant er ret usædvanlig, og som sagt er den meget konservativ og synes således at antage den række af tilføje opkald er ikke så almindelige. Implementeringer af dynamiske arrays bruger normalt konstant som 2 eller 1.5 (jeg har lige tjekket implementeringen af std :: vector i gcc / clang og den bruger 2, jeg ser ud til at huske Microsofts kompilators implementering bruger 1,5 ). Jeg ved ikke, hvor + 3 og + 6 konstanten kommer fra, men mit gæt er, at den, der skrev dette, på en eller anden måde fandt ud af, at + 3 var den bedste politik at have for små arrays, at + 6 var bedst for ret små arrays ( siger mindre end 100), og at det overhovedet ikke betyder noget for store arrays, så hvorfor ikke bare beholde det.
Alternative implementeringer som Jython og IronPython ser ud til at bruge den indfødte dynamiske array-klasse, der er deres underliggende sprog (henholdsvis Java og C #) leverer, så de har de samme præstationsegenskaber (de nøjagtige underliggende klasser synes at være ArrayList for Jython og C # List for IronPython).
Nogen spurgte i kommentarerne, hvordan det var muligt at have arrays af elementer af heterogene typer ([1, “hej”] er en gyldig liste i Python). Svaret på dette spørgsmål er, at arrays teknisk gemmer markører snarere end objekterne selv, hvilket gør det muligt for arrayet kun at indeholde elementer af en bestemt størrelse. At have henvisninger overalt i den underliggende implementering er et almindeligt træk ved dynamisk typede sprog, og faktisk på ethvert sprog, der forsøger at lade som om det ikke har markører.
Svar
Som sagt af Adrien Lucas Ecoffet, er pythonlister intet andet end arrays med variabel længde. Jeg graver i kildekoden til cpython og udvider makroen, den grundlæggende struktur er defineret som:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Jeg har beskåret kommentarerne her, henvis til originalen kode her. 6c2e2de5ab8e Inkluder / listobject.h
PyObject\_VAR\_HEAD indeholder et referencetal og en typeidentifikator. Så det er en vektor / matrix at over tildeler. Koden til ændring af størrelsen på en sådan matrix, når den er fuld, er i listobject.c . Den tildeler hukommelse for meget for at undgå at kalde listen\_resize for meget tid. på listen er: 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
For at se alle de listede metoder til implementering af Python-lister, inklusive tilføj, indsæt, fjern, udvid og andre, se dette fremragende blogindlæg.