En oversigt over, hvordan arrays fungerer

I datalogi er der begrebet en lineær datastruktur , hvilket betyder, at dataene er struktureret på en lineær måde, hvor orden betyder noget . Der er arrays og sammenkædede lister , men i dag taler jeg mest om arrays og lidt om sammenkædede lister.

De fleste objekt-orienteret sprog kommer med Arrays , mens de fleste f unctional sprog kommer med hægtede lister (se hvorfor i en anden af mine artikler, nævnt i bunden af denne artikel).

Der er en god grund til denne differentiering, som vi vil dykke ind i senere. Lad os nu bare se hurtigt på forskellene mellem de to datastrukturer. For at gøre dette skal vi tage en tur ned i hukommelsesbanen.

Spol tilbage tid

Objekter og funktioner og alt, hvad vi ved om computere, er grundlæggende gemt i bits og bytes på computeren.

På sprog som Java og C skal du på forhånd udtrykkeligt erklære størrelsen på en matrix.

Vent, men Ruby gør det ikke?

I Ruby bruger vi Arraytil vores lineære datastrukturer. Vi kan tilføje tilsyneladende uendelige ting i et Ruby-array, og det betyder ikke noget for os.

Det er godt, er det ikke ?! Det betyder, at arrays er uendeligt store, ikke? Og at Ruby er det overlegne sprog? Heldige os!

Men ikke så hurtigt. * popper din boble *

Der er ingen uendelige størrelsesarrays; hvad du ser i Ruby er, hvad vi kalder en Dynamic Array , og det kommer med en pris.

For at forstå, hvad dynamiske arrays er, skal vi først se på, hvordan arrays er repræsenteret i hukommelsen. Da MRI Ruby (Matz 'Ruby Interpreter) kompileres ned til C-kode, ser vi på, hvordan arrays er repræsenteret i C.

C-ing er at tro

Vi dykker ned i en lille smule C-kode for at hjælpe os med C lidt bedre ... :)

På sprog på lavere niveau som C skal du selv håndtere pegepinde og hukommelsesallokering. Selvom du ikke har behandlet C før (d ansvarsfraskrivelse - heller ikke jeg ), har du muligvis C-en af ​​de mest (i) berømte eksempler nedenfor:

Lad os nedbryde denne bit kode:

  • malloc har ingen magisk betydning bag sig, det står bogstaveligt for memory allocation
  • malloc returnerer en markør
  • malloc tager et argument ind, som er størrelsen på den hukommelse, du vil have programmet tildelt til dig.
  • 100 * sizeof(int) fortæller programmet, at vi vil gemme 100 heltal, så tildel os 100 * størrelsen på, hvad hvert heltal ville optage.
  • ptr/ pointer gemmer henvisning til hukommelsesadressen.

Timmy gemmer bagage!

Hvis ovenstående eksempel ikke rigtig gav mening, så prøv denne analogi. Tænk på hukommelsesallokering som en bagage-concierge. Det fungerer sådan her:

  • Timmy går til skranken, fortæller portneren, at han har 2 stykker bagage, om denne store, og at han gerne vil opbevare dem i lagerrummet.
  • Portneren kigger på lagerrummet og går ”Ja, vi har lidt plads på det udpegede B4område og tildeler den plads til opbevaring af din bagage”.
  • De giver Timmy et afhentningskort med det udpegede område B4i vores tilfælde.
  • Timmy er glad, går rundt og gør hvad som helst, og når han vil afhente sin bagage, går han tilbage til tælleren og viser dem sit afhentningskort . “ Har du C-en min bagage?

I vores eksempel er Timmys bagage dataene , afhentningskortet er markøren (det står, hvor Timmys taske er gemt). Det sted, hvor portneren opbevarer Timmys bagage, er hukommelsesblokken , og tælleren er programmet .

Ved at vise tælleren ( programmet ) Timmys kort ( pointer / hukommelsesadresse ) kan Timmy hente sin bagage ( data ). Bonus? Fordi de ved nøjagtigt, hvor Timmys taske opbevares - B4betyder det, at de relativt hurtigt kan hente al Timmys bagage!

Har du nogensinde spekuleret på, hvorfor du får adgang til elementer i matrix med indeks , sådan?

Dette skyldes, at arrayet indeholder referencerne til hukommelsesblokken, og indekset fortæller det forskydningen .

En analogi til det er, hvis jeg beder dig om at kigge efter Timmy i en kø på 20 personer, ville du logisk nok være nødt til at spørge hver af dem, om de var Timmy. Men hvis jeg fortalte dig, at Timmy er den 6. ( indeks ) fra den første person ( din oprindelige markør ), ved du præcis, hvor du skal se.

Det er hurtigt at hente elementer i arrays nøjagtigt på grund af dette - programmet behøver ikke at gennemse alle 100 elementer for at finde det, du leder efter. Hvis du har indekset, skal det bare tilføje forskydning til den oprindelige hukommelsesadresse, og den droid, du ledte efter, vil være lige der!

Hvad er dynamiske arrays da?

