Legjobb válasz
A nevükkel ellentétben a Python-listák valójában tömbök, ez a tény soha nem szűnt meg bosszantani (én nem “nem kedvelik a megtévesztő neveket). Pontosabban, ezek dinamikus tömbök, exponenciális túlallokációval, amely lehetővé teszi az alábbiakhoz hasonló kódok lineáris komplexitását:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Érdekes módon túlzott allokáció A CPython rendkívül konzervatív, mert 1,125 * új\_méret + 6-ot (vagy + 3-ot rendel, ha a tömb 9 elemnél kisebb). Ez az 1,125-es konstans meglehetősen ritka, és mint mondtam, nagyon konzervatív, és úgy tűnik, feltételezi azt az A hívások hozzáfűzése nem olyan gyakori: A dinamikus tömbök megvalósítása általában olyan állandót használ, mint a 2 vagy az 1,5 (én csak az std :: vektor megvalósítását ellenőriztem a gcc / clang fájlban, és 2-et használ, úgy tűnik, emlékszem a Microsoft fordítójának 1.5-ös implementációjára. ). Nem tudom, honnan jött a + 3 és + 6 konstans, de azt hiszem, aki ezt írta, valahogy rájött, hogy a + 3 volt a legjobb politika az apró tömbök számára, hogy a + 6 volt a legjobb meglehetősen kicsi tömbök számára ( mondjuk, kevesebb, mint 100), és hogy a nagy tömbök szempontjából ez egyáltalán nem számít, akkor miért ne csak megtartaná.
Úgy tűnik, hogy az alternatív megvalósítások, mint például a Jython és az IronPython, bármilyen natív dinamikus tömb osztályt is használnak a nyelv (illetve a Java és a C #) biztosítja, ezért ugyanazokkal a teljesítményjellemzőkkel rendelkeznek (a pontos mögöttes osztályok a ArrayListnek tűnik a Jython és a C # List az IronPython esetében).
Valaki megkérdezte a megjegyzésekben, hogy ez hogyan lehetséges heterogén típusú elemek tömbjei legyenek ([1, “hello”] érvényes lista a Pythonban). A kérdésre az a válasz, hogy a tömbök technikailag mutatókat tárolnak, nem pedig maguk az objektumok, ami lehetővé teszi, hogy a tömb csak meghatározott méretű elemeket tartalmazzon. A dinamikusan beírt nyelvek közös jellemzője, hogy az alapul szolgáló megvalósításban mindenhol mutatók vannak, és valójában minden olyan nyelv, amely megpróbálja úgy tenni, mintha nincsenek mutatói.
Válasz
Amint azt Adrien Lucas Ecoffet mondta, a python-listák nem más, mint változó hosszúságú tömbök. Bemegyek a cpython forráskódjába, és a makrót kibővítve az alapstruktúra a következő:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Itt megmetszettem a megjegyzéseket, lásd az eredetit kódot kell itt megadni. hogy több mint allokál. Az ilyen tömb átméretezésének kódja, ha tele van, a listobject.c fájlban van. Túlzottan osztja ki a memóriát, hogy elkerülje a list\_resize túl sok idő meghívását. a lista a következő: 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
A Python listák megvalósításának összes felsorolt módszerének megtekintéséhez, beleértve a függeléket, beillesztést, eltávolítást, kiterjesztést és másokat, olvassa el ezt a kiváló blogbejegyzést.