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.