Matrice dinamică - Dynamic array

Image
Mai multe valori sunt inserate la sfârșitul unei matrice dinamice utilizând expansiunea geometrică. Celulele gri indică spațiul rezervat expansiunii. Cele mai multe inserții sunt rapide (timp constant), în timp ce unele sunt lente datorită necesității realocării (timpul Θ ( n ), etichetat cu broaște țestoase). Dimensiunea logică și capacitatea de matrice finale sunt afișate.

În informatică , o matrice dinamică , matrice growable , matrice redimensionabile , tabel dinamic , matrice mutabil , sau lista de matrice este un acces aleator , variabilă de listă de dimensiuni structură de date care permite elementelor să fie adăugate sau eliminate. Este livrat cu biblioteci standard în multe limbaje moderne de programare mainstream. Tablourile dinamice depășesc o limită de tablouri statice , care au o capacitate fixă ​​care trebuie specificată la alocare.

O matrice dinamică nu este același lucru cu o matrice alocată dinamic , care este o matrice a cărei dimensiune este fixă ​​atunci când matricea este alocată, deși o matrice dinamică poate folosi o matrice de dimensiuni fixe ca back-end.

Capacitate și tablouri dinamice de dimensiuni limitate

O matrice dinamică simplă poate fi construită prin alocarea unei matrice de dimensiuni fixe, de obicei mai mare decât numărul de elemente necesare imediat. Elementele matricei dinamice sunt stocate contiguu la începutul matricei subiacente, iar pozițiile rămase spre sfârșitul matricei subiacente sunt rezervate sau neutilizate. Elementele pot fi adăugate la sfârșitul unei matrice dinamice în timp constant folosind spațiul rezervat, până când acest spațiu este complet consumat. Când tot spațiul este consumat și trebuie adăugat un element suplimentar, atunci matricea subiacentă de mărime fixă ​​trebuie mărită în dimensiune. De obicei, redimensionarea este costisitoare, deoarece implică alocarea unui nou tablou subiacent și copierea fiecărui element din tabloul original. Elementele pot fi eliminate de la sfârșitul unei matrice dinamice în timp constant, deoarece nu este necesară redimensionarea. Numărul de elemente utilizate de conținutul matricei dinamice este dimensiunea sau dimensiunea sa logică , în timp ce dimensiunea matricei subiacente se numește capacitatea matricei dinamice sau dimensiunea fizică , care este dimensiunea maximă posibilă fără relocarea datelor.

O matrice de dimensiuni fixe va fi suficientă în aplicațiile în care dimensiunea logică maximă este fixă ​​(de exemplu, prin specificații) sau poate fi calculată înainte ca matricea să fie alocată. O matrice dinamică ar putea fi preferată dacă:

  • dimensiunea logică maximă este necunoscută sau dificil de calculat, înainte ca matricea să fie alocată
  • se consideră că o dimensiune logică maximă dată de o specificație este probabil să se schimbe
  • costul amortizat al redimensionării unei matrice dinamice nu afectează în mod semnificativ performanța sau capacitatea de reacție

Extindere geometrică și cost amortizat

Pentru a evita costurile redimensionării de mai multe ori, tablourile dinamice se redimensionează cu o cantitate mare, cum ar fi dublarea dimensiunii și utilizează spațiul rezervat pentru extinderea viitoare. Operația de adăugare a unui element la final ar putea funcționa după cum urmează: 

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1

Pe măsură ce se inserează n elemente, capacitățile formează o progresie geometrică . Extinderea matricei cu orice proporție constantă a asigură faptul că inserarea n elemente necesită O ( n ) timp global, ceea ce înseamnă că fiecare inserție necesită timp constant amortizat . Multe matrice dinamice distribuie, de asemenea, o parte din stocarea subiacentă dacă dimensiunea sa scade sub un anumit prag, cum ar fi 30% din capacitate. Acest prag trebuie să fie strict mai mic de 1 / a pentru a oferi histerezis (furnizați o bandă stabilă pentru a evita creșterea și micșorarea în mod repetat) și pentru a susține secvențe mixte de inserții și îndepărtări cu cost constant amortizat.

Tablourile dinamice sunt un exemplu obișnuit atunci când predăm analiza amortizată .

Factor de creștere

Factorul de creștere pentru matricea dinamică depinde de mai mulți factori, inclusiv un compromis spațiu-timp și algoritmi utilizați în alocatorul de memorie în sine. Pentru factorul de creștere a , timpul mediu pe operație de inserție este de aproximativ a / ( a −1), în timp ce numărul de celule irosite este delimitat mai sus de ( a −1) n . Dacă alocatorul de memorie folosește un algoritm de alocare pentru prima potrivire , atunci valorile factorului de creștere, cum ar fi a = 2, pot determina extinderea matricei dinamice fără memorie, chiar dacă o cantitate semnificativă de memorie poate fi încă disponibilă. Au existat diverse discuții cu privire la valorile ideale ale factorilor de creștere, inclusiv propuneri pentru raportul auriu , precum și valoarea 1,5. Cu toate acestea, multe manuale folosesc a  = 2 în scopuri de simplitate și analiză.

