När jag lärde mig programmera verkade Pythons listor helt magiska för mig. Jag föreställde mig att de skulle implementeras av någon sorts magisk datastruktur som var delvis länkad lista, delvis array och som var perfekt för allt.

I takt med att jag växte som ingenjör kom jag fram till att detta var osannolikt. Jag gissade (korrekt) att det snarare än någon sorts magisk implementering bara backades upp av en array som kunde ändras i storlek. Jag bestämde mig för att läsa koden och ta reda på det.

En av de trevliga sakerna med CPython är den läsbara implementationen. Även om den relevanta filen är över 2000 rader C, är det mest sorteringsalgoritmen och boilerplate för att göra funktionerna anropsbara från Python-kod.1 De centrala listoperationerna är korta och enkla.

Här är några intressanta saker som jag hittade när jag läste implementationen. Kodutdragen nedan kommer från CPython-källkoden med förklarande kommentarer som lagts till av mig.

List Resizing

Om du lägger till en Python-lista och backing arrayen inte är tillräckligt stor måste backing arrayen expanderas. När detta sker växer backing arrayen med ungefär 12 %. Personligen hade jag antagit att denna tillväxtfaktor var mycket större. I Java växer ArrayList med 50 % när den expanderas2 och i Ruby växer Array med 100 %.3

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

länk till CPythons omallokeringskod

Jag gjorde några prestandatester – förallokering av matriser med konstruktioner som *500 verkar inte göra någon märkbar skillnad. I mitt ovetenskapliga riktmärke med att lägga till en lista 100 miljoner gånger var Python 3 mycket långsammare än Python 2 som var mycket långsammare än Ruby, men det krävs mycket mer forskning för att avgöra vilken inverkan (om någon) tillväxtfaktorn har på insättningsprestanda.

Insättning i början av listan

Insättning i början av en lista tar linjär tid – detta är inte så förvånande med tanke på resten av implementationen, men det är bra att veta att some_list.insert(0,value) sällan är en bra idé. En Reddit-användare påminde mig om Deques som byter konstant tid för insättning och borttagning från båda ändar i utbyte mot konstant tid för indexering.

// 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;

Länk till CPython-kod för insättning

Skapa listskivor

Tagning av en skiva av en lista t.ex. some_listär också en linjär tidsoperation i storleken på skivan, så återigen, ingen magi. Man skulle kunna tänka sig att optimera detta med någon form av copy-on-write-semantik, men CPython-koden föredrar enkelhet:

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

länk till CPython-kod för skivor

Slice Assignment

Du kan tilldela en skiva! Jag är säker på att detta är allmänt känt bland professionella Pythonutvecklare, men jag har aldrig stött på det under flera års pythonprogrammering. jag upptäckte det först när jag stötte på list_ass_slice(...)-funktionen i koden. Se dock upp med stora listor – den behöver kopiera alla objekt som tagits bort från den ursprungliga listan vilket kortvarigt fördubblar minnesanvändningen.

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

Sortering

Python-matriser sorteras med en algoritm som kallas “timsort”. Den är oerhört komplicerad och beskrivs i detalj i ett sidodokument i källkodsträdet. Grovt sett bygger den upp längre och längre löpningar av sekventiella objekt och slår ihop dem. Till skillnad från normal sammanslagningssortering börjar den med att leta efter delar av listan som redan är sorterade (runs i koden). Detta gör att den kan dra nytta av indata som redan är delvis sorterade.En intressant detalj: För sortering av små matriser (eller små delar av en större matris) med upp till 64 element4 använder timsort “binär sortering”. Detta är i huvudsak insättningssortering, men med hjälp av binär sökning för att infoga elementet på rätt plats. Det är faktiskt en O(n^2)-algoritm! Ett intressant exempel på att prestanda i den verkliga världen vinner över algoritmisk komplexitet i praktiken. link

Har jag missat något häftigt med CPython-listor? Låt mig veta det i kommentarerna.

Tack till Leah Alpert för förslag till det här inlägget.

Vill du få e-postmeddelanden om nya blogginlägg?

Jag skriver ungefär en gång varannan vecka om ämnen som t.ex. databaser, språkinställningar och algoritmer och nyligen djupinlärning.Vill du anställa mig? Jag är tillgänglig för uppdrag från en vecka till några månader. Anställ mig!