Beste svaret
I motsetning til hva navnet deres tilsier, er Python-lister faktisk arrays, et faktum som aldri slutter å irritere meg (jeg vet ikke «Liker ikke villedende navn). Spesielt er de dynamiske matriser med eksponentiell overallokering, som gjør at kode som følgende har 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 * ny\_størrelse + 6 (eller + 3 når matrisen er mindre enn 9 elementer). Den 1.125-konstanten er ganske uvanlig, og som sagt er den veldig konservativ og ser ut til å anta den serien av vedleggsanrop er ikke så vanlig. Implementeringer av dynamiske matriser bruker vanligvis konstant som 2 eller 1.5 (jeg har nettopp sjekket implementeringen av std :: vector i gcc / clang og den bruker 2, jeg ser ut til å huske at Microsoft-kompilatorens implementering bruker 1,5 ). Jeg vet ikke hvor + 3 og + 6 konstanten kom fra, men jeg antar at den som skrev dette på en eller annen måte fant ut at + 3 var den beste policyen å ha for små matriser, at + 6 var best for ganske små matriser ( si mindre enn 100) og at det egentlig ikke gjaldt for store matriser, så hvorfor ikke bare beholde det.
Alternative implementeringer som Jython og IronPython ser ut til å bruke den innfødte dynamiske arrayklassen som ligger til grunn for deres underliggende språk (henholdsvis Java og C #) gir, så de har de samme ytelsesegenskapene (de nøyaktige underliggende klassene ser ut til å være ArrayList for Jython og C # List for IronPython).
Noen spurte i kommentarene hvordan det var mulig å ha matriser av elementer av heterogene typer ([1, «hei»] er en gyldig liste i Python). Svaret på det spørsmålet er at matriser teknisk lagrer pekere i stedet for objektene i seg selv, noe som gjør at matrisen kun inneholder elementer av en bestemt størrelse. Å ha pekere overalt i den underliggende implementeringen er et vanlig trekk ved dynamisk typede språk, og faktisk på ethvert språk som prøver å late som om det ikke har noen pekere.
Svar
Som sagt av Adrien Lucas Ecoffet, er pythonlister ikke annet enn matriser med variabel lengde. Jeg graver i kildekoden til cpython, og utvider makroen, den grunnleggende strukturen er definert som:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Jeg har beskåret kommentarene her, referer til originalen kode her. 6c2e2de5ab8e Inkluder / listobject.h
PyObject\_VAR\_HEAD inneholder et referansetall og en typeidentifikator. Så det er en vektor / matrise som over tildeler. Koden for å endre størrelse på en slik matrise når den er full er i listobject.c . Den tildeler minne for mye for å unngå å ringe listen\_resize for mye tid. av 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 å se alle de listede metodene for implementering av Python-lister, inkludert legge til, sette inn, fjerne, utvide og andre, se dette utmerkede blogginnlegget.