Dinamički niz

Dinamički niz je struktura podataka promenljive dužine sa direktnim pristupom, nad kojom su definisane operacije dodavanja i izbacivanja elemenata. Dolazi u standardnim bibliotekama mnogih modernih, često korišćenih programskih jezika.

Nekoliko vrednosti je ubačeno na kraj dinamičkog niza korišćenjem geometrijske progresije. Siva polja označavaju prostor rezervisan za proširenje. Većina dodavanja je brza (konstantno vreme), dok su neka spora zbog potrebe za realokacijom (Θ(n) vreme, označeno kornjačama). Prikazani su dužina i kapacitet konačnog niza.

Dinamički niz nije isto što i dinamički alociran niz, koji je zapravo niz fiksne dužine čija se dužina određuje pri alokaciji. Ipak, i dinamički niz može koristiti niz fiksne dužine kao back end.

Dinamički nizovi ograničene dužine i kapacitet

Najjednostavniji dinamički niz može se napraviti alociranjem niza fiksne dužine, koji ćemo zatim podeliti na dva dela: prvi čuva elemente dinamičkog niza, a drugi je rezervisan, tj. neiskorišćen. Tada je moguće dodavati ili uklanjati elemente sa kraja dinamičkog niza u konstantnom vremenu, koristeći rezervisan prostor, sve dok se taj prostor ne popuni. Broj elemenata koji je upotrebljen za članove niza je njegova dužina, dok se veličina rezervisanog prostora naziva kapacitet dinamičkog niza. Kapacitet niza je njegova maksimalna dužina bez realokacije podataka.

U aplikacijama gde je dužina niza ograničena, moguće je koristiti strukture podataka fiksne dužine. Međutim, ovo se može ispostaviti kao kratkoročno rešenje ukoliko kasnije bude bilo potrebno više prostora. Često je bolje rešenje omogućiti da svakom nizu može da se menja veličina, a onda se prilikom optimizacije vratiti na korišćenje nizova fiksirane dužine. Promena kapaciteta je skup proces, koji obično obuhvata kopiranje celokupnog sadržaja niza.

Geometrijsko povećanje kapaciteta i amortizovana cena

Pošto je promena kapaciteta skup proces, cena se može značajno smanjiti većim proširivanjima (na primer, udvostručujući kapacitet) i korišćenjem rezervisanog prostora za buduća dodavanja članova niza. Operacija dodavanja elementa na kraj niza može izgledati ovako:

  function insertEnd(dynarray a, element e)
    if (a.size = a.capacity)
        a.capacity ← a.capacity * 2 // udvostručuje kapacitet 
        ... kopiranje podataka na novu memorijsku lokaciju...
    a[a.size] ← e
    a.size ← a.size + 1

Pošto je uneto n elemenata, kapaciteti formiraju geometrijsku progresiju. Proširivanje kapaciteta nekim konstantnim faktorom obezbeđuje da je za unos n elemenata potrebno ukupno vreme O(n),što znači da je za svaki pojedinačan unos potrebno amortizovano konstantno vreme. Vrednost ovog faktora proporcionalnosti utiče na odnos vreme-prostor: prosečno vreme po operaciji ubacivanja elementa je oko а/(а-1) dok je broj utrošenih ćelija ograničen odozgo sa (a-1)n. Izbor vrednosti a zavisi od biblioteke ili aplikacije: u nekim udžbenicima a=2 dok Javina ArrayList implementacija koristi a=3/2.

Mnogi dinamički nizovi takođe dealociraju deo raspoloživog prostora ako veličina padne ispod nekog praga, npr. 30% kapaciteta. Potrebno je da taj prag obavezno bude manji od 1/а da bi podržao naizmenične sekvence dodavanja i brisanja sa amortizovanom konstantnom cenom. Dinamički nizovi su uobičajen primer u objašnjavanju amortizovane analize.

Odlike

	Povezana lista	Niz	Dinamički niz	Balansirano stablo	Lista s direktim pristupom
Indeksiranje	Θ(n)	Θ(1)	Θ(1)	Θ(log n)	Θ(log n)
Ubaci/Izbriši s početka	Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(1)
Ubaci/Izbriši s kraja	Θ(n) poslednji element nije poznat Θ(1) poslednji element je poznat	N/A	Θ(1) amortizovano	Θ(log n)	Θ(log n) osvežavanje
Ubaci/Izbriši iz sredine	vreme pretrage + Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(log n) osvežavanje
Potrošen prostor (prosek)	Θ(n)	0	Θ(n)	Θ(n)	Θ(n)

Osobine dinamičkih nizova su slične osobinama nizova, uz dopunske operacije dodavanja i uklanjanja elemenata na kraju niza:

• Dobijanje ili postavljanje vrednosti sa određenim indeksom (konstantno vreme)
• Iteracije nad elementima u redosledu (linearno vreme, dobro ponašanje keša)
• Insertovanje ili brisanje elementa u sredini niza (linearno vreme)
• Insertovanje ili brisanje elementa na kraju niza (konstantno amortizovano vreme)

Dinamički nizovi dele mnoge prednosti nizova, uključujući lokalnost referenci i efikasno korišćenje keša, kompaktnost (malo korišćenje memorije) i mogućnost nasumičnog (direktnog) pristupa. Obično im je potreban samo mali dodatni prostor u kome se čuvaju podaci o veličini i kapacitetu. Zbog toga su dinamički nizovi atraktivno rešenje za kreiranje struktura podataka sa optimalnom upotrebom keša. U jezicima kao što su Phyton ili Java, koji koriste semantiku referenci, dinamički nizovi uglavnom neće čuvati stvarne podatke, već reference ka podacima koji su smešteni u drugim delovima memorije. U ovom slučaju, sekvencijalni pristup podacima će u stvarnosti predstavljati pristupanje većem broju nepovezanih delova memorije, pa će biti izgubljene mnoge prednosti koje ova struktura podataka ima u upotrebi keša.

U poređenju sa povezanim listama, dinamički nizovi imaju brže indeksiranje (konstantno vreme prema linearnom vremenu) i uglavnom brže iteracije zahvaljujući boljoj lokalnosti referenci. S druge strane, dinamičkim nizovima potrebno je linearno vreme da ubace ili izbrišu podatak sa proizvoljne lokacije, pošto svi naredni elementi moraju biti premešteni, dok povezane liste ovu operaciju obavljaju u konstantnom vremenu. U slučaju visoko fragmentisanog memorijskog prostora, može biti skupo ili nemoguće obezbediti povezan blok za veliki dinamički niz, dok povezane liste ne zahtevaju da cela struktura podataka bude smeštena neprekinuto.

Balansirano stablo može uskladištiti listu, istovremeno obezbeđujući, uz prihvatljivu efikasnost, sve operacije kako dinamičkih nizova tako i povezanih lista, ali i dodavanje na kraj i iteracije sa podacima su sporije nego kod dinamičkih nizova, zbog smeštaja podataka u odvojenim blokovima kao i zbog operacija balansiranja stabla.

Literatura

• Lambert, Kenneth Alfred (2009). Physical size and logical size. Fundamentals of Python: From First Programs Through Data Structures. Cengage Learning. str. 510—. ISBN 978-1-4239-0218-8.