Amikor programozni tanultam, a Python-listák teljesen varázslatosnak tűntek számomra. Úgy képzeltem el őket, mintha valamiféle varázslatos adatstruktúra valósítaná meg őket, ami részben linkelt lista, részben tömb, ami mindenre tökéletes.

Amint mérnökként fejlődtem, rájöttem, hogy ez valószínűtlen. Arra tippeltem (helyesen), hogy valamiféle mágikus megvalósítás helyett inkább csak egy átméretezhető tömb áll a háttérben. Úgy döntöttem, elolvasom a kódot, és kiderítem.

A CPython egyik szép tulajdonsága az olvasható megvalósítás. Bár a vonatkozó fájl több mint 2000 sornyi C-t tartalmaz, ez többnyire a rendezési algoritmus, és boilerplate, hogy a függvények Python kódból meghívhatók legyenek.1 Az alapvető listaműveletek rövidek és egyszerűek.

Itt van néhány érdekes dolog, amit az implementációt olvasva találtam. Az alábbi kódrészletek a CPython forrásból származnak az általam hozzáadott magyarázó megjegyzésekkel.

List Resizing

Ha egy Python-listához csatolunk, és a háttértömb nem elég nagy, akkor a háttértömböt ki kell bővíteni. Amikor ez megtörténik, a háttértömb körülbelül 12%-kal megnő. Én személy szerint azt feltételeztem, hogy ez a növekedési tényező sokkal nagyobb. Java-ban a ArrayList 50%-kal nő, amikor kibővül2 , Ruby-ban pedig a Array 100%-kal nő.3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

link a CPython újraallokációs kódjára

Megtettem néhány teljesítménykísérletet – a tömbök előzetes allokálása olyan konstrukciókkal, mint a *500, nem tűnik úgy, hogy észrevehető különbséget jelentene. Az én tudománytalan benchmarkomban, amikor 100 milliószor csatoltam egy listához, a Python 3 sokkal lassabb volt, mint a Python 2, ami sokkal lassabb volt, mint a Ruby, azonban sokkal több kutatásra van szükség ahhoz, hogy meghatározzuk a növekedési tényező hatását (ha van egyáltalán) a beszúrási teljesítményre.

A lista elején történő beszúrás

A lista elején történő beszúrás lineáris időt vesz igénybe – ez az implementáció többi részét tekintve nem annyira meglepő, de jó tudni, hogy some_list.insert(0,value) ritkán jó ötlet. Egy Reddit-felhasználó emlékeztetett a Deques-re, amely állandó idejű beszúrást és eltávolítást mindkét végéről cserébe állandó idejű indexelésért cserébe.

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;

link a CPython beszúrási kódjára

Lista szeletek létrehozása

Egy lista szeletének felvétele pl. some_lista szelet méretének lineáris időbeli művelete is, tehát megint csak nem varázslat. Elképzelhető, hogy ezt valamilyen copy-on-write szemantikával optimalizáljuk, de a CPython kódja az egyszerűségnek kedvez:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}

link a CPython slice kódjára

Slice hozzárendelés

Egy slice-hoz hozzárendelhetjük! Biztos vagyok benne, hogy ez általánosan ismert a profi Python fejlesztők körében, de én több évnyi python programozás alatt még soha nem futottam bele. csak akkor jöttem rá, amikor a kódban a list_ass_slice(...) függvényre bukkantam. Vigyázzunk azonban nagy listáknál – az eredeti listából törölt összes elemet át kell másolnia, ami rövid időre megduplázza a memóriahasználatot.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Sortírozás

A python tömböket a “timsort” nevű algoritmussal rendezzük. Ez vadul bonyolult, és részletesen le van írva egy oldalsó dokumentumban a forrásfában. Nagyjából egymás után következő elemek egyre hosszabb és hosszabb sorozatait építi fel és egyesíti őket. A normál egyesítéses rendezéssel ellentétben a lista azon szakaszait keresi, amelyek már rendezettek (runs a kódban). Ez lehetővé teszi, hogy kihasználja a már részben rendezett bemeneti adatok előnyeit.Egy érdekes érdekesség: Kis, legfeljebb 64 elemű tömbök (vagy egy nagyobb tömb kis részeinek) rendezéséhez4 a timsort a “bináris rendezést” használja. Ez lényegében beillesztési rendezés, de bináris keresést használ az elem megfelelő helyre történő beillesztéséhez. Ez valójában egy O(n^2) algoritmus! Érdekes példa arra, hogy a gyakorlatban a valós teljesítmény győzedelmeskedik az algoritmikus bonyolultság felett. link

Kihagytam valami klasszat a CPython listákról? Tudassa velem a hozzászólásokban.

Köszönöm Leah Alpertnek, hogy javaslatokat adott ehhez a bejegyzéshez.

Szeretne e-mailben értesülni az új blogbejegyzésekről?

Pár hetente egyszer posztolok olyan témákról, mint adatbázisok, nyelvi belső tulajdonságok és algoritmusok, és újabban a mélytanulás.Szeretne felvenni? 1 héttől néhány hónapig terjedő megbízásokra állok rendelkezésre. Vegyen fel!