Matrice dinamică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 31 martie 2015; verificarea necesită 51 de modificări .

O matrice se numește dynamic , a cărei dimensiune se poate modifica în timpul execuției programului. Capacitatea de a schimba dimensiunea distinge o matrice dinamică de una statică, a cărei dimensiune este setată în momentul în care programul este compilat. Pentru a modifica dimensiunea unei matrice dinamice , un limbaj de programare care acceptă astfel de matrice trebuie să ofere o funcție sau un operator încorporat. Matricele dinamice permit lucrul mai flexibil cu datele, deoarece permit să nu prezică volumele de date stocate, ci să ajusteze dimensiunea matricei în conformitate cu volumele necesare efectiv.

De asemenea, uneori, matricele dinamice sunt matrice de lungime variabilă , a căror dimensiune nu este fixă în timpul compilării, ci este setată atunci când tabloul este creat sau inițializat în timpul execuției programului. Ele diferă de matricele dinamice „reale” prin faptul că nu oferă redimensionare automată cu păstrarea conținutului, așa că programatorul trebuie să implementeze o astfel de facilitate dacă este necesar.

Suport în limbaje de programare

Matricele dinamice pot fi suportate fie la nivelul de sintaxă al limbajului de programare în sine, fie la nivelul bibliotecilor de sistem. Descrierea unui tablou dinamic poate fi diferită din punct de vedere sintactic de descrierea unuia static, dar poate fi aceeași. În al doilea caz, de regulă, toate tablourile din limbaj sunt potențial dinamice și depinde de programator dacă să folosească această proprietate în fiecare caz particular. Atunci când sunt suportate de matrice dinamice prin biblioteci de sistem, acestea sunt de obicei implementate ca clase (în sensul OOP ) sau tipuri generice (așa-numitele „șabloane” sau „generice”); declarația de matrice în acest caz este o instanțiere a unei clase sau o instanțiere de tip generic. În funcție de limbaj, tablourile dinamice pot fi doar matrice unidimensionale sau au două sau mai multe dimensiuni.

Suportul pentru matrice dinamice implică prezența obligatorie a unei operații încorporate pentru determinarea dimensiunii curente a unei matrice. Dimensiunea inițială a unui tablou dinamic este fie egală cu zero, fie este setată în timpul descrierii sau inițializării. Redimensionarea ulterioară este efectuată printr-o operație specială încorporată (procedură). În unele limbi (de exemplu , JavaScript , Lua ) extinderea matricei are loc automat atunci când se încearcă să scrie într-o celulă inexistentă.

Implementare

Pentru ca matricele să fie redimensionabile dinamic, implementarea trebuie să găsească o „medie de aur” între mai multe cerințe conflictuale.

Memorie eficientă - Implementarea nu ar trebui să aibă ca rezultat o supraîncărcare semnificativă a memoriei.
Eficiența performanței , care include:
- suprasarcina minimă pentru modificarea dimensiunii matricei;
- salvând, dacă este posibil, un timp constant de acces de citire/scriere la elementele matricei.
Compatibilitate la nivel scăzut cu matrice statice obișnuite . De exemplu, o condiție prealabilă pentru utilizarea unei matrice dinamice în apelurile la funcțiile API ale sistemului de operare poate fi ca elementele matricei să fie plasate într-un bloc contiguu de RAM fizică în ordinea corespunzătoare indexării matricei. Dacă această cerință nu este îndeplinită, matricele dinamice nu pot fi utilizate împreună cu codul de nivel scăzut.

În funcție de prioritatea anumitor cerințe, este selectată metoda de implementare care le îndeplinește.

Matrice de lungime variabilă

