Red sa dva kraja

Из Википедије, слободне енциклопедије

U informatici, red sa dva kraja (engl. Double-ended-queue, uglavnom se piše deque, izgovara se dek) je apstraktan tip podataka koji je uopštenje reda, u koji se elementi mogu dodavati ili uklanjati sa početka(glave) ili kraja(repa).[1]

Imenovanje[уреди]

Deque se ponekad piše i kao dequeue, ali se taj termin uglavnom ne koristi pošto je dequeue takođe glagol koji znači "ukloniti iz reda". Uprkos tome, nekoliko biblioteka i neki autori, kao Aho, Hopkroft, i Ulman u svom udžbeniku Strukture podataka i algoritmi(Data structures and algorithms), koriste termin dequeue. Džon Mičel, autor dela Koncepti u programskim jezicima(Concepts in Programming Languages), takođe koristi ovaj termin.

Razlike i podtipovi[уреди]

Razlikuje se od reda koji radi na principu FIFO, u koji se elementi samo mogu dodati na jedan kraj a vaditi sa drugog kraja. Deque može da ima neke od sledećih podtipova:

  • Deque sa ograničenjem na ulaz: brisanje elemenata se može vršiti na oba kraja dok se ubacivanje može vršiti samo na jednom kraju.
  • Deque sa ograničenjem na izlaz: ubacivanje elemenata se može vršiti na oba kraja dok se brisanje može vršiti samo na jredom kraju.

Osnovni kao i najuobičajeniji tipovi lista u računarstvu, redovi i stekovi se mogu smatrati posebnim oblikom redova sa dva kraja, i mogu se implementirati korišćenjem istih.

Operacije[уреди]

Osnovne operacije koje se mogu vršiti su ubacivanje i vađenje sa bilo kog kraja. Uglavnom se i implementira operacija koja će da vrati vrednost sa bilo kog od krajeva deque-a bez da ga obriše.

Imena se razlikuju među jezicima; neki od značajnijih jezika:

operacija uobičajena imena Ada C++ Java Perl PHP Python Ruby JavaScript
ubaciti element na kraj inject, snoc Append push_back offerLast push array_push append push push
ubaciti element na početak push, cons Prepend push_front offerFirst unshift array_unshift appendleft unshift unshift
izbrisati poslednji element eject Delete_Last pop_back pollLast pop array_pop pop pop pop
izbrisati prvi element pop Delete_First pop_front pollFirst shift array_shift popleft shift shift
pogledati poslednji element Last_Element back peekLast $array[-1] end <obj>[-1] last <obj>[<obj>.length - 1]
pogledati prvi element First_Element front peekFirst $array[0] reset <obj>[0] first <obj>[0]

Implementacije[уреди]

Postoje najmanje dva uobičajena načina za efikasno implementiranje deque-a: korišćenjem modifikovanog dinamičkog niza ili dvostruko povezane liste.

Pristup korišćenjem dinamičkog niza koristi varijantu dinamičkog niza koji može da se proširuje sa oba kraja. Takvi nizovi imaju sva svojstva dinamičkih nizova, kao što su konstantno vreme nasumičnom pristupu podacima, dobra lokalnost referenci, neefikasno ubacivanje/izbacivanje elemenata u sredini, kao i amortizovano konstantno vreme za ubacivanje/brisanje na oba kraja, umesto samo na jednom kraju. Tri uobičajene implementacije:

  • Skladištenje deque-a u kružnom baferu koji se proširuje tek kada se napuni do kraja. Ovime se postiže manja učestalost proširivanja.
  • Alociranje sadržaja deque-a počevši od centra niza koji se koristi za realizaciju i proširivanje istog tek kad se dostigne bilo koji od krajeva. Ovakav pristup može zahtevati učestalija proširivanja i trošiti više prostora, posebno kada se elementi dodaju samo sa jednog kraja.
  • Skladištenje sadržaja u više manjih nizova, pritom alocirajući dodatne nizove s početka ili kraja po potrebi. Indeksiranje se implementira tako što se koristi dinaminčki niz koji čuva pokazivače na svaki od manjih nizova.