Mai jos sunt factorii de creștere utilizați de mai multe implementări populare:

Implementare Factorul de creștere ( a )
Java ArrayList 1,5 (3/2)
Python PyListObject ~ 1.125 (n + n >> 3)
Microsoft Visual C ++ 2013 1,5 (3/2)
G ++ 5.2.0 2
Clang 3.6 2
Nebunie Facebook / FBVector 1,5 (3/2)
Rugina Vec 2
Mergeți felii între 1,25 și 2

Performanţă

Compararea structurilor de date ale listelor
Arunca o privire Mutați (introduceți sau ștergeți) la ... Spațiu în exces, în
medie
Început Sfârșit Mijloc
Listă legată Θ ( n ) Θ (1) Θ (1), element final cunoscut;
Θ ( n ), element final necunoscut 		Timp de
vizionare + Θ (1) 		Θ ( n )
Matrice Θ (1) N / A N / A N / A 0
Matrice dinamică Θ (1) Θ ( n ) Θ (1) amortizat Θ ( n ) Θ ( n )
Copac echilibrat Θ (jurnal n) Θ (jurnal n) Θ (jurnal n ) Θ (jurnal n ) Θ ( n )
Listă cu acces aleatoriu Θ (jurnal n) Θ (1) N / A N / A Θ ( n )
Arborele matricial hașurat Θ (1) Θ ( n ) Θ (1) amortizat Θ ( n ) Θ (√ n )

Tabloul dinamic are o performanță similară cu un tablou, cu adăugarea de noi operații de adăugare și eliminare a elementelor:

  • Obținerea sau setarea valorii la un anumit indice (timp constant)
  • Iterarea elementelor în ordine (timp liniar, performanță bună în cache)
  • Introducerea sau ștergerea unui element în mijlocul matricei (timp liniar)
  • Introducerea sau ștergerea unui element la sfârșitul matricei (timp constant amortizat)

Tablourile dinamice beneficiază de multe dintre avantajele tablourilor, inclusiv o bună localitate de referință și utilizarea cache-ului de date , compactitate (utilizare redusă a memoriei) și acces aleatoriu . De obicei, acestea au doar o mică cheltuială suplimentară fixă ​​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 . Cu toate acestea, în limbi cum ar fi Python sau Java care aplică semantica de referință, matricea dinamică, în general, nu va stoca datele reale, ci mai degrabă va stoca referințe la datele care se află în alte zone ale memoriei. În acest caz, accesarea secvențială a elementelor din matrice va implica de fapt accesarea mai multor zone de memorie necontigue, astfel încât numeroasele avantaje ale facilității cache a acestei structuri de date se pierd.

Comparativ cu listele legate , matricile dinamice au indexare mai rapidă (timp constant versus timp liniar) și iterație de obicei mai rapidă datorită localității îmbunătățite de referință; cu toate acestea, matricile dinamice necesită timp liniar pentru a insera sau șterge într-o locație arbitrară, deoarece toate elementele următoare trebuie mutate, în timp ce listele legate pot face acest lucru în timp constant. Acest dezavantaj este atenuat de buffer-ul de spațiu și de variantele vectoriale cu niveluri discutate în variantele de mai jos. De asemenea, într-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.

Un arbore echilibrat poate stoca o listă, oferind în același timp toate operațiunile atât ale matricelor dinamice, cât și ale listelor legate, dar atât inserarea la sfârșit, cât și iterația din listă sunt mai lente decât pentru o matrice dinamică, în teorie și în practică, din cauza depozitarea contiguă și traversarea arborelui / manipularea aeriană.

Variante

Bufferele Gap sunt similare cu matricele dinamice, dar permit operațiuni de inserare și ștergere eficiente grupate în apropierea aceleiași locații arbitrare. Unele implementări de deque utilizează deque de matrice , care permit inserarea / îndepărtarea în timp constant amortizat la ambele capete, în loc de un singur capăt.

Goodrich a prezentat un algoritm din matrice dinamică numit vectori cu niveluri care oferă performanță O ( n 1 / k ) pentru inserții și ștergeri de oriunde din matrice și O ( k ) get și set, unde k ≥ 2 este un parametru constant.

Hashed array tree (HAT) este un algoritm de matrice dinamică publicat de Sitarski în 1996. Arborele matricial hașat deșeuri comandă n 1/2 cantitate de spațiu de stocare, unde n este numărul de elemente din matrice. Algoritmul are o performanță amortizată O (1) atunci când se adaugă o serie de obiecte la capătul unui arbore matricial hash.