Implementarea tablourilor de lungime variabilă diferă puțin de implementarea tablourilor statice obișnuite. O matrice de elemente de tip T de lungime variabilă este de obicei stocată într-un bloc RAM contiguu de dimensiune , unde N este numărul de elemente specificat la descrierea (crearea) matricei. Adică, declararea unui tablou de lungime variabilă, de fapt, maschează pur și simplu alocarea dinamică a memoriei. Diferența poate fi aceea că (de exemplu, ca în C99 și mai târziu) unui tablou cu lungime variabilă i se alocă memorie pe stivă, ca și altor variabile automate, în timp ce modul tipic de alocare a memoriei dinamice (în funcția C ) alocă memorie pe stivă. grămada . De asemenea, pentru o matrice cu lungime variabilă, compilatorul generează, de obicei, automat codul de dealocare a memoriei atunci când matricea declarată iese din domeniul de aplicare. $sizeof(T)\cdot N$ malloc

Mutarea unui tablou în memorie

Cel mai obișnuit pentru limbajele compilate procedurale tipice este implementarea redimensionării unui tablou prin mutarea acesteia în memoria heap.

Pentru matrice este alocat un fragment de RAM, a cărui dimensiune este mai mare decât așa-numitul necesar. dimensiune logică (dimensiune sau lungime). Numărul de elemente care pot fi plasate efectiv în această memorie se numește capacitatea matricei dinamice. Lungimea curentă a matricei este stocată într-un contor separat. Poate fi folosit pentru a determina dimensiunea curentă, precum și pentru a controla depășirea matricei, dacă limbajul acceptă un astfel de control. Astfel, în realitate, o matrice dinamică este o matrice de dimensiune fixă, în care este ocupată doar o parte a celulelor.
Comanda de a mări dimensiunea matricei, dacă noua dimensiune nu depășește capacitatea, pur și simplu schimbă contorul de lungime a matricei la dimensiunea dorită. Nu există nicio modificare a matricei în sine.
O instrucțiune de creștere în care noua dimensiune depășește capacitatea face ca matricea să fie relocată în memorie:

este alocat un nou fragment RAM, a cărui dimensiune depășește dimensiunea matricei;
conținutul matricei este copiat în memoria nou alocată;
dimensiunea și capacitatea matricei sunt actualizate;
în structura de serviciu care stochează parametrii matricei, valoarea pointerului de date este schimbată cu una nouă;
se lansează comanda de eliberare a fragmentului RAM alocat anterior pentru matrice; dacă limbajul acceptă gestionarea automată a memoriei , atunci eliberarea memoriei alocate anterior pentru matrice rămâne cu colectorul de gunoi.

Comanda de reducere a dimensiunii unui tablou poate duce la mișcarea acestuia în memorie dacă, ca urmare a execuției sale, procentul de celule ocupate din matrice scade sub o anumită valoare. Deplasarea în acest caz se efectuează conform aceleiași scheme ca și în cazul comenzii de creștere a matricei.

Această implementare este cea mai eficientă în ceea ce privește viteza de acces la celulele matrice deja alocate. În plus, oferă timp de acces constant la orice element, indiferent de indexul acestuia. Cu toate acestea, suprasarcina suplimentară a operațiunilor de redimensionare poate fi semnificativă. Valoarea acestor costuri depinde de parametrii algoritmului de mutare a matricei.

Capacitatea inițială și creșterea capacității pe măsură ce dimensiunea crește. Poate fi specificat fie ca valoare relativă (o anumită fracțiune din lungimea logică a matricei), fie ca o creștere absolută peste lungimea matricei necesară. Cu cât acești parametri sunt mai mari, cu atât mai târziu, cu același mod de umplere a matricei, va fi necesară următoarea mișcare, dar cu atât mai multă memorie va rămâne nefolosită. Extinderea matricei cu orice factor constant garantează că inserarea a n elemente va dura O(n) timp, ceea ce înseamnă că fiecare inserare durează o anumită perioadă de timp definită. Valoarea numerică a acestui coeficient conduce la diferiți indicatori: timpul mediu de inserare al unei operații este a/(a-1), în timp ce numărul de celule irosite este (a-1)n. Valoarea acestei constante în diferite aplicații și biblioteci poate fi diferită: multe manuale folosesc valoarea 2, dar implementarea ArrayList în limbajul Java utilizează un factor de 3/2, în alte cazuri folosesc a=9/8.
Capacitate minima. Setat de obicei din motive de eficiență, pentru a nu pierde performanța atunci când matricele mici sunt redimensionate frecvent. În practică, setarea înseamnă că toate matricele dinamice mai mici decât capacitatea minimă vor risipi de fapt memoria.
Procentul minim de umplere al matricei. Specifică când va avea loc relocarea după ce matricea a fost redusă în dimensiune. Cu cât această valoare este mai mare, cu atât se va produce mai des mișcarea atunci când dimensiunea matricei scade. Cu cât este mai mică, cu atât mai multă memorie va rămâne ocupată, dar nu va fi folosită atunci când dimensiunea matricei este redusă.

