Džudi niz

U računarstvu i softverskom inženjeringu, Džudi niz je struktura podataka koja ima visoke performanse, nisku potrošnju memorije i implementira asocijativni niz. Za razliku od normalnih nizova, Džudi nizovi mogu biti oskudni, odnosno, oni mogu da imaju velike opsege neraspoređenih indeksa. Mogu se koristiti za skladištenje i gledanje vrednosti preko celog broja ili stringa. Ključne prednosti korišćenja Džudi niza je njegova proširivost, visoke performanse, memorija, efikasnost i jednostavnost upotrebe.

Džudi nizovi su i brzinski i memorijski-efikasni, bez potrebe podešavanja i konfiguracije, te oni mogu zameniti uobičajene strukture podataka (povezane liste, binarne, trojne, B-stabla, hešing) i bolje rade sa veoma velikim skupovima podataka.

Da bi bila mala potrošnja memorije, Džudi nizovi koriste više od 20 različitih tehnika kompresije za komprimovanje čvorova.

Džudi Niz je izmislio Daglas Baskins (engl. Douglas Baskins) i nazvan je po njegovoj sestri.

Terminologija

Proširivanje, populacija i gustina stanovništva se najčešće koriste kada su u pitanju Džudi nizovi. Pošto se obično ne koristi u literaturi stabla pretrage, važno je da se definišu:

1. Prostor je opseg mogućih ključeva, npr 200, 300, itd
2. Populacija je broj ključeva sadržane u prostoru, na primer, stanovništvo od 5 mogu biti ključevi 200, 360, 400, 512 i 720
3. Gustina se koristi da se opiše oskudnost prostornih ključeva: Gustina = Populacija / Prostor

Prednosti

Alokacija memorije

Džudi nizovi su dizajnirani da budu bezgranični nizovi i samim tim njihova veličina nije unapred dodeljena. Oni mogu dinamički da biraju da povećavaju ili smanjuju memoriju prema populaciji niza i može da skalira na velikom broju elemenata. Pošto dinamički alocira memoriju kako raste, on je samo ograničen mašinskom memorijom. Memorija koju koriste Džudi nizovi je skoro proporcionalna broju elemenata u nizu.

Brzina

Džudi nizovi su dizajnirani da zadrži broj procesorskih punjenja keš linija što je moguće niže, a algoritam je složen u pokušaju da zadovolji ovaj cilj, što je češće moguće. Zbog ovih keš optimizacija, Džudi nizovi su brzi, ponekad čak i brži od heš tabela, posebno za veoma velike skupove podataka. Oni troše mnogo manje memorije nego heš tabele. Takođe, moguće je uraditi naručeni sekvencijalni prolaz ključeva, što nije moguće u heš tabelama.