Într-o lucrare din 1999, Brodnik și colab. descrie o structură de date a matricei dinamice pe nivele, care irosește doar n 1/2 spațiu pentru n elemente în orice moment al timpului și demonstrează o limită inferioară care arată că orice matrice dinamică trebuie să irosească atât de mult spațiu dacă operațiunile vor rămâne timp constant amortizat . În plus, acestea prezintă o variantă în care creșterea și micșorarea tamponului nu numai că are timp amortizat, dar în cel mai rău caz.

Bagwell (2002) a prezentat algoritmul VList, care poate fi adaptat pentru a implementa o matrice dinamică.

Suport lingvistic

C ++ e std::vectorsi Rust e std::vec::Vecsunt implementări de matrice dinamice, așa cum sunt ArrayListclasele livrate cu Java API și .NET Framework .

List<>Clasa generică furnizată cu versiunea 2.0 a .NET Framework este de asemenea implementată cu matrice dinamice. Smalltalk „s OrderedCollectioneste un tablou dinamic cu pornire dinamic și de final index, ceea ce face îndepărtarea primului element și O (1).

Python „s listimplementare datatype este o matrice dinamică.

Delphi și D implementează matrice dinamice la baza limbajului.

Ada e Ada.Containers.Vectorspachet generic prevede punerea în aplicare matrice dinamică pentru un anumit subtip.

Multe limbaje de scriptare, cum ar fi Perl și Ruby, oferă matrice dinamice ca tip de date primitiv încorporat .

Mai multe cadre multi-platformă oferă implementări de matrice dinamice pentru C , inclusiv CFArrayși CFMutableArrayîn Core Foundation , și GArrayși GPtrArrayîn GLib .

Common Lisp oferă un suport rudimentar pentru vectorii redimensionabili, permițând configurarea arraytipului încorporat ca reglabil și locația inserării de către indicatorul de umplere .

Referințe

  1. ^ a b A se vedea, de exemplu, codul sursă al clasei java.util.ArrayList din OpenJDK 6 .
  2. ^ Lambert, Kenneth Alfred (2009), „Dimensiunea fizică și dimensiunea logică” , Fundamentals of Python: From First Programs Through Data Structures , Cengage Learning, p. 510, ISBN 978-1423902188
  3. ^ a b Goodrich, Michael T .; Tamassia, Roberto (2002), „1.5.2 Analiza unei implementări extinse de matrice”, Algorithm Design: Foundations, Analysis and Internet Example , Wiley, pp. 39-41.
  4. ^ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "17.4 Tabelele dinamice". Introducere în algoritmi (ediția a II-a). MIT Press și McGraw-Hill. pp. 416-424. ISBN 0-262-03293-7.
  5. ^ a b c "Vectorul C ++ STL: definiție, factor de creștere, funcții membre" . Arhivat din original la 06.08.2015 . Adus 05-08-2015 .
  6. ^ "factorul de creștere a vectorului de 1,5" . comp.lang.c ++. moderat . Grupuri Google.
  7. ^ Listează implementarea obiectelor de la github.com/python/cpython/, recuperat 23-03-2020.
  8. ^ Brais, Hadi. "Disecarea vectorului C ++ STL: Partea 3 - Capacitate și dimensiune" . Micromisterii . Adus 05-08-2015 .
  9. ^ "facebook / prostie" . GitHub . Adus 05-08-2015 .
  10. ^ "rug-lang / rugină" . GitHub . Adus 09-06-2020 .
  11. ^ "golang / go" . GitHub . Adus 2021-09-14 .
  12. ^ Ziua 1 Keynote - Bjarne Stroustrup: C ++ 11 Style la GoingNative 2012 pe channel9.msdn.com de la minutul 45 sau folia 44
  13. ^ Strângerea numărului: de ce nu ar trebui să folosiți NICIODATĂ link-list în codul dvs. din nou la kjellkod.wordpress.com
  14. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Raport tehnic CS-99-09) (PDF) , Departamentul de Informatică, Universitatea din Waterloo
  15. ^ a b c Chris Okasaki (1995). „Liste cu acces aleatoriu pur funcționale”. Lucrările celei de-a șaptea conferințe internaționale privind limbajele de programare funcționale și arhitectura computerelor : 86-95. doi : 10.1145 / 224164.224187 .
  16. ^ Goodrich, Michael T .; Kloss II, John G. (1999), „Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences” , Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 1663 : 205–216 , doi : 10.1007 / 3-540 -48447-7_21 , ISBN 978-3-540-66279-2
  17. ^ Sitarski, Edward (septembrie 1996), „HATs: Hashed array trees” , Algorithm Alley, Dr. Dobb's Journal , 21 (11)
  18. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Raport tehnic CS-99-09), Departamentul de Informatică, Universitatea din Waterloo
  19. ^ Bagwell, Phil (2002), Liste funcționale rapide, Hash-Lists, Deques și matrice de lungime variabilă , EPFL
  20. ^ Javadoc onArrayList
  21. ^ Clasa ArrayList

linkuri externe