Implicitne strukture podataka
U računarstvu, implicitne strukture podataka su strukture podataka koje koriste veoma malo memorije pored stvarnih elemenata podataka, odnosno veoma malo informacija osim glavnih podataka se čuvaju u ovim strukturama. To su šeme za skladištenje koje ne sadrže pokazivače i predstavlja datoteku od n k-torki koje su sačuvane kao jednostavna matrica dimenzije n sa k, iz koje se podaci čitaju brže. Kod implicitnih struktura podataka, jedina strukturna informacija koja se čuva je informacija koja omogućava da niz raste i da se n smanjuje. Ni jedna druga informacija nije obavezna. Ovakve strukture podataka se zovu "implicitne" jer je većina strukture elemenata implicitno izražena po njihovom redu. Još jedan termin koji se koristi kao sinonim je prostorna efikasnost. Definicije "veoma malog" nisu precizne i mogu značiti od O(1) do O(n) dodatnog prostora. Svemu se pristupa u-mestu, čitajući bitove na različitim pozicijama u podacima. Da bi se postiglo optimalno kodiranje, koristimo bitove umesto bajtova. Implicitne strukture podataka su često, takodje, i sažete strukture podataka (strukture podataka koje zauzimaju malo prostora za podatke).
Iako bi se većina složila da prostor na disku danas nije problem i da ne treba da se opterećujemo brinući o poboljšanju iskorišćenosti prostora, problem za koji su implicitne strukture podataka dizajnirane da poboljšaju je problem korišćenja glavne memorije. Hard diskovi, ili bilo koji drugi uredjaji za čuvanje velike količine podataka, kao i U/I uredjaji su mnogo sporiji od glavne memorije. Dakle, što veći procenat zadataka može da stane u bafere u glavnoj memoriji to je manja zavisnost na sporim U/I uredjajima. Dakle, ako veći komad implicitne strukture može da stane u glavnu memoriju, operacije izvršene u njoj mogu biti brže čak i ako asimptotsko vreme izvršavanja nije toliko dobro koliko njegova prostorna složenost. Osim toga, pošto je keš memorija centralno procesorske jedinice obično mnogo manja od glavne memorije, implicitne strukture podataka mogu poboljšati efikasnost keš memorije, njegovu brzinu rada, pogotovo ako se koristi metod poboljšavanja na prostornoj složenosti.
Implicitne data strukture za težinske elemente
Za prezentaciju elemenata različitih težina postoji nekoliko struktura podataka. Strukture koriste jos jednu lokaciju pored obaveznih za vrednosti elemenata. Prva struktura podržava najgori slučaj vremenske pretrage u smislu rangiranja težina elemenata. Ako elementi nisu sortirani, onda varijacija ove strukture koristi prosečno vreme.
Primeri
Primeri implicitnih struktura podataka uključuju i
- Binarni hip
- Dvoroditeljski hip
Spoljašnje veze
- Pogledati članke od J. Ian Munro, Greg Frederickson.