Katsaus taulukoiden toimintaan

Tietojenkäsittelytieteessä on lineaarisen tietorakenteen käsite , mikä tarkoittaa, että data on rakennettu lineaarisella tavalla, missä järjestyksessä on merkitystä . On Taulukot ja linkitettyjen listojen , mutta tänään otan puhu enimmäkseen paneelit, ja hieman linkitettyjen listojen.

Objektin suuntautunut kielten tulevat Arrays , kun taas suurin osa f unctional kieliä mukana Linked Listat (katso miksi toinen artikkelini, mainitsi alareunassa tässä artikkelissa).

Tähän erilaistumiseen on hyvä syy, johon sukelamme myöhemmin. Katsotaan nyt vain nopeasti kahden tietorakenteen erot. Tätä varten meidän on mentävä matkalle muistikaistalla.

Kelaa aikaa

Kohteet ja toiminnot sekä kaikki, mitä tiedämme tietokoneista, tallennetaan pohjimmiltaan tietokoneeseen bitteinä ja tavuina.

Java- ja C-kaltaisilla kielillä sinun on ilmoitettava erikseen taulukon koko etukäteen.

Pysy, mutta Ruby ei tee niin?

Ruby- Arraysovelluksessa käytämme lineaarisia tietorakenteitamme. Voimme lisätä näennäisesti loputtomia asioita Ruby-ryhmään, ja sillä ei ole merkitystä meidän puolestamme.

Se on hienoa, eikö olekin ?! Se tarkoittaa, että taulukot ovat äärettömän suuria, eikö? Ja että Ruby on ylivertainen kieli? Onnekas meille!

Mutta ei niin nopeasti. * ponnahtaa kuplasi *

Ei ole äärettömän kokoisia taulukoita; mitä näet Ruby'ssa, kutsumme dynaamiseksi taulukoksi , ja siihen liittyy kustannuksia.

Jotta ymmärtäisimme, mitä dynaamiset taulukot ovat, katsotaan ensin, miten taulukot esitetään muistissa. Koska MRI Ruby (Matz 'Ruby Interpreter) kääntyy alas C-koodiin, tarkastelemme, kuinka taulukot esitetään C: ssä

C-ing uskoo

Sukellamme hieman C-koodiin auttaaksemme C: tä hieman paremmin ... :)

Alemman tason kielillä, kuten C, joudut käsittelemään osoittimia ja muistin jakamista itse. Vaikka et olisikaan käsitellyt C: tä aikaisemmin (d isclaimer - en minäkään ), sinulla voi olla C-een yksi kuuluisimmista alla olevista (in) esimerkeistä:

Hajotetaan tämä koodibitti:

  • malloc ei ole mitään taikuista merkitystä sen takana, se kirjaimellisesti edustaa memory allocation
  • malloc palauttaa osoittimen
  • malloc vie argumentin, joka on muistin koko, jonka haluat ohjelman jakavan sinulle.
  • 100 * sizeof(int) kertoo ohjelmalle, että haluamme tallentaa 100 kokonaislukua, joten jaa meille 100 * koko, jonka kukin kokonaisluku vie.
  • ptr/ pointer tallentaa viittauksen muistiosoitteeseen.

Timmy säilyttää matkatavaroitaan!

Jos yllä olevalla esimerkillä ei ollut mitään järkeä, kokeile tätä analogiaa. Ajattele muistin jakamista matkatavaroiden vastaanottopalveluna. Se toimii näin:

  • Timmy menee tiskille, kertoo concierge: lle, että hänellä on 2 matkalaukkua, tästä suuresta, ja että hän haluaisi varastoida ne varastoon.
  • Concierge vilkaisee varastotilaa ja menee "Kyllä, meillä on tilaa määrätylle B4alueelle ja osoitamme sen tilaa matkatavaroiden säilyttämiseen".
  • Ne käsi Timmy noudon kortin kanssa rajatulla alueella sitä, B4meidän tapauksessamme.
  • Timmy on onnellinen, kiertää tekemällä mitä tahansa, ja kun hän haluaa noutaa matkatavaransa, hän palaa tiskille ja näyttää heille noutokorttinsa . " Onko sinulla C-een matkalaukkuni?

