de Edison Yap

O prezentare generală a modului în care funcționează matricele

O prezentare generala a modului in care functioneaza matricele
matrici – cum funcționează?

În informatică, există conceptul de a structura liniară a datelor, ceea ce înseamnă că datele sunt structurate într-un mod liniar în care ordinea contează. Sunt Matrice și Liste conectate, dar astăzi voi vorbi mai ales despre tablouri și puțin despre listele legate.

Majoritatea limbajelor orientate spre obiecte vin cu Matrice, întrucât majoritatea flimbajele unctionale vin cu Liste conectate (vezi de ce într-un alt articol al meu, menționat în partea de jos a acestui articol).

Există un motiv bun pentru această diferențiere în care ne vom scufunda mai târziu. Deocamdată să aruncăm o privire rapidă asupra diferențelor dintre cele două structuri de date. Pentru a face acest lucru, va trebui să facem o călătorie pe banda de memorie.

Timp de derulare înapoi

Obiectele și funcțiile și tot ceea ce știm despre computere sunt stocate fundamental în biți și octeți în computer.

În limbi precum Java și C, trebuie să declarați în mod explicit dimensiunea unui tablou în prealabil.

Stai, dar Ruby nu face asta?

În Ruby, folosim Array pentru structurile noastre de date liniare. Putem adăuga lucruri aparent infinite într-o matrice Ruby și nu ar conta în ceea ce ne privește.

E grozav, nu-i așa ?! Asta înseamnă că matricile sunt infinit mare nu? Și Ruby este limba superioară? Norocul nostru!

Dar nu atât de repede. * îți apare balonul *

Nu sunt tablouri de dimensiuni infinite; ceea ce vedeți în Ruby este ceea ce noi numim a Matrice dinamică, și vine cu un cost.

Pentru a înțelege ce sunt matricele dinamice, să aruncăm mai întâi o privire la modul în care sunt reprezentate matricele în memorie. Deoarece MRI Ruby (Matz ‘Ruby Interpreter) compilează până la codul C, vom analiza modul în care sunt reprezentate matricile în C.

C-ing este să crezi

Ne vom scufunda într-un pic de cod C pentru a ne ajuta C un pic mai bine … 🙂

În limbaje de nivel inferior, cum ar fi C, trebuie să vă ocupați cu indicatorii și cu alocarea memoriei. Chiar dacă nu ați mai avut de-a face cu C înainte (disclaimer – nici eu nu am), este posibil să aveți C-een unul dintre cele mai (celebre) exemple de mai jos:

Să descompunem acest bit de cod:

  • malloc nu are nicio semnificație magică în spatele ei, literalmente înseamnă memory allocation
  • malloc returnează un indicator
  • malloc acceptă un argument, care este dimensiunea memoriei pe care doriți să o aloce programul pentru dvs.
  • 100 * sizeof(int) spune programului că vrem să stocăm 100 de numere întregi, deci alocați-ne 100 * dimensiunea a ceea ce ar ocupa fiecare număr întreg.
  • ptr/ pointer stochează referințe la adresa memoriei.

Timmy depozitează bagaje!

Dacă exemplul de mai sus nu prea avea sens, încercați această analogie. Gândiți-vă la alocarea memoriei ca la un concierge pentru bagaje. Funcționează așa:

  • Timmy se duce la tejghea, îi spune conciergei că are 2 bagaje, cam acest mare și că ar vrea să le depoziteze în depozit.
  • Portarul aruncă o privire la camera de depozitare și spune: „Da, avem niște camere la locul desemnat B4 zona și va aloca acel spațiu pentru a vă depozita bagajele “.
  • Îi întind lui Timmy a card de ridicare cu zona desemnată pe ea, B4 în cazul nostru.
  • Timmy este fericit, merge în jur făcând orice și când vrea să-și ridice bagajele, se întoarce la tejghea și le arată card de ridicare. „Ai cumpărat bagajele mele?

În exemplul nostru, bagajul lui Timmy este date, cardul de preluare este indicatorul (indică unde este depozitată geanta lui Timmy). Locul în care concierge depozitează bagajele lui Timmy este bloc de memorie, iar contorul este program.

Arătând contorul (programul) Cartea lui Timmy (pointer / adresa de memorie), Timmy își poate recupera bagajele (date). Primă? Pentru că știu exact unde este depozitată geanta lui Timmy – B4, asta înseamnă că pot prelua relativ rapid toate bagajele lui Timmy!

De asemenea, m-am întrebat vreodată de ce accesați elemente în matrice cu index, ca astfel?

Acest lucru se datorează faptului că matricea conține referințele la blocul de memorie, iar indexul îi spune decalaj.

O analogie pentru asta este dacă vă rog să-l căutați pe Timmy într-o coadă de 20 de persoane, în mod logic ar trebui să-i întrebați pe fiecare dintre ei dacă erau Timmy. Dar, dacă ți-aș spune că Timmy este al șaselea (index) de la prima persoană (indicatorul original), știi exact unde să te uiți.

Recuperarea elementelor în tablouri este rapidă tocmai din această cauză – programul nu trebuie să caute toate cele 100 de elemente pentru a găsi ceea ce căutați. Dacă aveți indexul, trebuie doar să adăugați offset-ul la adresa de memorie originală, iar droidul pe care îl căutați va fi chiar acolo!

