Proređeni niz
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
U računarstvu, proređeni niz je niz u kome veći broj elemenata ima istu vrednost (podrazumevana vrednost je uglavnom 0 ili null). Pojava nula elemenata u velikom nizu je veoma neefikasna kako za računanje tako i za smeštanje istih. Niz u kome je veliki broj nula elemenata pretenduje da bude proređen.
U slučaju proređenih nizova, može se zatražiti vrednost sa "praznog" mesta u nizu. U tom slučaju, za niz brojeva vraća se vrednost 0, a za niz nekih drugih podataka vraća se vrednost NULL.
Prosta implementacija niza može alocirati prostor za ceo niz, ali u slučaju kada je nekoliko nepodrazumevajućih vrednosti, takva implementacija nije efikasna. Obično je algoritam koji se koristi umesto običnog niza okarakterisan drugim poznatim osobinama niza. Na primer, ako je proređenost unapred poznata ili su elementi složeni prema nekoj funkciji.
Hip, memorijski alokator, u programu može da izabere da sačuva delove praznog prostora u povezanoj listi pre nego što bi sačuvao sve alocirane delove u takozvani bitovski niz.
Prikaz уреди
Proređen niz može biti prikazan kao:
Sparse_Array[{pos1 -> val1, pos2 -> val2,...}] ili
Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]
gde su vrednosti proređenog niza smeštene na odgovarajućim pozicijama .
Proređeni niz kao povezana lista уреди
Očigledno je pitanje zašto nam je potrebna povezana lista za predstavljanje proređenog niza, ako ga možemo jednostavno predstaviti koristeći običan niz. Odgovor na ovo pitanje leži u činjenici da prilikom prikazivanja proređenog niza kao običnog niza, velika količina memorije je alocirana za 0 ili NULL elemente. Na primer, uzmimo u obzir sledću deklaraciju:
- double arr[1000][1000];
Kada deklarišemo ovaj niz, alocirali smo neophodan prostor za 1000000 vrednosti tipa double. Kako svaki double zahteva 8 bajtova u memoriji, ovaj ceo niz zateva 8 miliona bajtova u istoj. Zato što je ovo proređeni niz, mnogi njegovi elementi imaju vrednost 0 (ili NULL). Otuda će deklarisanje ovog niza upiti sav prostor što će rezultovati rasipanje memorije (u poređenju sa nizom čija je memorija alocirana samo za ne-nula elemente). Efikasan način da se prevaziđe ovaj problem je da se niz predstavi kao povezana lista koja zahteva manje memorije, jer su smešteni samo ne-nula elementi. Takođe, kada se koristi povezana lista, pristup elementima niza se vrši kroz manji broj iteracija nego u običnom nizu.
Proređeni niz kao povezana lista sadrži čvorove međusobno povezane. U jednodimenzionalnom nizu, svaki čvor se sastoji od "indeksa" (pozicije) ne-nula elementa i "vrednosti" na toj poziciji, i pokazivača na "sledeći" čvor(zbog povezivanja sa sledećim čvorom), a čvorovi su povezani u istom redu kao i indeksi. U slučaju dvodimenzijonalnih proređenih nizova, svaki čvor se sastoji od indeksa za vrstu, indeksa za kolonu, vrednosti na toj poziciji i pokazivača na sledeći element.