U računalnoj znanosti postoji koncept linearne strukture podataka , što znači da su podaci strukturirani na linearni način na koji je važan redoslijed . Postoje nizovi i povezani popisi , ali danas ću govoriti uglavnom o nizovima i malo o povezanim popisima.
Većina objektno-orijentirani jezici dolaze s Razvrstati , dok je većina f unctional jezike dolaze s vezana lista (vidi zašto se u još jednom od svojih članaka, spominje na dnu ovog članka).
Postoji dobar razlog za ovu diferencijaciju u koji ćemo kasnije zaroniti. Za sada ćemo samo na brzinu pogledati razlike između dviju struktura podataka. Da bismo to učinili, morat ćemo krenuti putovanjem memorijskom trakom.
Vrijeme premotavanja
Predmeti i funkcije i sve što znamo o računalima, u osnovi se pohranjuju u bitovima i bajtovima u računalu.
U jezicima kao što su Java i C, prethodno morate izričito navesti veličinu niza.
Čekaj, ali Ruby to ne radi?U Rubyu koristimo Arrayza svoje linearne strukture podataka. Možemo dodati naizgled beskonačne stvari u Rubyev niz i to ne bi bilo važno što se nas tiče.
To je sjajno zar ne ?! To znači da su nizovi beskrajno veliki, zar ne? A da je Ruby superiorni jezik? Sretno nama!
Ali ne tako brzo. * iskoči vaš mjehur *
Ne postoji niz beskonačnih veličina; ono što vidite u Rubyu je ono što nazivamo Dynamic Array , a to dolazi uz cijenu.
Da bismo razumjeli što su dinamički nizovi, pogledajmo prvo kako su nizovi predstavljeni u memoriji. Budući da se MRI Ruby (Matz 'Ruby Interpreter) kompilira na C kod, pogledat ćemo kako su nizovi predstavljeni u C.
C-ing vjeruje
Zaronit ćemo u malo C koda koji će nam pomoći C malo bolji ... :)
U jezicima niže razine, poput C, sami se morate nositi s pokazivačima i dodjelom memorije. Čak i ako se prije niste bavili C-om (d izjava - nisam ni ja ), možda imate C-een jedan od najpoznatijih (ne) primjera u nastavku:
Razdvojimo ovaj bit koda:
mallocnema magično značenje iza sebe, doslovno se zalaže zamemory allocationmallocvraća pokazivačmallocuzima argument, što je veličina memorije koju želite da vam program dodijeli.100 * sizeof(int)govori programu da želimo pohraniti 100 cijelih brojeva, pa nam dodijelite 100 * veličinu onoga što bi zauzimao svaki cijeli broj.ptr/ pokazivač pohranjuje referencu na memorijsku adresu.
Timmy sprema prtljagu!
Ako gornji primjer zapravo nije imao smisla, pokušajte s ovom analogijom. Dodjeljivanje memorije shvatite kao vratar prtljage. Djeluje ovako:
- Timmy ide na šalteru, kaže vratar da ima 2 komada prtljage, o tom veliki, a da je on bih ih pohraniti u spremište.
- Vratar pogleda prodavaonicu i kaže "Da, imamo neko mjesto na određenom
B4prostoru i dodijelit ćemo taj prostor za pohranu vaše prtljage". - U našem slučaju Timmyju daju karticu za preuzimanje s označenim
B4mjestom. - Timmy je sretan, obilazi radeći što god, a kad želi podići prtljagu, vrati se do šaltera i pokaže im svoju karticu za preuzimanje . “ Jeste li mi uzeli prtljagu? "
U našem primjeru, Timmyjeva prtljaga su podaci , kartica za preuzimanje je pokazivač (navodi se gdje je Timmyjeva torba pohranjena). Mjesto na kojem vratar čuva Timmyjevu prtljagu je memorijski blok , a brojač program .
Pokazujući brojač ( program ) Timmyjevu karticu ( pokazivač / adresa memorije ), Timmy može preuzeti svoju prtljagu ( podatke ). Bonus? Budući da točno znaju gdje se čuva Timmyjeva torba - B4, to znači da relativno brzo mogu preuzeti svu Timmyjevu prtljagu!
Također, ikad se zapitalo zašto elementima u polju pristupate s indeksom , na taj način?
To je zato što niz sadrži reference na memorijski blok, a indeks mu govori o odmaku .
Analogija za to je ako vas zamolim da potražite Timmyja u redu od 20 ljudi, logično biste morali pitati svakog od njih jesu li Timmy. Ali, ako sam vam rekao da je Timmy 6. ( indeks ) od prve osobe ( vaš izvorni pokazivač ), znate točno gdje trebate tražiti.
Dohvaćanje elemenata u nizovima je upravo zbog toga brzo - program ne mora pregledavati svih 100 elemenata kako bi pronašao ono što tražite. Ako imate indeks, on jednostavno mora dodati odmak originalnoj memorijskoj adresi, a droid kojeg ste tražili bit će tamo!
Što su onda dinamički nizovi?
Dakle, rekao sam vam malo o tome kako su nizovi predstavljeni u memoriji, ali sada je vrijeme da razgovaramo o nekim minusima.
Sjećate se kako morate izričito izjaviti potrebnu količinu memorije? To znači da će niz pronaći mjesto koje će točno odgovarati vašoj veličini. Ne postoji jamstvo da će moći stati više od onoga što imate (jer memorijski blok odmah iza njega može biti zauzet).
Povratak na našu analogiju prtljage: mislite na to kao da bi Timmy trebao spremiti 2 komada prtljage i B4može pohraniti točno 2 komada prtljage, pa je dodijele Timmyju. Sad iz nekog razloga Timmy želi spremiti još jedan komad prtljage, ali B4ne može spremiti 3 komada, samo 2, pa što rade?
Uzimaju svu njegovu postojeću prtljagu, premještaju je na novo mjesto u koje može stati više od 3 komada, a zatim ih sve spremaju zajedno.
To je skupa operacija, ali točno tako djeluje i memorija!
U Rubyu ne morate deklarirati određenu veličinu prije nego što je ručno , ali to je zato što Ruby automatski obrađuje to pomoću dinamičkih polja.
Ono što dinamički niz čini jest da će se, ako se niz približi punom kapacitetu, automatski deklarirati novi, veći niz i premjestiti sve postojeće elemente u njega, a stari niz tada se prikuplja smeće. Koliko veći? Faktor rasta je obično 2; dvostruka veličina trenutnog niza.
Zapravo, ne vjerujte mi na riječ .
Ruby ima ObjectSpace modul koji nam omogućuje interakciju s trenutnim objektima koji žive u memoriji. Ovim modulom možemo zaviriti u upotrebu memorije našeg dinamičkog niza - zvuči točno onako kako želimo!
Napisao sam malu Ruby skriptu koja izračunava faktor rasta dinamičkog niza. Slobodno ga pogledajte ovdje, a ako to učinite, možete vidjeti da Rubyovi nizovi imaju faktor rasta 1,5x (to jest, čine polje koje je 50% veće na svakoj kopiji).
Znam što su nizovi, koji su povezani popisi?
Imajte na umu da iako se nizovi i povezani popisi smatraju linearnom strukturom podataka, oni imaju jednu veliku razliku među sobom.
Elementi u nizu pohranjuju se doslovno tik jedan do drugoga u memoriju (tako da možemo imati indeks za brza pretraživanja). Ali čvorovi na povezanim popisima nemaju takva ograničenja (zbog čega ne postoji pretraživanje indeksa za povezane popise) - svaka se stavka može pohraniti bilo gdje u memorijskom bloku.
Gotovo kao da Timmy pokušava spremiti 5 komada prtljage, a vratar nema mjesta i odluči ih ostaviti svugdje. Zvuči neorganizirano?
Ako su pohranjeni na različitim mjestima, kako znati koje su vrećice Timmyjeve? Savjet: Samo pratite sljedeći čvor / vreću! U našem slučaju, vratar ih čuva odvojeno, ali s oznakom na svakoj od njih koja upućuje na sljedeću vreću.
Čvor na povezanom popisu sastoji se od dva dijela - podatkovnog dijela i pokazivača na sljedeći čvor. Na taj su način oni u stanju održavati njegov lineardio - oni i dalje imaju koncept reda, samo ih ne moraju doslovno čuvati u redu!
node = [ data | pointer ]
Na primjer, s obzirom na sljedeći primjer pohranjen u memoriji:
[C | D] [A | B] [B | C] [D | nil]
Izgleda da ovi dijelovi nisu u redu - ali da sam vam rekao da je prvi element A, mogli biste mi reći točan redoslijed popisa:
list = [A -> B -> C ->D -> nula]
Puno zanimljivih stvari možete učiniti s povezanim popisima u koje ovdje neću zalaziti (također puno na Big O o kojem nisam razgovarao). Ali već postoji mnoštvo dobrih članaka o strukturama podataka. Ako ste uspjeli ovdje, predlažem vam da pročitate s Aliina blogova ovdje.
hvala u, dalje: uvod u povezane popise
U ovom ćemo postu govoriti o strukturi povezanih podataka na popisu na jeziku "hvala u, sljedeći" od ... dev.to
Ovdje također možete pročitati više o Popisima / Protivima na Wiki.
Završna riječ
U početku sam ovaj članak napisao za malo drugačiju temu - [Elixir | Zašto povezani popisi?], Ali ustanovio sam da je predugo trebalo objasniti kako nizovi rade prije nego što sam uspio objasniti zašto Elixir koristi povezane popise. Stoga sam ih razdvojio u dva članka.
U tom članku govorim o tome zašto funkcionalni jezici koriste povezane popise kao svoju linearnu strukturu podataka. Pogledajte!
[Eliksir | Zašto povezane liste? ]
Oduvijek sam smatrao da su podatkovne strukture cool, ali znate što je hladnije? Vidjevši ih u divljini! Dok prolazim kroz ... od
Izvori
- //medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Ovdje sam saznao za dodatne
ObjectSpacemetode zahtijevajući
Izvorno objavljeno na dev.to