Oppiessani ohjelmointia Python-listat vaikuttivat minusta täysin maagisilta. Kuvittelin niiden olevan toteutettu jonkinlaisella maagisella tietorakenteella, joka oli osittain linkitetty lista, osittain array ja joka sopi täydellisesti kaikkeen.

Kehittyessäni insinööriksi tajusin, että tämä oli epätodennäköistä. Arvelin (oikein), että jonkinlaisen maagisen toteutuksen sijaan sen taustalla oli vain kokoa muuttava array. Päätin lukea koodin ja ottaa siitä selvää.

Yksi CPythonin hienouksista on luettava toteutus. Vaikka kyseinen tiedosto on yli 2000 riviä C:tä, se on enimmäkseen lajittelualgoritmi ja boilerplatea, jotta funktiot ovat kutsuttavissa Python-koodista.1 Listan ydinoperaatiot ovat lyhyitä ja suoraviivaisia.

Tässä on muutama mielenkiintoinen asia, joita löysin toteutusta lukiessani. Alla olevat koodinpätkät ovat peräisin CPythonin lähdekoodista, johon olen lisännyt selventäviä kommentteja.

Listan koon muuttaminen

Jos Python-listaan liitetään ja taustamäärikkö ei ole tarpeeksi suuri, taustamäärikköä on laajennettava. Kun näin tapahtuu, taustamäärikkö kasvaa noin 12 %. Itse olin olettanut, että tämä kasvukerroin on paljon suurempi. Javassa ArrayList kasvaa 50 %, kun sitä laajennetaan2 , ja Rubyssä Array kasvaa 100 %.3

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

linkki CPythonin uudelleenallokointikoodiin

Tein muutaman suorituskykykokeen – tukimassojen esiallokointi konstruktioilla kuten *500 ei näytä tekevän mitään havaittavaa eroa. Epätieteellisessä vertailuarvossani, jossa listaan liitettiin 100 miljoonaa kertaa, Python 3 oli paljon hitaampi kuin Python 2, joka oli paljon hitaampi kuin Ruby, mutta tarvitaan kuitenkin paljon lisää tutkimusta, jotta voidaan määrittää kasvutekijän vaikutus (jos sitä on) insertin suorituskykyyn.

Syöttäminen listan alussa

Syöttäminen listan alussa vie lineaarista aikaa – tämä ei ole kovin yllättävää ottaen huomioon muun toteutuksen, mutta on hyvä tietää, että some_list.insert(0,value) on harvoin hyvä idea. Eräs Reddit-käyttäjä muistutti minua Dequeistä, jotka vaihtavat vakioaikaista inserttiä ja poistoa molemmista päistä vakioaikaiseen indeksointiin.

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

linkki CPythonin insertointikoodiin

Listan viipaleiden luominen

Listan viipaleen ottaminen esim. some_liston myös lineaarisen ajan operaatio viipaleen koon mukaan, joten taas ei mitään taikuutta. Tämän voisi kuvitella optimoitavan jonkinlaisella copy-on-write-semantiikalla, mutta CPythonin koodi suosii yksinkertaisuutta:

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

linkki CPythonin slice-koodiin

Slice Assignment

Voi osoittaa sliceen! Olen varma, että tämä on yleisesti tiedossa ammattimaisten Python-kehittäjien keskuudessa, mutta en ole koskaan törmännyt siihen useiden vuosien python-ohjelmoinnin aikana. huomasin sen vasta, kun törmäsin list_ass_slice(...)-funktioon koodissa. Ole kuitenkin varovainen suurilla listoilla – sen täytyy kopioida kaikki alkuperäisestä listasta poistetut kohteet, mikä hetkellisesti kaksinkertaistaa muistin käytön.

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

Lajittelu

Pythonin matriisit lajitellaan algoritmilla, joka tunnetaan nimellä “timsort”. Se on hurjan monimutkainen ja se on kuvattu yksityiskohtaisesti lähdepuussa olevassa sivudokumentissa. Karkeasti sanottuna se muodostaa yhä pidempiä sarjoja peräkkäisistä kohteista ja yhdistää ne. Toisin kuin tavallinen yhdistelmälajittelu, se alkaa etsimällä listan osia, jotka on jo lajiteltu (runs koodissa). Näin se voi hyödyntää syöttötietoa, joka on jo osittain lajiteltu.Mielenkiintoinen tieto: Pienten, enintään 64-alkioisten matriisien (tai suuremman matriisin pienten osien) lajitteluun4 timsort käyttää “binary sort” -lajittelua. Tämä on pohjimmiltaan lisäyslajittelu, mutta siinä käytetään binäärihakua elementin sijoittamiseksi oikeaan paikkaan. Se on itse asiassa O(n^2)-algoritmi! Mielenkiintoinen esimerkki siitä, että reaalimaailman suorituskyky voittaa käytännössä algoritmisen monimutkaisuuden. link

Olenko missannut jotain hienoa CPython-listoista? Kerro minulle kommenteissa.

Kiitos Leah Alpertille ehdotuksista tähän postaukseen.

Haluatko saada sähköpostia uusista blogikirjoituksista?

Postailen noin kerran parissa viikossa aiheista kuten tietokannat, kielten sisäiset ominaisuudet ja algoritmit sekä viime aikoina syväoppiminen.Haluatko palkata minut? Olen käytettävissä toimeksiantoihin 1 viikosta muutamaan kuukauteen. Palkkaa minut!