Podrška od strane programskih jezika[уреди]

Ada-ini kontejneri obezbeđuju generičke pakete: Ada.Containers.Vectors koji sadrži implementaciju dinamičkih nizova, odnosno Ada.Containers.Doubly_Linked_Lists koji sadrži implementaciju dvostruko povezanih listi.

C++-ova biblioteka standardnih šablona ovezbeđuje šablone klasa std::deque i std::list koje sadrže implementacije deque-a, odnosno lista.

Od verzije 6, Java-in Collections Framework obezbeđuje novi Deque interfejs koji obezbeđuje funkcionalnost umetanja i brisanja sa oba kraja. Klase kao sto su ArrayDeque (koja je takođe novina u Java 6) i LinkedList implementiraju ovaj intefejs i obezbeđuju implementacije dinamičkog niza, odnosno povezanih listi. Međutim, the ArrayDeque, nasuprot svom imenu, ne podržava nasumičan pristup elementima.

Python 2.4 je uveo collections modul sa podrškom za deque objekte. Od verzije 5.3, proširenje PHP-ove SPL sadrži 'SplDoublyLinkedList' klasu koja se može koristiti za implementaciju deque-a. Prethodno su se morale koristiti nizovne funkcije array_shift/unshift/pop/push da bi se napravio deque.

GHC-ov Data.Sequence modul implementira efikasan, funkcionalan red sa dva karaja u Haskelu. Implementacija koristi 2-3 stablo sa pribeleženim veličinama. Postoje i druge mogućnosti za implementaciju čisto funkcionalnih redova sa dva kraja (većinom koristeći lenjo izračunavanje).[2][3]

Složenost[уреди]

  • U implementaciji koja koristi dvostruko povezanu listu izuzimajući vreme potrebno za alokaciju/dealokaciju vremenska složenost svih operacija je O(1). Uzgred, vremenska složenost ubacivanja i brisanja elemenata u sredini je takođe O(1) ako se koristi iterator. Doduše, vremenska složenost za pristup elementu koristeći indeks je O(n).
  • Koristeći proširiv niz, amortizovana vremenska složenost svih operacija je O(1). Takođe je i vremenska složenost nasumičnog pristupa elementu O(1), dok je vremenska složenost umetanja i brisanja elemenata iz sredine O(n).

Primene[уреди]

Primer gde deque može biti upotrebljen je A-Steal algoritam za raspoređivanje poslova.[4] Ovaj algoritam implementira raspoređivanje poslova za nekoliko procesora. Čuva se zaseban deque za svaki od procesora koji sadrži niti koje svaki procesor treba da izvrši. Da bi izvršio sledeću nit, procesor uzima element iz deque-a (koristeći operaciju "izbriši prvi element"). Ako trenutna nit napravi kopiju sebe(fork-uje), stavlja se na početak deque-a (koristeći operaciju "ubaciti na početak reda") i pokreće se nova nit. Kada jedan od procesora završi izvršenje svojih niti (tj. red je prazan), može da "ukrade" nit drugog procesora tako što uzima poslednji element iz deque-a drugog procesora (koristeći operaciju "izbriši poslednji element") i izvršava tu nit. Ovaj algoritam koristi Intel-ova Threading Building Blocks (TBB) biblioteka za paralelno programiranje.

Vidi još[уреди]

Reference[уреди]

  1. ^ Donald Knut. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. 1997. ISBN 978-0-201-89683-1. pp. Section 2.2.1: Stacks, Queues, and Deques, pp. 238-243.
  2. ^ http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf C. Okasaki, "Purely Functional Data Structures", September 1996
  3. ^ Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)
  4. ^ Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 978-3-540-71034-9.  See pp. 22.

Литература[уреди]

  • Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 978-3-540-71034-9.  See pp. 22.

Spoljašnje veze[уреди]