Strukture podataka i algoritmi
6 Redovi

Redovi su dinamicki skupovi koji imaju neki koncept poretka. Ovaj koncept moze da se bazira na poretku ulaska u red - dajuci Prvi-Unutra-Prvi-Van (First-In-First-Out = FIFO) ili Poslednji-Unutra-Prvi-Van (Last-In-First-Out = LIFO) redove. Oba tipa mogu da se izvedu pomocu povezanih listi: najjednostavnija "dodavanje-na-glavu" implementacija povezane liste daje LIFO ponasanje. Mala izmena - dodavanje pointera na rep liste uz izmenu implementacije tako da se novi objekat dodaje na rep liste - rezultira FIFO ponasanjem.

Performanse

Direktna analiza pokazuje da je u oba ova slucaja, vreme potrebno za dodavanje ili brisanje objekta konstantno i nezavisno od broja objekata u redu. Stoga su i dodavanje i brisanje O(1) operacije. Za svaku konkretnu kombinaciju racunar + operativni sistem + programski jezik, dodavanje moze da traje c1 sekundi, a brisanje c2 sekundi, ali mi nismo zainteresovani za vrednost konstante, jer ce ona varirati od racunara do racunara, jezika do jezika, itd. Ono sto je bitno je da vreme ne zavisi od n - dajuci O(1) algoritme.

Jednom kada imamo O(1) metod, tesko da se bilo sta dalje moze uciniti sa algoritamske tacke gledista. Ponekad, bolji pristup problemu ce rezultirati manjim konstantnim vremenom. Cesto, poboljsanja kompajlera, operativnog sistema, racunara itd. rezultiraju znacajnim unapredjenjima. Medjutim, O(1) metod su vec dovoljno brzi, tako da je malo verovatno da ce se trud ulozen u poboljsanje takvog metoda zaista isplatiti!

6.1 Prioritetni redovi

Objekti koji se dodaju u red cesto poseduju neki prioritet: on odredjuje poredak u kome objekti izlaze iz reda - objekti sa najvisim prioritetom se prvi uklanjaju.

Ovakva situacija se cesto pojavljuje u kontrolnim sistemima procesa. Zamislimo konzolu kontrolora u velikoj automatizovanoj fabrici. Ona prima mnoge rutinske poruke iz svih delova sistema: njima se dodeljuje nizak prioritet zato sto one samo javljaju o normalnom funkcionisanju sistema - one jednostavno azuriraju razlicite delove monitora na konzoli tako da postoji potvrda da ne postoje problemi. Nema neke bitne razlike ako takve poruke kasne ili se izgube.

Povremeno se, medjutim, nesto polomi ili pokvari i posalju se poruke za uzbunu. One imaju visoki prioritet jer zahtevaju odredjenu akciju kako bi se resio problem (cak i ako je masovna evakuacija jer nista ne moze da spreci neizbeznu eksploziju!).

Tipicno ce takvi sistemi biti sastavljeni od mnogih malih delova, od kojih ce jedan biti buffer za poruke koje prima konzola kontrolora. Komunikacioni sistem stavlja poruke u buffer, tako da se komunikacione veze mogu osloboditi za nove poruke dok program konzole obradjuje poruke. Program konzole vadi poruke iz buffera i azurira odgovarajuce delove monitora konzole. Ocigledno je da zelimo da sortiramo poruke po njihovom prioritetu tako da budemo sigurni da ce se poruke za uzbunu obraditi trenutno i da nece kasniti iza par hiljada rutinskih poruka, dok se fabrika sprema da eksplodira!

Kao sto smo videli, mogli bismo da koristimo strukturu stabla - koja u opstem slucaju daje O(logn) performanse i za dodavanje i za brisanje poruka. Na zalost, ako stablo postane nebalansirano, performanse se degradiraju do O(n) u patoloskim slucajevima. Ovo po svemu sudeci nije prihvatljivo kada radimo sa opasnim industrijskim procesima, nuklearnim reaktorima, sistemima kontrole leta i drugim sistema od zivotne vaznosti.

Sa strane

Najveci deo racunarskih sistema spada u siroku kategoriju informacionih sistema - koji jednostavno skladiste i obradjuju informacije u korist ljudi koji donose odluke u skladu sa tim informacijama. U takvim sistemima, ocigledno, nije bitno da li treba 1 ili 100 sekundi da se nadje podatak - to jednostavno odredjuje da li cete na kafu otici odmah ili kasnije. Medjutim, kao sto cemo videti, koriscenje najboljih poznatih algoritama je obicno lako i direktno: ako se vec ne nalaze u bibliotekama rutina, onda se nalaze u udzbenicima. Cak ne morate ni da se mucite da ih programirate! U takvim slucajevima, patice samo vasa reputacija ako neko (ko je dobro prostudirao njegovu knjigu algoritama!) dodje i kaze
"Zaboga, zasto je X (vi!) koristio ovaj O(n2) metod -
kad postoji dobro poznati O(n)!"
Jedino ce proizvodjaci hardvera biti veoma srecni ako koristite neefikasne algoritme - to samo pospesuje zahteve za novim i brzim hardverom - i osigurava njihovu veliku zaradu!

Postoji struktura koja garantuje O(logn) performanse i za dodavanje i za brisanje: ona se zove gomila (heap).

Kljucni pojmovi

FIFO red
Red u kome prvi dodati objekat uvek prvi izlazi napolje.
LIFO red
Red u kome poslednji dodati objekat uvek prvi izlazi napolje.
Prioritetni red
Red u kome su objekti sortirani tako da objekat sa najvecim prioritetom uvek prvi izlazi napolje.
Sistemi od zivotne vaznosti
Sistemi od kojih zavisimo u pogledu sigurnosti i koji mogu dovesti do smrti ili povrede ukoliko zakazu: medicinski sistemi, sistemi za osmatranje industrijskih postrojenja i sistemi kontrole leta su primeri sistema od zivotne vaznosti.
Sistemi u realnom vremenu
Sistemi u kojima je vreme ogranicenje. Sistem koji mora da odgovori na neki dogadjaj (npr. na promenu visine aviona prouzrokovanu nekim atmosferskim dogadjajem kao sto je skoro uspravni vetar) u ogranicenom vremenu kako bi odrzao stabilnost ili nastavio ispravno izvrsenje operacija (npr. avionski sistemi moraju da na odgovarajuci nacin usaglase kontrolne povrsine aviona pre sletanja!).
Dalje na Gomile
Nazad na Sadrzaj
© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.