Jak jsou seznamy Pythonu implementovány interně?


Nejlepší odpověď

Na rozdíl od toho, co naznačuje jejich název, seznamy Pythonu jsou vlastně pole, což mě nikdy nepřestává otravovat (já ne „Nejsou to zavádějící názvy). Konkrétně se jedná o dynamická pole s exponenciálním nadměrným přidělením, což umožňuje lineární složitosti kódu jako je následující:

lst = []

for i in xrange(0, 100000):

lst.append(i)

Zajímavé je, že nadměrná alokace v CPython je extrémně konzervativní, protože přiděluje 1,125 * new\_size + 6 (nebo + 3, když je pole menší než 9 prvků). Tato konstanta 1.125 je poměrně neobvyklá, a jak jsem řekl, je velmi konzervativní a zdá se tedy, že předpokládá, že řada přidávání hovorů není tak běžné. Implementace dynamických polí obvykle používají konstantu jako 2 nebo 1,5 (právě jsem zkontroloval implementaci std :: vector v gcc / clang a používá 2, zdá se mi, že si pamatuji implementaci kompilátoru Microsoft používá 1,5 ). Nevím, odkud pochází konstanta + 3 a + 6, ale myslím, že kdokoli to napsal, nějak zjistil, že + 3 je nejlepší politika pro malá pole, že + 6 je nejlepší pro poměrně malá pole ( řekněme méně než 100) a že na velkých polích to vlastně vůbec nevadí, tak proč si to prostě nenechat.

Zdá se, že alternativní implementace jako Jython a IronPython používají jakoukoli třídu nativního dynamického pole jako svůj podklad jazyk (respektive Java a C #), takže mají stejné výkonnostní charakteristiky (přesné základní třídy se zdají být ArrayList pro Jython a C # List pro IronPython).

Někdo se v komentářích zeptal, jak je to možné mít pole prvků heterogenních typů ([1, „ahoj“] je platný seznam v Pythonu). Odpověď na tuto otázku je, že pole technicky ukládají ukazatele spíše než samotné objekty, což umožňuje, aby pole obsahovalo pouze prvky konkrétní velikosti. Mít ukazatele všude v podkladové implementaci je společným rysem jazyků s dynamickým typem a vlastně jakéhokoli jazyka, který se snaží předstírat, že ukazatele nemá.

Odpovědět

Jak uvedl Adrien Lucas Ecoffet, seznamy pythonu nejsou nic jiného než pole s proměnnou délkou. Kopám do zdrojového kódu cpythonu a při rozšiřování makra je základní struktura definována jako:

typedef struct {

PyObject\_VAR\_HEAD

PyObject **ob\_item;

Py\_ssize\_t allocated;

} PyListObject;

Ořezal jsem zde komentáře, odkazuji na originál kód zde. 6c2e2de5ab8e Include / listobject.h

PyObject\_VAR\_HEAD obsahuje počet odkazů a identifikátor typu. Je to tedy vektor / pole že přes přidělí. Kód pro změnu velikosti takového pole, když je plný, je v listobject.c . Nadměrně přiděluje paměť, aby se zabránilo příliš dlouhému volání list\_resize. Vzor růstu seznamu je: 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

Chcete-li zobrazit všechny uvedené metody implementace seznamů seznamu Python, včetně připojení, vložení, odebrání, rozšíření a dalších, přečtěte si tento vynikající blogový příspěvek.

Implementace seznamu Python

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *