Structuri de date

Calculatoarele pot stoca și prelucra cantități mari de date. Structurile formale de date permit unui programator să structureze mental cantități mari de date în relații gestionabile conceptual.

Uneori folosim structuri de date pentru a ne permite să facem mai multe: de exemplu, pentru a realiza căutarea sau sortarea rapidă a datelor. Alteori, folosim structuri de date astfel încât să putem face mai puțin: de exemplu, conceptul de stivă este o formă limitată a unei structuri de date mai generale. Aceste limitări ne oferă garanții care ne permit să argumentăm mai ușor despre programele noastre. Structurile de date oferă, de asemenea, garanții cu privire la complexitatea algoritmică – alegerea unei structuri de date adecvate pentru un job este crucială pentru scrierea unui software bun.

Deoarece structurile de date sunt abstracții de nivel superior, ele ne prezintă operațiuni pe grupuri de date, cum ar fi adăugarea unui element la o listă sau căutarea elementului cu cea mai mare prioritate într-o coadă. Când o structură de date oferă operațiuni, putem numi structura de date un tip de date abstracte (uneori abreviat ca ADT – abstract data type). Tipurile de date abstracte pot reduce la minimum dependențele din codul dvs., ceea ce este important atunci când codul dvs. trebuie modificat. Deoarece sunteți abstractizat  departe de la detaliile de nivel inferior, unele dintre elementele comune de nivel superior pe care o structură de date le partajează cu o structură de date diferită pot fi utilizate pentru a le înlocui pe una cu cealaltă.

Limbajele noastre de programare sunt echipate cu un set de tipuri încorporate, cum ar fi numere întregi și numere cu virgulă mobilă, care ne permit să lucrăm cu obiecte de date pentru care procesorul mașinii are suport nativ. Aceste tipuri încorporate sunt abstracții ale ceea ce procesorul oferă de fapt, deoarece tipurile încorporate ascund detalii atât despre execuția cât și despre limitările lor.

De exemplu, atunci când folosim un număr cu virgulă mobilă, ne preocupă în primul rând valoarea și operațiunile care îi pot fi aplicate. Luați în considerare calcularea lungimii unei hipotenuze:

let c := sqrt(a * a + b * b)

Codul mașinii generat din cele de mai sus ar folosi modele comune pentru calcularea acestor valori și acumularea rezultatului. De fapt, aceste tipare sunt atât de repetitive încât au fost create limbaje la nivel înalt pentru a evita această redundanță și pentru a permite programatorilor să se gândească la ce valoare a fost calculată în loc de cum a fost calculată.

Aici sunt în joc două concepte utile și conexe:

  • Încapsularea este atunci când modelele comune sunt grupate împreună sub un singur nume și apoi parametrizate, pentru a obține o înțelegere la nivel superior a acelui model. De exemplu, operația de multiplicare necesită două valori sursă și scrie produsul acestor două valori într-o destinație dată. Operațiunea este parametrizată atât de surse, cât și de destinația unică.
  • Abstracția este un mecanism pentru a ascunde detaliile de implementare ale unei abstracții departe de utilizatorii abstracției. De exemplu, atunci când înmulțim numerele, nu este nevoie să cunoaștem tehnica utilizată efectiv de procesor, ci doar să îi cunoaștem proprietățile.

Un limbaj de programare este atât o abstracție a unei mașini, cât și un instrument pentru a încapsula detaliile interioare ale mașinii. De exemplu, un program scris într-un limbaj de programare poate fi compilat pe mai multe arhitecturi de mașini diferite atunci când acel limbaj de programare încapsulează suficient utilizatorul departe de orice mașină.

Aici, luăm în considerare abstracția și încapsularea conform căreia limbajele noastre de programare oferă un pas mai departe: când aplicațiile devin mai complexe, abstracțiile limbajelor de programare devin la un nivel prea scăzut pentru a fi gestionate eficient. Astfel, ne construim propriile abstracții pe deasupra acestor constructe de nivel inferior. Putem chiar construi abstracții suplimentare pe deasupra acestor abstracții. De fiecare dată când construim în sus, pierdem accesul la detaliile de implementare de nivel inferior. Deși pierderea unui astfel de acces ar putea părea a fi un compromis negativ, este de fapt o afacere: ne preocupăm în primul rând să rezolvăm problema la îndemână, mai degrabă decât să luăm decizii banale care ar fi putut fi înlocuite la fel de arbitrar cu o altă decizie. Când putem gândi la niveluri superioare, ne scutim de aceste poveri.

Fiecare structură de date pe care o acoperim aici poate fi gândită ca o singură unitate care are un set de valori și un set de operații care pot fi efectuate pentru a accesa sau modifica aceste valori. Structura de date în sine poate fi înțeleasă ca un set de operațiuni ale structurii de date împreună cu proprietățile fiecărei operațiuni (adică, ce face operațiunea și cât ne-am putea aștepta să dureze).

