Toen ik leerde programmeren, leken Python-lijsten me volkomen magisch. Ik stelde me voor dat ze werden geïmplementeerd door een soort magische datastructuur die deels gekoppeld was aan een lijst en deels een array die perfect was voor alles.

Toen ik verder ontwikkelde als ingenieur, kwam ik erachter dat dit onwaarschijnlijk was. Ik gokte (correct) dat in plaats van een soort van magische implementatie, het was gewoon ondersteund door een resizable array. Ik besloot de code te lezen en het uit te zoeken.

Een van de leuke dingen van CPython is de leesbare implementatie. Hoewel het betreffende bestand meer dan 2000 regels C bevat, gaat het vooral om het sorteeralgoritme en boilerplate om de functies vanuit Python-code aanroepbaar te maken.1 De kernbewerkingen van de lijst zijn kort en rechttoe rechtaan.

Hieronder staan een paar interessante dingen die ik vond bij het lezen van de implementatie. Onderstaande codefragmenten komen uit de CPython broncode met door mij toegevoegd commentaar.

List Resizing

Als je append aan een Python lijst en de backing array is niet groot genoeg, dan moet de backing array worden uitgebreid. Wanneer dit gebeurt, wordt de backing array met ongeveer 12% vergroot. Persoonlijk had ik aangenomen dat deze groeifactor veel groter was. In Java groeit ArrayList met 50% wanneer het wordt uitgebreid2 en in Ruby groeit Array met 100%.3

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

link naar CPython reallocatie code

Ik heb een paar prestatie-experimenten gedaan – het prealloceren van arrays met constructen zoals *500 lijkt geen merkbaar verschil te maken. In mijn onwetenschappelijke benchmark van het appen naar een lijst 100 miljoen keer, was Python 3 veel langzamer dan Python 2 die veel langzamer was dan Ruby, echter, er is veel meer onderzoek nodig om de impact (indien aanwezig) van de groeifactor op de insert prestaties te bepalen.

Invoegen aan het begin van de lijst

Invoegen aan het begin van een lijst kost lineaire tijd – dit is niet zo verrassend gezien de rest van de implementatie, maar het is goed om te weten dat some_list.insert(0,value) zelden een goed idee is. Een Reddit-gebruiker herinnerde me aan Deques die een constante tijd van invoegen en verwijderen aan beide uiteinden inruilen voor een constante tijd van indexeren.

// 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 naar CPython insertion code

Creating List slices

Het nemen van een slice van een lijst bijv. some_list is ook een lineaire tijdoperatie in de grootte van de slice, dus opnieuw, geen magie. Je zou je kunnen voorstellen dat je dit optimaliseert met een soort copy-on-write semantiek, maar de CPython code geeft de voorkeur aan eenvoud:

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

link naar CPython slice code

Slice Assignment

Je kunt toewijzen aan een slice! Ik ben er zeker van dat dit algemeen bekend is onder professionele Python ontwikkelaars, maar ik ben het nog nooit tegengekomen in verscheidene jaren van Python programmeren. Ik ontdekte het pas toen ik de list_ass_slice(...) functie in de code tegenkwam. Pas echter op met grote lijsten – het moet alle items kopiëren die uit de oorspronkelijke lijst zijn verwijderd, waardoor het geheugengebruik even verdubbelt.

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

Sorteren

Python arrays worden gesorteerd met een algoritme dat bekend staat als “timsort”. Het is erg ingewikkeld en wordt in detail beschreven in een document in de broncodeboom. Ruwweg bouwt het langere en langere reeksen van opeenvolgende items op en voegt ze samen. In tegenstelling tot normale merge sort, begint het met het zoeken naar delen van de lijst die al gesorteerd zijn (runs in de code). Hierdoor kan het gebruik maken van invoergegevens die al gedeeltelijk gesorteerd zijn. Een interessant weetje: Voor het sorteren van kleine arrays (of kleine secties van een grotere array) van maximaal 64 elementen4, gebruikt timsort “binary sort”. Dit is in wezen insertion sort, maar dan met binair zoeken om het element op de juiste plaats in te voegen. Het is eigenlijk een O(n^2) algoritme! Een interessant voorbeeld van hoe real-world prestaties het winnen van algoritmische complexiteit in de praktijk. link

Miste ik iets cools aan CPython-lijsten? Laat het me weten in de comments.

Dank aan Leah Alpert voor het leveren van suggesties voor deze post.

Wil je gemaild worden over nieuwe blog posts?

Ik post ongeveer eens in de paar weken over onderwerpen zoals databases, taal internals en algoritmes, en recent, deep learning.Wil je me inhuren? Ik ben beschikbaar voor opdrachten van 1 week tot een paar maanden. Huur mij in!