Esimerkissämme Timmyn matkatavarat ovat tietoja , noutokortti on osoitin (siinä ilmoitetaan, missä Timmyn laukku on tallennettu). Paikka, johon concierge tallentaa Timmyn matkatavaroita, on muistilohko , ja laskuri on ohjelma .

Näyttämällä laskuria ( ohjelma ) Timmyn korttia ( osoitin / muistiosoite ), Timmy voi noutaa matkatavaransa ( tiedot ). Bonus? Koska he tietävät tarkalleen, missä Timmyn laukku on varastoitu - B4, se tarkoittaa, että he voivat hakea kaikki Timmyn matkatavarat suhteellisen nopeasti!

Oletko koskaan miettinyt, miksi käytät taulukon elementtejä indeksillä , kuten niin?

Tämä johtuu siitä, että taulukko sisältää viitteet muistilohkoon, ja hakemisto kertoo sille siirtymän .

Vastauksena tähän on se, että jos pyydän sinua etsimään Timmyä 20 henkilön jonosta, sinun on loogisesti kysyttävä jokaiselta heiltä, ​​olivatko he Timmy. Mutta, jos sanoin, että Timmy on kuudes ( hakemisto ) ensimmäisestä henkilöstä ( alkuperäinen osoitin ), tiedät tarkalleen mistä etsiä.

Elementtien hakeminen taulukoista on nopeaa juuri tämän vuoksi - ohjelman ei tarvitse etsiä kaikkia 100 elementtiä etsimäsi. Jos sinulla on hakemisto, sen on vain lisättävä siirtymä alkuperäiseen muistiosoitteeseen, ja etsimäsi droidi on siellä!

Mitä dynaamiset taulukot sitten ovat?

Joten olen kertonut sinulle hieman siitä, miten taulukot ovat edustettuina muistissa, mutta nyt on aika puhua joistakin haitoista.

Muistatko, kuinka sinun on ilmoitettava nimenomaisesti tarvitsemasi muistimäärä? Tämä tarkoittaa, että taulukko löytää paikan, joka sopii juuri sinun kokoosi. Ei ole mitään takeita siitä, että se mahtuu enemmän kuin sinulla on (koska muistilohko sen takana saattaa olla varattu).

Takaisin matkatavaroiden analogiamme: ajattele sitä, kuin Timmyn olisi varastoitava 2 matkalaukkua ja joka B4voisi tallentaa tarkalleen 2 matkalaukkua, joten he varaavat sen Timmylle. Jostain syystä Timmy haluaa tallentaa toisen matkalaukun, mutta B4ei voi varastoida 3 kappaletta, vain 2, joten mitä he tekevät?

He ottavat kaikki hänen olemassa olevat matkatavaransa, siirtävät sen uuteen paikkaan, johon mahtuu yli 3 kappaletta, ja säilyttävät sitten kaikki yhdessä.

Se on kallis toimenpide, mutta se toimii myös muistin avulla!

Ruby- sovelluksessa sinun ei tarvitse ilmoittaa tiettyä kokoa ennen käsin , mutta se johtuu siitä, että Ruby käsittelee sitä sinulle automaattisesti dynaamisten taulukoiden kautta.

Dynaaminen matriisi tekee siitä, että jos matriisi lähestyy täydellistä kapasiteettiaan, se ilmoittaa automaattisesti uuden, suuremman matriisin ja siirtää kaikki olemassa olevat elementit siihen, ja vanha matriisi kerätään sitten roskiin. Kuinka paljon isompi? Kasvutekijä on yleensä 2; kaksinkertainen nykyisen taulukon koko.

Itse asiassa, älä ota sanaani siihen .

Rubyllä on ObjectSpace-moduuli, jonka avulla voimme olla vuorovaikutuksessa nykyisten muistissa elävien esineiden kanssa. Voimme käyttää tätä moduulia kurkistamaan dynaamisen matriisimme muistin käyttöä - kuulostaa täsmälleen haluamaltamme!