Există diverse estimări ale valorilor optime pentru parametrii algoritmului de mișcare, dar din considerații generale este clar că niciuna dintre metodele de determinare a acestora nu garantează eficiența maximă în toate cazurile și pentru oricare este posibil să se aleagă un algoritm. pentru lucrul cu o matrice, în care mutarea va fi ineficientă. Pentru a compensa efectele negative, multe limbi care acceptă matrice dinamice au parametri suplimentari în comenzile de creștere / scădere a matricei care vă permit să controlați direct capacitatea matricei. Dacă programatorul știe cu siguranță până la ce dimensiune va crește/scădea matricea ca urmare a uneia sau aceleia operațiuni și cum va fi procesată matricea în viitor, el poate specifica direct capacitatea finală necesară în comanda de redimensionare, evitând astfel un număr mare de mișcări fără sens.

Alți algoritmi de alocare dinamică

Există mulți algoritmi pentru implementarea matricelor dinamice, pe lângă cei de mai sus. Astfel, este posibilă implementarea altor structuri diferite de date cu ajutorul celulelor de memorie dinamice conectate prin legături. Cele mai multe dintre aceste metode oferă un avantaj în anumite condiții specifice, dar fie nu oferă timp de acces constant, fie sunt incompatibile cu matricele statice și, prin urmare, nu pot funcționa cu cod de nivel scăzut.

Utilizare

Matricele dinamice sunt folosite pentru a procesa seturi de date omogene a căror dimensiune nu este cunoscută exact în momentul scrierii programului, dar care pot încadra în memoria disponibilă. Fără utilizarea matricelor dinamice, soluția unor astfel de probleme se reduce la una dintre următoarele strategii:

alocarea unui tablou static de dimensiuni mari, evident suficient pentru plasarea completă a datelor;
utilizarea unei matrice statice ca un buffer în care datele sunt încărcate în părți;
utilizarea altor structuri de date dinamice (de exemplu, liste).

Prima opțiune este aplicabilă numai atunci când dimensiunea setului de date se modifică într-un interval mic, strict limitat (de exemplu, în procesarea de text, o limită de 1000 de caractere pe linie este destul de acceptabilă). În caz contrar, alegerea unei matrice mici va limita funcționalitatea programului, iar una mare (astfel încât să fie cu siguranță suficientă pentru orice date de intrare) va duce la o utilizare ineficientă a memoriei. Procesarea tamponării complică algoritmul, iar alte structuri dinamice în sarcinile de procesare a secvențe mari de date simple nu pot fi comparate cu o matrice în termeni de eficiență.

Utilizarea matricelor dinamice vă permite să alocați exact atâta memorie cât este cu adevărat necesar (imediat, dacă sarcina vă permite să determinați cantitatea înainte de a încărca datele sau în timpul încărcării, extinzând matricea după cum este necesar), încărcați toate datele într-una singură matrice și procesați-le uniform. Cu toate acestea, această strategie are și dezavantaje:

