Bästa svaret
I motsats till vad deras namn antyder är Python-listor faktiskt arrays, ett faktum som aldrig slutar irritera mig (jag vet inte ”Gillar inte vilseledande namn). Specifikt är de dynamiska matriser med exponentiell överallokering, vilket gör att kod som följande har linjär komplexitet:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Intressant, överallokering i CPython är extremt konservativ eftersom den tilldelar 1.125 * ny\_storlek + 6 (eller + 3 när matrisen är mindre än 9 element). Den 1.125-konstanten är ganska ovanlig, och som sagt är den väldigt konservativ och verkar således anta den serien av bifoga samtal är inte så vanliga. Implementeringar av dynamiska matriser använder vanligtvis konstanta som 2 eller 1.5 (jag kollade bara implementeringen av std :: vector i gcc / clang och den använder 2, jag verkar komma ihåg att Microsoft-kompilatorns implementering använder 1,5 ). Jag vet inte var + 3 och + 6 konstanten kommer ifrån, men min gissning är att den som skrev detta på något sätt upptäckte att + 3 var den bästa policyn att ha för små matriser, att + 6 var bäst för ganska små matriser ( säg mindre än 100) och att det egentligen inte spelade någon roll alls för stora matriser, så varför inte bara behålla det.
Alternativa implementeringar som Jython och IronPython verkar använda vilken nativ dynamisk matrisklass som är deras underliggande språk (respektive Java och C #) tillhandahåller, så de har samma prestandaegenskaper (de exakta underliggande klasserna verkar vara ArrayList för Jython och C # List för IronPython).
Någon frågade i kommentarerna hur det var möjligt att ha matriser med element av heterogena typer ([1, ”hej”] är en giltig lista i Python). Svaret på den frågan är att matriserna tekniskt lagrar pekare snarare än själva objekten, vilket gör att matrisen endast kan innehålla element av en viss storlek. Att ha pekare överallt i den underliggande implementeringen är ett vanligt inslag i dynamiskt skrivna språk, och i själva verket på alla språk som försöker låtsas att det inte har några pekare.
Svar
Som sagt av Adrien Lucas Ecoffet är pythonlistor inget annat än arrayer med variabel längd. Jag gräver i källkoden till cpython och utvidgar makrot, grundstrukturen definieras som:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Jag har beskurit kommentarerna här, hänvisa till originalet kod här. 6c2e2de5ab8e Inkludera / listobject.h
PyObject\_VAR\_HEAD innehåller ett referensantal och en typidentifierare. Så det är en vektor / array som över tilldelar. Koden för att ändra storlek på en sådan matris när den är full finns i listobject.c . Den överfördelar minne för att undvika att anropa list\_resize för mycket tid. i listan är: 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
För att se alla listade metoder för implementering av Python-listor, inklusive bifoga, infoga, ta bort, förläng och andra, se detta utmärkta blogginlägg.