Ce sunt matricele dinamice atunci?

Așa că v-am spus puțin despre modul în care sunt reprezentate matricele în memorie, dar acum este timpul să vorbim despre unele contra.

Vă amintiți cum trebuie să declarați în mod explicit cantitatea de memorie de care aveți nevoie? Aceasta înseamnă că matricea va găsi un loc care să se potrivească exact dimensiunii dvs. Nu există nicio garanție că se va potrivi mai mult decât ceea ce aveți (deoarece blocul de memorie din spatele acestuia ar putea fi ocupat).

Înapoi la analogia bagajelor noastre: gândiți-vă la asta ca și cum Timmy ar fi trebuit să stocheze 2 bagaje și B4pot stoca exact 2 bagaje, așa că le alocă lui Timmy. Acum, dintr-un anumit motiv, Timmy vrea să stocheze un alt bagaj, dar B4 nu pot stoca 3 bucăți, doar 2, deci ce fac?

Își iau toate bagajele existente, le mută într-un loc nou, care poate încadra mai mult de 3 piese, apoi le depozitează împreună.

Aceasta este o operațiune costisitoare, dar este exact modul în care funcționează și memoria!

În Ruby, nu trebuie să declarați o dimensiune specifică înainte de mână, dar asta pentru că Ruby îl gestionează automat pentru dvs. prin intermediul matricelor dinamice.

Ceea ce face o matrice dinamică este că, dacă matricea se apropie de capacitatea sa maximă, va declara automat o matrice nouă mai mare și va muta toate elementele existente în ea, iar matricea veche este apoi colectată la gunoi. Cât de mare? Factorul de creștere este obișnuit 2; dubla dimensiunea matricei curente.

De fapt, nu mă crede pe cuvânt.

Ruby are un Modulul ObjectSpace care ne permite să interacționăm cu obiecte actuale care trăiesc în memorie. Putem folosi acest modul pentru a arunca o privire asupra utilizării memoriei matricei noastre dinamice – sună exact ca ceea ce ne dorim!

Am scris un mic script Ruby care calculează factorul de creștere al matricei dinamice. Simțiți-vă liber să aruncați o privire aici, și dacă faceți acest lucru, puteți vedea că matricile Ruby au un factor de creștere de 1,5x (adică fac o matrice cu 50% mai mare la fiecare copie).

Știu ce sunt matricele, ce sunt listele legate?

Rețineți că, deși matricele și listele legate sunt ambele considerate structuri de date liniare, ele au o diferență mare între ele.

Elementele dintr-o matrice sunt stocate literalmente unul lângă altul în memorie (deci putem avea index pentru căutări rapide). Dar nodurile din listele legate nu au o astfel de restricție (motiv pentru care nu există o căutare a indexului pentru listele legate) – fiecare articol poate fi stocat oriunde pe blocul de memorie.

Este aproape ca și cum Timmy ar încerca să stocheze 5 bagaje, iar concierge nu are spațiu și decide să le lase peste tot. Sună neorganizat?

De asemenea, dacă sunt depozitate în locuri diferite, de unde știi ce genți sunt ale lui Timmy? Sugestie: Țineți evidența următorului nod / geantă! În cazul nostru, concierge le păstrează separat, dar cu o etichetă pe fiecare dintre ele care indică următoarea geantă.

Un nod dintr-o listă legată constă din două părți – partea de date și un indicator către următorul nod. Acesta este modul în care sunt capabili să mențină linear o parte din aceasta – au încă conceptul de ordine, nu trebuie doar să fie stocate în ordine literalmente!

node = [ data | pointer ]

De exemplu, având în vedere următorul exemplu stocat în memorie:

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

Aceste biți par a fi defecte – dar dacă ți-aș fi spus că primul element este A, ați putea să-mi spuneți ordinea exactă a listei:

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

Există o mulțime de lucruri interesante pe care le puteți face cu listele legate pe care nu am de gând să le scufund aici (de asemenea, multe despre Big O despre care nu am vorbit). Dar există deja o mulțime de articole bune despre structurile de date. Dacă ai reușit aici, îți sugerez să citești din postarea lui Ali aici.

Vă mulțumesc, în continuare: o introducere în listele legate
În această postare, vom vorbi despre structura de date a listelor legate în limba „mulțumesc, următor” de …dev.to

De asemenea, puteți citi mai multe despre Listă / Contra Wiki aici.

Notă de închidere

Am scris inițial acest articol pentru un subiect ușor diferit – [ Elixir | Why Linked Lists?], dar am găsit că a durat prea mult timp pentru a explica modul în care funcționează matricile înainte de a fi în măsură să explic de ce Elixir folosește liste legate. Așa că le-am separat în două articole.

În acest articol, vorbesc despre motivele pentru care limbajele funcționale folosesc liste legate ca structură de date liniară. Verifică-l!

[ Elixir | Why Linked Lists? ]
Mereu am crezut că structurile de date sunt interesante, dar știi ce e mai cool? Văzându-i în sălbăticie! În timp ce treceam prin …dev.to

Surse

  1. https://medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 – Aici am aflat despre suplimentar ObjectSpace metode prin necesitatea acestuia

Postat inițial pe dev.to