Notarea Big-oh este un mod obișnuit de a exprima performanța unui cod de computer. Notarea creează o relație între numărul de elemente din memorie și performanța medie pentru o funcție. Pentru un set de n elemente, O(n) indică faptul că o anumită funcție va opera în medie pe setul de ori. O(1) indică faptul că funcția efectuează întotdeauna un număr constant de operații indiferent de numărul de articole. Notarea reprezintă doar complexitatea algoritmică, astfel încât o funcție poate efectua mai multe operații, dar la multiplii constanți ai lui n se renunță prin convenție.

Nodul

Prima structură de date pe care o discutăm este structura de nod. Un nod este pur și simplu un container pentru o valoare, plus un pointer către un nod „următor” (care poate fi null).

Cele de mai sus reprezintă o abstracție a unei structuri:

În unele limbaje, structurile sunt numite înregistrări sau clase. Unele alte limbaje nu oferă suport direct pentru structuri, dar permit în schimb să fie construite din alte constructe (cum ar fi tupluri sau liste).

Aici, ne preocupă doar faptul că nodurile conțin valori de o anumită formă, așa că spunem pur și simplu că tipul său este „element”, deoarece tipul nu este important. În unele limbaje de programare nu trebuie specificat vreodată niciun tip (ca în limbaje tastate dinamic, cum ar fi Scheme, Smalltalk sau Python). În alte limbaje, este posibil ca tipul să fie restricționat la întreg sau șir (ca în limbajele tipizate static, cum ar fi C). În alte limbaje, decizia de tip a elementului conținut poate fi întârziată până când tipul este efectiv utilizat (ca în limbajele care acceptă tipuri generice, cum ar fi C++ și Java). În oricare dintre aceste cazuri, traducerea pseudocodului în propriul limbaj ar trebui să fie relativ simplă.

Fiecare dintre operațiile de nod specificate poate fi implementată destul de ușor:

// Creați un nod nou, cu v ca valoare conținută și apoi ca
// valoarea următorului pointer
function make-node(v, node next): node
let result := new node {v, next}
return result
end

// Returnează valoarea conținută în nodul n
function get-value(node n): element
return n.value
end

// Returnează valoarea următorului pointer al nodului n
function get-next(node n): node
return n.next
end

// Setează valoarea conținută a lui n ca v
function set-value(node n, v)
n.value := v
end

// Setează valoarea următorului pointer al nodului n pentru a fi new-next
function set-next(node n, new-next)
n.next := new-next
return new-next
end
În principal, suntem mai preocupați de operațiuni și strategia de implementare decât de structura în sine și de implementarea la nivel scăzut. De exemplu, suntem mai preocupați de cerința de timp specificată, care afirmă că toate operațiunile necesită timp care este O(1). Implementarea de mai sus îndeplinește aceste criterii, deoarece durata de timp a fiecărei operațiuni este constantă. O altă modalitate de a gândi operațiuni în timp constant este să le gândiți ca operații a căror analiză nu depinde de nicio variabilă.

Deoarece un nod este doar un container atât pentru o valoare, cât și un container către un pointer către un alt nod, nu ar trebui să fie surprinzător cât de banală este structura de date a nodului în sine (și implementarea sa).

Construirea unui lanț din noduri

Deși structura nodului este simplă, ne permite de fapt să calculăm lucruri pe care nu le-am fi putut calcula doar cu numere întregi de dimensiuni fixe.

Dar mai întâi, vom analiza un program care nu are nevoie să utilizeze noduri. Următorul program va citi (dintr-un flux de intrare; care poate fi de la utilizator sau dintr-un fișier) o serie de numere până când se ajunge la sfârșitul fișierului și apoi va afișa care este cel mai mare număr și media tuturor numerelor :

program(input-stream in, output-stream out)
let total := 0
let count := 0
let largest := -∞

while has-next-integer(in):
let i := read-integer(in)
total := total + i
count := count + 1
largest := max(largest, i)
repeat

println out „Maximum: ” largest

if count != 0:
println out „Average: ” (total / count)
fi
end
Dar acum luați în considerare rezolvarea unei sarcini similare: citiți într-o serie de numere până când se ajunge la sfârșitul fișierului și afișați cel mai mare număr și media tuturor numerelor care împart în mod egal cel mai mare număr. Această problemă este diferită, deoarece este posibil ca cel mai mare număr să fie ultimul introdus: dacă trebuie să calculăm media tuturor numerelor care împart acel număr, va trebui să ne amintim cumva pe toate. Am putea folosi variabile pentru a ne aminti numerele anterioare, dar variabilele ne-ar ajuta să rezolvăm problema numai atunci când nu sunt introduse prea multe numere.