scăderea vitezei din cauza costurilor generale pentru modificarea dimensiunii unui tablou dinamic;
potențiala scădere a fiabilității: cu o cantitate extrem de mare de date de intrare, o încercare de a crește matricea la dimensiunea corespunzătoare poate duce la o încetinire semnificativă bruscă sau chiar la eșecul programului din cauza lipsei de memorie liberă.

În general, se poate observa că suportul matricelor dinamice mărește comoditatea dezvoltării, dar nu scutește programatorul de nevoia de a evalua nevoile de memorie ale programului; de asemenea, necesită înțelegerea caracteristicilor unei implementări specifice de matrice dinamice și potrivirea algoritmilor de procesare a datelor cu aceste caracteristici.

Exemple

Pascal

Matricele dinamice sunt acceptate de Delphi , FreePascal , dar nu de Turbo Pascal .

var byteArray : Matrice de octeți ; // Matrice unidimensională multiArray : Matrice de șir de caractere ; // Matrice multidimensională ... începe ... // Setați dimensiunea unui tablou unidimensional la n elemente SetLength ( byteArray , n ) ; // Accesul la o matrice dinamică este similar cu accesul la unul obișnuit. // Indexarea începe întotdeauna de la zero, indicii sunt întotdeauna numere întregi. byteArray [ 0 ] := 10 ; // Redimensionați la m elemente. SetLength ( byteArray , m ) ; ... // Setați dimensiunea unui tablou bidimensional la elementele X*Y SetLength ( multiArray , X , Y ) ; multiArray [ 7 , 35 ] := 'ru.wikipedia.org' ; ... sfârşitul .

Xi

Nu există matrice dinamice în limbajul C în sine, dar biblioteca standard funcționează mallocși freevă reallocpermite să implementați o matrice de dimensiune variabilă:

int * mas = ( int * ) malloc ( sizeof ( int ) * n ); // Creați o matrice de n elemente de tip int ... mas = ( int * ) realloc ( mas , sizeof ( int ) * m ); // Schimbați dimensiunea matricei de la n la m, păstrând conținutul ... liber ( mas ); // Eliberarea memoriei după utilizarea matricei

Dezavantajul acestei abordări este necesitatea de a calcula dimensiunea memoriei alocate, de a aplica o conversie explicită de tip și de a monitoriza cu atenție durata de viață a matricei (cum este întotdeauna cazul memoriei alocate dinamic în C).

O matrice dinamică multidimensională poate fi creată ca o matrice de pointeri către matrice:

int ** A = ( int ** ) malloc ( N * sizeof ( int * )); pentru ( int i = 0 ; i < N ; i ++ ) { A [ i ] = ( int * ) malloc ( M * sizeof ( int )); }

Cu toate acestea, creșterea dimensiunii complică în mod semnificativ procedurile de creare a unei matrice și de eliberare a memoriei după ce utilizarea acesteia este completă. Sarcina de a redimensiona o matrice de-a lungul uneia sau mai multor coordonate devine și mai complicată.

Unele compilatoare C oferă o funcție de bibliotecă non-standard void *alloca(size_t size)care facilitează oarecum lucrul cu matrice dinamice. Această funcție alocă memorie nu pe heap, cum ar fi malloc, ci pe stivă, iar această memorie este eliberată automat când se ajunge la operator return. Adică, atunci când o matrice dinamică este alocată de această funcție, nu trebuie să fie șters manual, dar o astfel de matrice nu poate fi returnată de la funcție la punctul de apel.

De la versiunea standardului C99 , în limbaj au fost introduse matrice de lungime variabilă. În sintaxa obișnuită pentru declararea unei matrice C, în locul mărimii matricei, poate fi indicată nu numai o constantă, ci și o variabilă de tip întreg:

