Da jeg lærte at programmere, virkede Python-lister helt magiske for mig. Jeg forestillede mig dem som værende implementeret af en slags magisk datastruktur, der var dels linked-list, dels array, som var perfekt til alting.

Mens jeg voksede som ingeniør, gik det op for mig, at det var usandsynligt. Jeg gættede (korrekt), at i stedet for en slags magisk implementering, blev det bare understøttet af et array, der kan ændres i størrelse. Jeg besluttede mig for at læse koden og finde ud af det.

En af de gode ting ved CPython er den læsbare implementering. Selv om den relevante fil er over 2000 linjer C, er det for det meste sorteringsalgoritmen og boilerplate for at gøre funktionerne kaldbare fra Python-kode.1 De centrale listeoperationer er korte og ligetil.

Her er et par interessante ting, jeg fandt ved at læse implementeringen. Kodestumperne nedenfor kommer fra CPython-kilden med forklarende kommentarer tilføjet af mig.

List Resizing

Hvis du tilføjer til en Python-liste, og det bagvedliggende array ikke er stort nok, skal det bagvedliggende array udvides. Når dette sker, vokser det bagvedliggende array med ca. 12 %. Personligt havde jeg antaget, at denne vækstfaktor var meget større. I Java vokser ArrayList med 50 %, når den udvides2, og i Ruby vokser Array med 100 %.3

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

link til CPython-reallokeringskode

Jeg lavede et par eksperimenter med ydeevnen – præallokering af arrays med konstruktioner som *500 ser ikke ud til at gøre nogen mærkbar forskel. I min uvidenskabelige benchmark med tilføjelse til en liste 100 millioner gange var Python 3 meget langsommere end Python 2, som var meget langsommere end Ruby, men der er behov for meget mere forskning for at bestemme vækstfaktorens indvirkning (hvis nogen) på indsætningsydelsen.

Indsætning i begyndelsen af listen

Indsætning i begyndelsen af en liste tager lineær tid – dette er ikke så overraskende i betragtning af resten af implementeringen, men det er godt at vide, at some_list.insert(0,value) sjældent er en god idé. En Reddit-bruger mindede mig om Deques, som bytter konstant tidsindsættelse og -fjernelse fra begge ender til gengæld for konstant tidsindeksering.

// 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 til CPython-indsættelseskode

Skabelse af listeskiver

Tage en skive af en liste f.eks. some_lister også en lineær tidsoperation i størrelsen af skiven, så igen er der ingen magi. Man kunne forestille sig at optimere dette med en slags copy-on-write-semantik, men CPython-koden favoriserer enkelhed:

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

link til CPython-slice-kode

Slice Assignment

Du kan tildele til en slice! Jeg er sikker på, at dette er almindeligt kendt blandt professionelle Python-udviklere, men jeg er aldrig stødt på det i flere år med python-programmering. jeg opdagede det først, da jeg stødte på list_ass_slice(...)-funktionen i koden. Pas dog på med store lister – den skal kopiere alle elementer, der er slettet fra den oprindelige liste, hvilket kortvarigt fordobler hukommelsesforbruget.

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

Sortering

Python arrays sorteres med en algoritme kendt som “timsort”. Den er vildt kompliceret og er beskrevet i detaljer i et sidedokument i kildetræet. Groft sagt opbygger den længere og længere kørsler af sekventielle elementer og slår dem sammen. I modsætning til normal sammenlægningssortering starter den med at lede efter sektioner af listen, der allerede er sorteret (runs i koden). Dette gør det muligt for den at drage fordel af inputdata, der allerede er delvist sorteret. en interessant detalje: Til sortering af små arrays (eller små sektioner af et større array) på op til 64 elementer4 bruger timsort “binær sortering”. Dette er i bund og grund indsættelsessortering, men ved hjælp af binær søgning til at indsætte elementet på den korrekte placering. Det er faktisk en O(n^2)-algoritme! Et interessant eksempel på, at den virkelige verdens ydeevne vinder over algoritmisk kompleksitet i praksis. link

Er jeg gået glip af noget fedt ved CPython-lister? Lad mig vide det i kommentarerne.

Tak til Leah Alpert for at komme med forslag til dette indlæg.

Vil du modtage e-mails om nye blogindlæg?

Jeg skriver ca. en gang hver anden uge om emner som databaser, sproginternaler og algoritmer og for nylig, dyb læring.Vil du ansætte mig? Jeg er tilgængelig for engagementer fra 1 uge til et par måneder. Hyr mig!