Olen kirjoittanut pienen Ruby-komentosarjan, joka laskee dynaamisen taulukon kasvutekijän. Voit vapaasti katsoa sitä täällä, ja jos teet, näet, että Ruby-matriiseilla on 1,5-kertainen kasvutekijä (eli ne tekevät ryhmästä, joka on 50% suurempi jokaisessa kopiossa).

Tiedän mitä taulukot ovat, mitä linkitetyt luettelot ovat?

Muista, että vaikka matriiseja ja linkitettyjä luetteloita pidetään lineaarisina tietorakenteina, niiden välillä on yksi suuri ero.

Matriisin elementit tallennetaan kirjaimellisesti aivan vierekkäin muistiin (joten meillä voi olla hakemisto nopeaa hakua varten). Linkitettyjen luetteloiden solmuilla ei kuitenkaan ole tällaista rajoitusta (minkä vuoksi linkitetyille luetteloille ei ole hakemistohakua) - jokainen kohde voidaan tallentaa mihin tahansa muistilohkoon.

On melkein kuin Timmy yrittäisi varastoida viittä matkalaukkua, eikä conciergeellä ole tilaa ja päättää jättää ne kaikkialle. Kuulostaa järjestämättömältä?

Myös jos ne varastoidaan eri paikkoihin, mistä tiedät, mitkä pussit ovat Timmyn pussit? Vihje: Seuraa vain seuraavaa solmua / pussia! Meidän tapauksessamme concierge pitää heidät erikseen, mutta jokaisessa niistä on merkki, joka osoittaa seuraavaan pussiin.

Linkitetyn luettelon solmu koostuu kahdesta osasta - dataosasta ja osoittimesta seuraavaan solmuun. Näin he pystyvät ylläpitämään linearosan siitä - heillä on edelleen järjestyksen käsite, niitä ei vain tarvitse varastoida järjestyksessä kirjaimellisesti!

node = [ data | pointer ]

Esimerkiksi, kun muistiin on tallennettu seuraava esimerkki:

[C | D] [A | B] [B | C] [D | nil]

Nämä bitit näyttävät olevan epäkunnossa - mutta jos olisin sanonut sinulle, että ensimmäinen elementti on A, voisit kertoa minulle luettelon tarkan järjestyksen:

list = [A -> B -> C ->D -> nolla]

Linkitetyillä listoilla on paljon mielenkiintoista, joihin en aio sukeltaa täällä (myös paljon Big O: ssa, josta en puhunut). Mutta tietorakenteista löytyy jo paljon hyviä artikkeleita. Jos teit sen täällä, ehdotan, että luet Alin blogiviestistä täältä.

kiitos seuraavaksi: johdanto linkitettyihin luetteloihin

Tässä viestissä puhumme linkitetyn luettelon tietorakenteesta "kiitos u, seuraava" kielellä ... dev.to

Voit myös lukea lisää luettelosta / haitoista Wikissä täältä.

Loppuhuomautus

Kirjoitin tämän artikkelin alun perin hieman eri aiheesta - [Elixir | Miksi linkitetyt luettelot?], Mutta havaitsi, että taulukoiden toiminnan selittäminen kesti liian kauan, ennen kuin pystyin selittämään, miksi Elixir käyttää linkitettyjä luetteloita. Joten olen jakanut ne kahteen artikkeliin.

Tuossa artikkelissa puhun siitä, miksi toiminnalliset kielet käyttävät linkitettyjä luetteloita lineaarisena tietorakenteenaan. Tarkista se!

[Elixir | Miksi linkitetyt luettelot? ]

Olen aina ajatellut tietorakenteiden olevan hienoja, mutta tiedät mikä on siistimpi? Näet heidät luonnossa! Käydessään läpi ... dev.to

Lähteet

  1. //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Täältä sain lisätietoja muista ObjectSpacemenetelmistä vaatimalla sitä

Alun perin lähetetty dev.to