Så jeg har fortalt dig lidt om, hvordan arrays er repræsenteret i hukommelsen, men nu er det tid til at tale om nogle ulemper.

Husk hvordan du eksplicit skal erklære den mængde hukommelse, du har brug for? Dette betyder, at arrayet finder et sted, der passer nøjagtigt til din størrelse. Der er ingen garanti for, at det vil være i stand til at passe mere, end hvad du har (fordi hukommelsesblokken lige bag den kan være optaget).

Tilbage til vores bagageanalogi: tænk på det som om Timmy skulle opbevare 2 stykker bagage og B4kan gemme nøjagtigt 2 stykker bagage, så de tildeler det til Timmy. Nu af en eller anden grund vil Timmy opbevare endnu et stykke bagage, men B4kan ikke gemme 3 stykker, kun 2, så hvad gør de?

De tager al hans eksisterende bagage, flytter den til et nyt sted, der kan passe mere end 3 stykker, og gemmer dem alle sammen.

Det er en dyr operation, men det er præcis, hvordan hukommelse også fungerer!

I Ruby behøver du ikke at erklære en bestemt størrelse før hånden , men det er fordi Ruby håndterer det automatisk for dig gennem dynamiske arrays.

Hvad et dynamisk array gør, er at hvis arrayet nærmer sig sin fulde kapacitet, vil det automatisk erklære et nyt, større array og flytte alle eksisterende elementer ind i det, og det gamle array samles derefter skrald. Hvor meget større? Vækstfaktoren er normalt 2; dobbelt så stort som det aktuelle array.

Faktisk skal du ikke tage mit ord for det .

Ruby har et ObjectSpace-modul, der giver os mulighed for at interagere med aktuelle objekter, der lever i hukommelsen. Vi kan bruge dette modul til at kigge på hukommelsesforbruget i vores dynamiske array - lyder nøjagtigt som det, vi vil have!

Jeg har skrevet et lille Ruby-script, der beregner vækstfaktoren for det dynamiske array. Du er velkommen til at se på det her, og hvis du gør det, kan du se, at Ruby-arrays har en 1,5x vækstfaktor (det vil sige, de laver en matrix, der er 50% større på hver kopi).

Jeg ved hvad arrays er, hvad er sammenkædede lister?

Husk, at selvom arrays og sammenkædede lister begge betragtes som lineære datastrukturer, har de en stor forskel mellem dem.

Elementer i en matrix gemmes bogstaveligt talt lige ved siden af ​​hinanden i hukommelsen (så vi kan have indeks til hurtige opslag). Men noder i sammenkædede lister har ingen sådan begrænsning (det er derfor, der ikke er nogen indeksopslag for sammenkædede lister) - hvert eneste element kan gemmes hvor som helst på hukommelsesblokken.

Det er næsten som om Timmy prøver at opbevare 5 stykker bagage, og portneren ikke har plads og beslutter at lade dem være overalt. Lyder uorganiseret?

Også hvis de opbevares forskellige steder, hvordan ved du hvilke tasker der er Timmy's? Tip: Bare hold styr på den næste node / taske! I vores tilfælde holder portneren dem separat, men med et mærke på hver af dem, der peger på den næste taske.

En node i en sammenkædet liste består af to dele - datadelen og en markør til den næste node. Dette er, hvordan de er i stand til at opretholde den lineardel af det - de har stadig begrebet orden, de behøver bare ikke at blive gemt ordentligt!

node = [ data | pointer ]

For eksempel givet følgende eksempel gemt i hukommelsen:

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

Disse bits ser ud som om de ikke er i orden - men hvis jeg havde fortalt dig, at det første element er A, ville du være i stand til at fortælle mig den nøjagtige rækkefølge på listen:

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

Der er mange interessante ting, du kan gøre med linkede lister, som jeg ikke vil dykke ind her (også meget på Big O, som jeg ikke talte om). Men der er allerede masser af gode artikler derude om datastrukturer. Hvis du gjorde det her, foreslår jeg, at du læser fra Alis blogindlæg her.

tak u, næste: en introduktion til sammenkædede lister

I dette indlæg vil vi tale om den sammenkædede liste datastruktur på sproget "tak u, næste" af ... dev.to

Du kan også læse mere om Liste / Ulemper på Wiki her.

Afslutningsnote

Jeg skrev oprindeligt denne artikel for et lidt andet emne - [Elixir | Hvorfor sammenkædede lister?], Men fandt det tog alt for lang tid at forklare, hvordan arrays fungerer, før jeg var i stand til at forklare, hvorfor Elixir bruger sammenkædede lister. Så jeg har opdelt dem i to artikler.

I den artikel taler jeg om, hvorfor funktionelle sprog bruger sammenkædede lister som deres lineære datastruktur. Tjek det ud!

[Eliksir | Hvorfor sammenkædede lister? ]

Jeg har altid syntes datastrukturer er seje, men ved du hvad der er køligere? At se dem i naturen! Mens du går igennem ... dev.to

Kilder

  1. //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Det er her, jeg fandt ud af yderligere ObjectSpacemetoder ved at kræve det

Oprindeligt udgivet på dev.to