void func ( int arraySize ) { intmas [ arraySize ] ; // Descrierea unui tablou cu lungime variabilă pentru ( int i = 0 ; i < arraySize ; ++ i ) { mas [ i ] = anotherFunc ( i ); // Faceți referire la elementele matricei } ... }

O matrice cu lungime variabilă poate fi setată la orice dimensiune dorită în momentul creării. Memoria pentru aceasta este alocată pe stivă. O matrice de lungime variabilă există până când iese din domeniul în care a fost declarată, după care memoria sa este eliberată automat. Ca și în cazul precedent, o matrice de lungime variabilă nu poate fi returnată de la o funcție către apelant.

C++

Biblioteca standard oferă o clasă de șablon std::vector[1] care implementează funcționalitatea unui tablou dinamic:

// Declaram o matrice mas, continand initial numerele 1 - 5: std :: vector < int > mas = { 1 , 2 , 3 , 4 , 5 }; mas . rezerva ( 100 ); // Rezervați spațiu de stocare pentru cel puțin 100 de articole fără a modifica dimensiunea reală. Conținutul rămâne același. mas . redimensionare ( 50 ); // Setați dimensiunea explicită la exact 50 de elemente. Elementele lipsă vor primi valoarea „implicit”, elementele suplimentare vor fi eliminate. mas [ i ] = i ; // Atribui i-lea element valoarea i mas . push_back ( 100 ); // Adăugați un element la sfârșitul tabloului int x = mas . spate (); // Accesați ultimul element, în acest exemplu x == 100 mas . pop_back (); // Elimina ultimul element std :: cout << mas . dimensiune () << " " << mas . capacitate () << " \n " ; // Capacitatea de afișare și dimensiunea reală auto mas2 = mas ; // Variabila mas2 conține o copie completă a mas

std::vectorare multe metode și operatori, dintre care unele sunt prezentate în exemplul de mai sus. Ele vă permit să accesați prin index, să schimbați dimensiunea matricei în orice direcție, să o utilizați ca stivă, să scrieți o nouă valoare într-o poziție arbitrară a matricei (cu o schimbare a elementelor rămase) și, în general, să susțină semantica de tipul valorii : copiere, schimb, mutare, transfer într-o funcție și returnare, comparare element-wise cu un alt obiect de același tip. Gestionat nu este doar dimensiunea reală, ci și capacitatea, care vă permite să optimizați procesul de alocare a memoriei.

std::vectorimplementează principiul RAII : deține subobiectele sale, alocă și eliberează memorie și apelează corect constructori/destructori.

Standardul C++ necesită o implementare care să îndeplinească următoarele condiții:

toate elementele matricei trebuie să fie stocate într-un rând în ordinea creșterii indicelui într-un bloc integral de RAM;
trebuie garantat un timp de acces constant la un element arbitrar.

Lucrările de nivel scăzut cu memorie dinamică pot fi implementate prin mijloace moștenite din limba strămoșilor , dar pentru a asigura siguranța tipului și pentru a respecta cerințele modelului obiect, se recomandă alocarea memoriei pentru matrice folosind operatori specifici limbajului new []și delete []:

// Alocați memorie pentru o matrice int de lungime n int * mas = new int [ n ]; ... // Eliberarea memoriei matricei delete [] mas ;

Printre altele, acest lucru vă permite să redefiniți operatori pentru tipurile definite new []de utilizator delete []și, astfel, să implementați propriile scheme de alocare a memoriei.

În C++ modern, managementul manual al memoriei este o bază esențială pentru implementarea containerelor de șabloane, dar prezintă dificultăți semnificative chiar și pentru programatorii experimentați și nu este recomandat pentru utilizare în codul aplicației. [2] [3]

Note

↑ std::vector - cppreference.com . Preluat la 16 octombrie 2021. Arhivat din original la 28 iunie 2011. (nedefinit)
↑ Ghid de bază C++: R.1: Gestionați automat resursele folosind mânerele de resurse și RAII (Achiziția resurselor este inițializarea) . Preluat la 16 octombrie 2021. Arhivat din original la 8 februarie 2020. (nedefinit)
↑ Ghid de bază C++: R.11: Evitați apelarea la noi și ștergeți explicit . Preluat la 16 octombrie 2021. Arhivat din original la 8 februarie 2020. (nedefinit)

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă