Beste antwoord
In tegenstelling tot wat hun naam suggereert, zijn Python-lijsten eigenlijk arrays, een feit dat me altijd blijft irriteren (ik don “niet zoals misleidende namen). Het zijn met name dynamische arrays met exponentiële overtoewijzing, waardoor code zoals de volgende lineaire complexiteit kan hebben:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Interessant is dat overtoewijzing in CPython is extreem conservatief, omdat het 1,125 * new\_size + 6 toekent (of + 3 als de array kleiner is dan 9 elementen). Die constante van 1,125 is nogal ongebruikelijk, en zoals ik al zei is het erg conservatief en lijkt het dus aan te nemen dat de reeks van append-aanroepen zijn niet zo gebruikelijk. Implementaties van dynamische arrays gebruiken meestal constant zoals 2 of 1.5 (ik heb zojuist de implementatie van std :: vector in gcc / clang gecontroleerd en het gebruikt 2, ik meen me te herinneren dat de implementatie van de Microsoft-compiler 1.5 gebruikt ). Ik weet niet waar de constante + 3 en + 6 vandaan kwamen, maar ik vermoed dat degene die dit heeft geschreven op de een of andere manier heeft ontdekt dat + 3 het beste beleid was voor kleine arrays, dat + 6 het beste was voor vrij kleine arrays ( laten we zeggen, minder dan 100) en dat het helemaal niets uitmaakte voor grote arrays, dus waarom zou je het niet gewoon houden.
Alternatieve implementaties zoals Jython en IronPython lijken elke native dynamische array-klasse te gebruiken die hun onderliggende taal (respectievelijk Java en C #) biedt, dus ze hebben dezelfde prestatiekenmerken (de precieze onderliggende klassen lijken ArrayList voor Jython en C # List voor IronPython te zijn).
Iemand vroeg in de reacties hoe het mogelijk was arrays van elementen van heterogene typen hebben ([1, “hallo”] is een geldige lijst in Python). Het antwoord op die vraag is dat de arrays technisch gezien pointers opslaan in plaats van de objecten zelf, waardoor de array alleen elementen van een bepaalde grootte kan bevatten. Overal aanwijzers hebben in de onderliggende implementatie is een veelvoorkomend kenmerk van dynamisch getypeerde talen, en in feite van elke taal die probeert te doen alsof het geen verwijzingen heeft.
Antwoord
Zoals gezegd door Adrien Lucas Ecoffet, python-lijsten zijn niets anders dan arrays met variabele lengte. Ik verdiep me in de broncode van cpython en als ik de macro uitbreid, wordt de basisstructuur gedefinieerd als:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Ik heb de opmerkingen hier opgeschoond, verwijs naar het origineel code hier. 6c2e2de5ab8e include / listobject.h
PyObject\_VAR\_HEAD bevat een referentietelling en een type-ID. Het is dus een vector / array dat te veel toewijst. De code voor het wijzigen van de grootte van een dergelijke array wanneer deze “vol is, bevindt zich in listobject.c . Er wordt te veel geheugen toegewezen om te voorkomen dat list\_resize te veel tijd wordt aangeroepen. Het groeipatroon van de lijst is: 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
Raadpleeg deze uitstekende blogpost om alle vermelde methoden voor de lijst met implementatie van Python-lijsten te zien, inclusief toevoegen, invoegen, verwijderen, uitbreiden en andere.