Matrice dinamică
În informatică , un vector dinamic , vector expandabil, vector redimensionabil , tabel dinamic sau listă de matrice este o structură de date matrice care poate fi redimensionată și vă permite să adăugați sau să eliminați elemente. Acesta vine cu biblioteca standard în multe limbaje de programare majore moderne.
Un tablou dinamic nu este același cu un tablou alocat dinamic : acesta din urmă este un tablou de dimensiuni fixe atunci când tabloul în sine este alocat sau instanțiat; pentru mai multe informații despre acest tip de matrice, consultați matrice .
Tablouri dinamice de mărime și capacitate delimitate
Cea mai simplă matrice este construită alocând o matrice de dimensiuni fixe și împărțind-o în două părți: prima stochează elementele matricei dinamice, iar a doua este rezervată sau neutilizată. Acum este posibil să adăugați sau să eliminați elemente la sfârșitul matricei dinamice în timp constant folosind spațiul rezervat, până când acest spațiu este complet consumat. Numărul de elemente utilizate pentru conținutul matricei dinamice este dimensiunea sa logică (sau, pur și simplu, dimensiunea ), în timp ce dimensiunea matricei subiacente se numește capacitatea matricei dinamice, care este dimensiunea logică maximă posibilă.
În aplicațiile în care dimensiunea logică este mărginită, această structură de date este suficientă. Redimensionarea matricei subiacente este o operațiune costisitoare, care implică de obicei copierea întregului conținut al matricei.
Extindere geometrică și cost amortizat
Redimensionarea este foarte costisitoare, deoarece implică construirea unei alte matrice cu dimensiuni crescute și apoi copierea elementelor din matricea „veche” în „nouă”. Pentru a evita acest lucru de fiecare dată când adăugați un element nou, tablourile dinamice se redimensionează prin dublarea dimensiunii lor (în loc de o singură unitate). Aceasta folosește spațiul rezervat pentru extinderile viitoare. Operația de adăugare a unui element la final ar putea funcționa după cum urmează:
funcție insertEnd ( arraydin a, element e)
if (a.size = a.capacity)
// redimensionare pentru a dubla capacitatea sa curentă:
a. capacitate ← a. capacitate * 2
// (copiați conținutul noilor locații aici)
a [a.size] ← e
a. mărime ← a. mărime + 1
Pe măsură ce se inserează n elemente, capacitățile formează o progresie geometrică . Extinderea matricei cu orice proporție constantă asigură faptul că inserția de n elemente necesită un timp total de O ( n ) , ceea ce înseamnă că fiecare inserție necesită un timp constant amortizat . Valoarea acestei proporții a conduce la un compromis spațiu-timp: timpul mediu pentru operația de inserare este de aproximativ a / ( a -1), în timp ce numărul de celule pierdute este delimitat mai sus de ( a -1) n . Alegerea unei este independentă de aplicație, dar o utilizare obișnuită este a = 2.
Multe matrice dinamice, de asemenea, alocă o parte din memoria subiacentă dacă dimensiunea lor scade sub un anumit prag (de exemplu, 30% din capacitate).
Tablourile dinamice sunt un exemplu obișnuit atunci când predăm analiza amortizată .
Performanţă
| Listă concatenate | Matrice | Matrice dinamic | |
|---|---|---|---|
| Indexare | Θ ( n ) | Θ (1) | Θ (1) |
| Vizitează în ordine | Θ ( n ) | Θ ( n ) | Θ ( n ) |
| Introduceți / eliminați la sfârșit | Θ (1) | n / A | Θ (1) |
| Introducere / îndepărtare în mijloc | Θ (1) | n / A | Θ ( n ) |
| Spațiu pierdut (mediu) | Θ ( n ) | 0 | Θ ( n ) |
Matricea dinamică are o performanță similară matricei, cu adăugarea noilor operațiuni de adăugare și eliminare a elementelor de la final:
- Obțineți sau setați valoarea la un anumit indice (timp constant)
- Iterează elementele în ordine (timp liniar, performanță bună în cache)
- Introduceți sau eliminați un element din mijlocul matricei (timp liniar)
- Introduceți sau eliminați un element la sfârșitul matricei (timp amortizat constant)
Tablourile dinamice beneficiază de multe avantaje ale tablourilor, incluzând o locație bună de referință și utilizarea cache-ului de date , compactitate (utilizare redusă a memoriei) și acces aleatoriu . De obicei, acestea au doar puține cheltuieli suplimentare suplimentare pentru stocarea informațiilor despre dimensiune și capacitate. Acest lucru face ca matricele dinamice să fie un instrument atractiv pentru construirea de structuri de date prietenoase cu memoria cache .
Comparativ cu listele legate , matricile dinamice au indexare mai rapidă (timp constant versus timp liniar) și, de obicei, iterație mai rapidă datorită locației de referință mai bune; cu toate acestea, matricile dinamice necesită timp liniar pentru a insera sau șterge într-o locație arbitrară, deoarece toate elementele ulterioare trebuie mutate, în timp ce listele legate pot face acest lucru în timp constant. Acest dezavantaj este atenuat de spațiul tampon și de varianta vectorială gradată discutată în secțiunea Variante de mai jos. De asemenea, pentru o regiune de memorie foarte fragmentată , poate fi costisitor sau imposibil să găsești spațiu contiguu pentru o matrice dinamică mare, în timp ce listele legate nu necesită ca întreaga structură de date să fie stocată contiguu.
Variante
Spațiile tampon sunt similare cu matricele dinamice, dar permit inserarea și eliminarea eficientă grupate în apropierea aceleiași locații arbitrare. Unele implementări ale deque utilizează matricele deque , care permit un timp constant de inserare / îndepărtare amortizat la ambele capete, mai degrabă decât doar la sfârșit.
Goodrich [1] a prezentat un algoritm din matrice dinamică numit Tiered Vectors care permite performanța O (n 1/2 ) pentru a păstra inserția sau eliminarea din mijlocul matricei.
Hashed Array Tree (HAT) este un algoritm de matrice dinamic inventat de Sitarski în 1996. [2] Hashed Array Tree pierde o cantitate de spațiu de stocare de ordinul n 1/2 , unde n este numărul de elemente din matrice . Algoritmul are performanță amortizată la O (1) la adăugarea unei serii de obiecte la sfârșitul Arborelui Hashed Array.
Într-un raport din 1999 [3] , Brodnik și colab. descrieți o structură de date din matrice gradată dinamică, care pierde doar n 1/2 din spațiu pentru n elemente în orice moment al timpului și demonstrați o limită inferioară arătând că matricele dinamice trebuie să piardă acest spațiu suplimentar dacă operațiunile vor rămâne amortizate în timp. În plus, au o variantă în care mărirea și micșorarea tamponului nu sunt doar amortizate, ci, în cel mai rău caz, în timp constant.
Bagwell (2002) [4] a prezentat algoritmul VList , care poate fi adoptat pentru a implementa o matrice dinamică.
Suport lingvistic
Tipul de date std::vector în C ++ este o implementare a matricelor dinamice, la fel ca și clasele ArrayList furnizate cu Java API și infrastructura .NET . Clasa generică List<> furnizată cu versiunea 2.0 a infrastructurii .NET este de asemenea implementată cu tablouri dinamice. Delphi și D implementează matrice dinamice în nucleul (așa-numitul nucleu ) al limbajului. Multe limbaje de scriptare, cum ar fi Perl și PHP, oferă matrice dinamice ca tip de date primitiv încorporat. Pe de altă parte, Python, pe lângă capacitatea de a construi matrice dinamice, poate conține liste mixte de numere întregi, scripturi și flotări.
Notă
- ^ Vectori cu niveluri: matrice dinamice eficiente pentru secvențe bazate pe rang. [1]
- ^ HAT-uri: copaci matrici hași
- ^ Matrici redimensionabile în timp și spațiu optime
- ^ Liste funcționale rapide, Hash-Lists, Deques și matrice de lungime variabilă
Bibliografie
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein .Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Secțiunea 17.4: Tabelele dinamice, pp. 416-425.
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe Dynamic Array
linkuri externe
- NIST Dictionary of Algorithms and Data Structures: Dynamic array , la nist.gov .
- VPOOL - Implementarea limbajului C a matricei dinamice.
