XOR povezana lista

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

XOR povezana lista je struktura podataka koja se koristi u programiranju. Ona koristi prednost nad bitovskom XOR operacijom da smanji zahteve za skladištenje za dvostruko povezane liste.

Opis[уреди]

Obična dvostruko povezana lista čuva adrese prethodnih i narednih stavki liste u svakom čvoru liste, zahtevajući dva polja adrese.

...  A       B         C         D         E  ...
         –>  next –>  next  –>  next  –>
         <–  prev <–  prev  <–  prev  <–

XOR povezana lista kompresuje iste informacije u jednom adresnom polju čuvajući bitovske XOR (ovde oznacen ⊕) adrese za prethodnu i sledeću adresu u jednom polju:

...  A        B         C         D         E  ...
        <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

Formalnije:

link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

Kada prelazimo listu sa leva na desno: pretpostavimo da se nalazimo na C, možemo uzeti adresu prethodne stavke,B, i izvršimo XOR sa vrednošću link polja(B⊕D). Tada ćemo imati adresu za D i možemo nastaviti da prelazimo listu. Isti obrazac važi i u drugom smeru.

   tj.   addr(D) = link(C) ⊕ addr(B)
   gde
         link(C) = addr(B)⊕addr(D)
   onda  
         addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
     
         addr(D) = addr(B)⊕addr(B) ⊕ addr(D) 
   otada 
          X⊕X = 0                 
          => addr(D) = 0 ⊕ addr(D)
   otada
          X⊕0 = x
          => addr(D) = addr(D)

Da bismo pokrenuli prelazak kroz listu u bilo kom smeru iz neke tačke, moramo imati adresu dve uzastopne stavke ,ne samo jedne. Ako su adrese dve uzastopne stavke obrnute, treba završiti prelazak liste u suprotnom smeru.

Teorija operacije[уреди]

Ključ je prva operacija, i svojstva XOR-a:

  • X⊕X=0
  • X⊕0=X
  • X⊕Y=Y⊕X
  • (X⊕Y)⊕Z=X⊕(Y⊕Z)

R2 registar uvek sadrži XOR adrese trenutne stavke C sa adresom prethodnika P : C⊕P. Link polja u evidenciji sadrži XOR levog i desnog sledbenika adresa , L⊕R. XOR R2(C⊕P) sa trenutnim poljem (L⊕R) daje C⊕P⊕L⊕R.

  • Ako je prethodnik bio L, onda se P(=L) i L poništavaju ostavljajući C⊕R.
  • Ako je prethodnik bio R, onda se P(=R) i R poništavaju, ostavljajući C⊕L.

U svakom slučaju, rezultat je XOR trenutne adrese sa sledećom adresom. XOR sa trenutnom adresom u R1 ostavlja sledeću adresu. R2 je ostavljen sa neophodnim XOR parom (sada) trenutne adrese i prethodnika.

Karakteristike[уреди]

Dve XOR operacije dovoljne su da bi se izvršio prelaz od jedne stavke na drugu, iste instrukcije su dovoljne u oba slučaja. Razmotrimo listu stavki {...B C D...} i R1 i R2 kao registre koji sadrže adresu trenutne (C) stavke liste i radnog registra koji sadrzi XOR trenutne adrese sa prethodnom adresom (C⊕D) :

 X  R2,Link    R2 <- C⊕D ⊕ B⊕D (tj. B⊕C, "Link" kao polje 
                                u trenutnom registru, koji sadrži B⊕D)
 XR R1,R2      R1 <- C ⊕ B⊕C    (tj. B,sledeci registar)
  • Kraj liste je označen zamišljajući stavku liste na adresi nula postavljenu susedno od krajnje tačke, kao {0 A B C...}. Polje na A bilo bi 0⊕B. Dodatna instrukcija je potrebna u gornjoj sekvenci posle dve XOR operacije da detektuje nulu u razvoju adrese trenutne stavke,
  • Krajnja tačka liste može biti reflektujuća tako što će pokazivač veza biti nula. Nula pokazivač je ogledalo. (XOR leve i desne susedne adrese,koji je isti, je nula.)


Nedostaci[уреди]

  • Alatke opšte namene za debagovanje ne mogu pratiti XOR sistem,što otežava otklanje grešaka;[1]
  • Cena smanjivanja upotrebe memorije je porast kompleksnosti koda,čineći održavanje skupljim;
  • XOR pokazivača nije definisan u nekim kontekstima(npr. C jezik),mada mnogi jezici pružaju neku vrstu konverzije izmedju pokazivača i celih brojeva;
  • Pokazivači će biti nečitljivi ako neki ne prelazi listu- na primer,ako je pokazivač na stavku liste sadržan u drugoj strukturi podataka;
  • Dok se lista prelazi,mora se pamtiti adresa prethodno pristupljenog čvora u cilju izračunavanja sledeće adrese čvora.
  • XOR povezane liste ne pružaju neke od bitnih prednosti dvostruko-povezane liste,kao što je mogućnost brisanja čvora iz liste znajući samo njegovu adresu, ili mogućnost ubacivanja novog čvora pre ili posle već postojećeg čvora znajući jedino adresu postojećeg čvora.

Varijacije[уреди]

Osnovni princip XOR povezane liste može se primeniti na bilo koje reverzibilne binarne operacije. Zamena XOR-a sabiranjem ili oduzimanjem daje malo drugačije,ali u velikoj meri ekvivalentne, formulacije:

Sabiranje povezane liste[уреди]

...  A        B         C         D         E  ...
        <–>  A+C  <->  B+D  <->  C+E  <->

Ova vrsta liste ima potpuno iste osobine kao XOR povezana lista , osim što nulto polje nije "ogledalo". Adresa sledećeg čvora u listi je data oduzimanjem prethodne adrese čvora sa trenutnim poljem čvora.

Oduzimanje povezane liste[уреди]

...  A        B         C         D         E  ...
        <–>  C-A  <->  D-B  <->  E-C  <->

Ova vrsta liste se razlikuje od "tradicionalne" XOR povezane liste u tome što su instrukcijske sekvence koje treba da prelaze listu unapred drugačije od sekvenici koje prelaze listu unatrag. Adresa sledećeg čvora,idući unapred,data je dodavanjem polja na prethodnu adresu čvora;adresa prethodnog čvora je data oduzimanjem polja sledeće adrese čvora.

Oduzimanje povezane liste je takodje posebno u tome što cela lista može biti premeštena u memoriju bez potrebe bilo kakvog zakrpljavanja vrednosti pokazivača. Ovo je prednost u odnosu nad obe XOR povezane liste i tradicionalne liste.


Vidi još[уреди]

Reference[уреди]