De exemplu, să presupunem că ar trebui să luăm în considerare 200 de variabile pentru a păstra starea introdusă de utilizator. Și, în plus, să presupunem că fiecare dintre cele 200 de variabile a avut 64 de biți. Chiar dacă am fi foarte deștepți cu programul nostru, acesta ar putea calcula rezultatele doar pentru 264∙200 tipuri diferite de intrare. În timp ce acesta este un număr foarte mare de combinații, o listă de 300 de numere pe 64 de biți ar necesita chiar mai multe combinații pentru a fi codate corespunzător. (În general, se spune că problema necesită spațiu liniar. Toate programele care au nevoie doar de un număr finit de variabile pot fi rezolvate în spațiu constant.)

În loc să includem limitări care complică codificarea (cum ar fi faptul că avem doar un număr constant de variabile), putem folosi proprietățile abstractizării nodului pentru a ne permite să ne amintim cât de multe numere poate păstra computerul nostru:

program(input-stream in, output-stream out)
let largest := -∞
let nodes := null

while has-next-integer(in):
let i := read-integer(in)
nodes := make-node(i, nodes) // conțin valoarea i,
// și amintește și numerele anterioare
largest := max(largest, i)
repeat
println out „Maximum: ” largest

// acum calculează mediile tuturor factorilor cei mai mari
let total := 0
let count := 0
while nodes != null:
let j := get-value(nodes)
if j divides largest:
total := total + j
count := count + 1
fi
nodes := get-next(nodes)
repeat
if count != 0:
println out „Average: ” (total / count)
fi
end
Mai sus, dacă n numere întregi sunt citite cu succes, vor fi efectuate n apeluri către make-node. Acest lucru va necesita realizarea a n noduri (care necesită suficient spațiu pentru a menține valoarea și câmpurile următoare ale fiecărui nod, plus gestionarea internă a memoriei), astfel încât cerințele de memorie vor fi de ordinul O(n). În mod similar, construim acest lanț de noduri și apoi iterăm din nou peste lanț, ceea ce va necesita O(n) pași pentru a face lanțul, și apoi încă O(n) pași pentru a itera peste el.

Rețineți că, atunci când iterăm numerele din lanț, le privim de fapt în ordine inversă. De exemplu, să presupunem că numerele introduse în programul nostru sunt 4, 7, 6, 30 și 15. După atingerea EOF, lanțul de noduri va arăta astfel:

Structuri de date

Astfel de lanțuri sunt mai des denumite liste legate. Cu toate acestea, în general preferăm să gândim în termeni de liste sau secvențe, care nu au un nivel la fel de scăzut: conceptul de legătură este doar un detaliu de implementare. În timp ce o listă poate fi făcută cu un lanț, aici acoperim câteva alte modalități de a face o listă. Pentru moment, ne pasă mai mult de capacitățile de abstractizare ale nodului decât de unul dintre modurile în care este utilizat.

Algoritmul de mai sus folosește doar funcțiile make-node, get-value și get-next. Dacă folosim set-next putem schimba algoritmul pentru a genera lanțul astfel încât acesta să păstreze ordinea originală (în loc să o inversăm).

program (input-stream in, output-stream out) let largest := -∞ let nodes := null let tail_node := null while has-next-integer (in): let i := read-integer (in) if (nodes == null) nodes := make-node(i, null) // construiește primul nod din listă tail_node := nodes // există un nod în listă => primul și ultimul sunt la fel else tail_node := set-next (tail_node, make-node (i, null)) // adaugă un nod nou la sfârșitul listei largest := max(largest, i) repeat println out „Maximum: ” largest // acum calculează mediile tuturor factorilor cei mai mari let total := 0 let count := 0 while nodes != null: let j := get-value(nodes) if j divides largest: total := total + j count := count + 1 fi nodes := get-next(nodes) repeat if count != 0: println out „Average: ” (total / count) fi end

Include texte traduse din Wikipedia

Rolul social media în democrație, noul management public, și guvernanța electronică
Rolul social media în democrație, noul management public, și guvernanța electronică

O resursă esențială pentru oricine dorește să înțeleagă intersecția în evoluție dintre tehnologie și guvernare.

Nu a fost votat 9.53 lei20.97 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.
Traducere şi traducători
Traducere şi traducători

Ghidul esențial pentru toți cei pasionați de arta traducerii și complexitatea comunicării interculturale.

Nu a fost votat 14.32 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.
Inteligența competitivă - Concept - Studii
Inteligența competitivă – Concept – Studii

Inteligența competitivă: instrumentul esențial pentru succesul în afaceri

Nu a fost votat 9.53 lei15.08 lei Selectează opțiunile Acest produs are mai multe variații. Opțiunile pot fi alese în pagina produsului.

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *