Paras vastaus
Päinvastoin kuin heidän nimensä viittaa, Python-luettelot ovat itse asiassa matriiseja, tosiasia, joka ei koskaan lakkaa ärsyttämästä minua (en ”t kuten harhaanjohtavia nimiä). Erityisesti ne ovat dynaamisia matriiseja, joissa on eksponentiaalinen ylivara, mikä sallii seuraavanlaisen koodin olevan lineaarisen monimutkainen:
lst = []
for i in xrange(0, 100000):
lst.append(i)
Mielenkiintoista on, että ylivaraaminen CPython on erittäin konservatiivinen, koska se allokoi 1.125 * new\_size + 6 (tai + 3, kun matriisi on pienempi kuin 9 elementtiä). Tämä 1.125-vakio on melko harvinaista, ja kuten sanoin, se on hyvin konservatiivinen ja näyttää siten olettavan tämän sarjan Liitä puhelut eivät ole kovin yleisiä. Dynaamisten matriisien toteutuksissa käytetään yleensä vakiota, kuten 2 tai 1,5 (Tarkistin vain standardin std :: vector toteutuksen gcc / clang-sovelluksessa ja se käyttää 2: ta. Näyttää siltä, että muistan Microsoft-kääntäjän toteutuksen 1,5 ). En tiedä, mistä + 3 ja + 6 vakio tuli, mutta luulen, että kuka tämän kirjoitti, sai jotenkin selville, että + 3 oli paras käytäntö pienille matriiseille, että + 6 oli paras melko pienille matriiseille ( sanoa, alle 100) ja että sillä ei todellakaan ole väliä suurilla matriiseilla, joten miksi ei vain säilyttää sitä.
Vaihtoehtoiset toteutukset, kuten Jython ja IronPython, näyttävät käyttävän mitä tahansa alkuperäistä dynaamista matriisiluokkaa niiden taustalla kieli (Java ja C #) tarjoaa, joten niillä on samat suorituskykyominaisuudet (tarkat taustaluokat näyttävät olevan ArrayList Jythonille ja C # List IronPythonille).
Joku kysyi kommenteissa, kuinka se oli mahdollista heterogeenisten elementtien taulukot ([1, ”hei”] on kelvollinen luettelo Pythonissa). Vastaus tähän kysymykseen on, että matriisit tallentavat teknisesti osoittimia eikä itse objekteja, mikä sallii matriisin sisältää vain tietyn kokoisia elementtejä. Osoittimien käyttäminen kaikkialla taustalla olevassa toteutuksessa on dynaamisesti kirjoitettujen kielten yleinen piirre, ja itse asiassa kaikilla kielillä, jotka yrittävät teeskennellä, että sillä ei ole osoittimia.
Vastaa
Kuten Adrien Lucas Ecoffet sanoi, python-luettelot eivät ole muuta kuin muuttuvan pituisia taulukoita. Kaivun cpythonin lähdekoodiin ja laajentamalla makroa perusrakenne määritellään seuraavasti:
typedef struct {
PyObject\_VAR\_HEAD
PyObject **ob\_item;
Py\_ssize\_t allocated;
} PyListObject;
Olen karsinut kommentit täällä, viittaa alkuperäiseen koodi tähän. 6c2e2de5ab8e Sisällytä / listobject.h
PyObject\_VAR\_HEAD sisältää viitemäärän ja tyyppitunnisteen. Joten se ”sa vector / array että yli jakaa. Koodi tällaisen taulukon koon muuttamiseksi, kun se on täynnä, on kohdassa listobject.c . Se allokoi liikaa muistia välttääkseen soittamalla list\_resize liian monta kertaa. Kasvumalli luettelossa on: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…
arguments: list object, new size
returns: 0 if OK, -1 if not
list\_resize:
new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
new\_allocated += newsize
resize ob\_item (list of pointers) to size new\_allocated
return 0
Näet kaikki luetellut Python-luetteloiden toteutustavat, mukaan lukien lisäys, lisäys, poisto, laajentaminen ja muut, tutustu tähän erinomaiseen blogiviestiin.