Algoritmi/Randomizacija

Pošto deterministički algoritmi dolaze do svojih krajnjih granica prilikom rešavanja teških problema, korisna tehnika za ubrzanje obrade je randomizacija. U randomizovanim algoritmima, algoritam ima pristup izvoru slučaja (random source) koji može da bude zamišljen kao bacanje novčića tokom izvršenja. U zavisnosti od rezultata bacanja, algoritam može da razdvoji putanju obrade. Postoje dva osnovna tipa randomizovanih algoritama: Las Vegas i Monte Karlo. Kod Las Vegas algoritama slučaj se koristi za ubrzanje izvršenja, ali algoritam uvek mora da da ispravan rezultat za zadate ulaze. Monte Karlo algoritmi nemaju prethodno ograničenje, što znači da oni mogu da daju i pogrešan rezultat. Ipak, davanje pogrešnog rezultata mora da bude malo verovatno, jer bi u suprotnom Monte Karlo algoritmi bili potpuno beskorisni. Mnogi aproksimacioni algoritmi koriste randomizaciju.

Statistika redova

Pre no što pokrijemo tehnike randomizacije, počećemo sa determinističkim problemom koji će nas dovesti do problema koji koristi randomizaciju. Pretpostavimo da imamo nesortirani vektor vrednosti i da želimo na nađemo:

maksimalnu vrednost,
minimalnu vrednost i
srednju vrednost.

Da pomenem besmrtne reči jednog od naših bivših profesora "Kako bi to uradili?"

find-max

Prvo, relativno je prosto naći najveći element:

// find-max -- враћа највећи елемент
function find-max(array vals[1..n]): element
  let result := vals[1]
  for i from 2 to n:
    result := max(result, vals[i])
  repeat
  
  return result
end

Inicijalizacija result na $-\infty$ bi takođe bila prihvatljiva, ali beskorisna, pošto bi prvi poziv funkcije max kao rezltat dao prvi element vektora. Inicijalizacija promenljive result kao u gornjem primeru, omogućava izvršenje samo n-1 poređenja. (Štaviše, u jezicima koji pružaju mogućnost meta-programiranja, tip podatka ne mora obavezno da bude numerički i tada ne postoji dobar način da se prestavi ; korišćenje vals[1] je bezbedno u odnosu na tip elemenata.) Slična rutina za pronalaženje najmanjeg elementa može da se napravi pozivom funkcije min umesto max.

find-min-max

Predpostavimo da hoćemo istovremeno da nađemo i min i max. Evo jednog rešenja:

// find-min-max -- враћа најмањи и највећи елемент у датом низу
function find-min-max(array vals): pair
  return pair {find-min(vals), find-max(vals)}
end

Pošto i find-max i find-min prave po n-1 poziva funkcije max odnosno min (kada vals sadrži n elemenata) ukupan broj poređenja funkcije find-min-max je $2n-2$ . Međutim, ovde se izvršavaju i neka redundantna poređenja. Ove redundase mogu da se uklone zajedničkim „tkanjem“ funkcija min i max:

// find-min-max -- враћа најмањи и највећи елемент у датом низу
function find-min-max(array vals[1..n]): pair
  let min :=  $\infty$ 
  let max :=  $-\infty$ 
  
  if n is odd:
    min := max := vals[1]
    vals := vals[2,..,n]          // сада можемо претоставити а је n паран број
    n := n - 1
  fi
  
  for i:=1 to n by 2:             // узети у обзир вредности парова у vals
    if vals[i] < vals[i + 1]:
      let a := vals[i]
      let b := vals[i + 1]
    else:
      let a := vals[i + 1]
      let b := vals[i]            // инваријанте: a <= b
    fi
    
    if a < min: min := a fi
    if b > max: max := b fi
  repeat
  
  return pair {min, max}
end

Ovde se kroz petlju prolazi $n/2$ puta umesto n puta, ali je za svaki prolaz potrebno izvršiti tri poređenja. Tako je broj poređenja koji treba da se izvede $(3/2)n=1.5n$ , što dovodi do ubrzanja za $3/4$ u odnosu na originalni algoritam. Potrebno je izvršiti samo tri poređenja umesto četiri, zato što je prema konstrukciji aloritma, uvek $a\leq b$ . (U prvom delu if-a, dobro znamo da je $a<b$ , ali u else delu možemo samo da zaključimo da je $a\leq b$ .) Ovo svojstvo je iskorišćeno tako što nema više potrebe da se a poredi sa tekućim maksimumom, zato što je b već veće ili jednako a i isto tako nema potrebe za poređenjem b sa tekućim minimumom, zato što je a već manje ili jednako b.

U softverskoj struci postoji borba između korišćenja biblioteka i pisanja posebnih (specijalnih) algoritama koji su maksimalno prilagođeni za rešavanje konkretnog problema. U našem slučaju bibliotečke funkcije min i max nisu korišćene za dobijanje brže rutine find-min-max. Korišćenje ovih funkcija, verovatno ne bi predstavljalo usko grlo u relanom životu, međutim, ako se testiranjem otkrije da rutina treba da bude brža, onda bi trebalo da se primeni pristup koji je i ovde primenjen. Rešenja koja koriste biblioteke su uglavnom bolja od specijalnih rešenja. Tehnike kao što su otvorene implementacije i aspektno-orijentisano programiranje mogu da pomognu u razrešenju navedene dileme, korišćenjem onog najboljeg iz oba pristupa. Bez obzira na sve, važno je da se razlika između korišćenja standardnih bibliotečkih funkcija i pisanja specijalnog koda jasno prepozna.

find-median

Konačno, treba da razmotrimo kako da nađemo srednju vrednost. Jedan od mogućih pristupa je da sortiramo dati vektor i onda srednju vrednost izdvojimo iz vals[n/2]:

// find-median -- враћа средњу вредност елемената у vals
function find-median(array vals[1..n]): element
  assert (n > 0)
  
  sort(vals)
  return vals[n / 2]
end

Ako naši brojevi nisu bliski po vrednosti ili ne mogu da se sortiraju pozicionim sortiranjem (radix sort) gornji algoritam će zahtevati $O(n\log n)$ koraka. Međutim, moguće je dobiti statistiku n-tog reda u $O(n)$ vremena. Ključno je da se izbaci sortiranje: nije nam, zapravo, potrebno da ceo vektor bude sortran da bi našli srednju vrednost, i zato postoje određeni gubici kada se prvo sortira ceo vektor. Tehnika koju ćemo koristiti da bi ovo postigli je slučajnost. Pre nogo što prikažemo funkciju find-median bez sortiranja, uvešćemo operaciju u stilu podeli i vladaj, poznatu kao particionisanje. Ono što želimo je rutina koja nalazi slučajni element vektora i onda particioniše (deli) vektor na tri dela:

elementi koji su manji ili jednaki slučajnom elementu;
elementi koji jednaki slučajnom elementu; i
elementi koji su veći ili jednaki slučajnom elementu.

Ova tri dela su označena celobrojnim promenljivim: j i i. Particionisanje se izvedi "na mestu", u vektoru:

// partition -- разбија низ у три партиције од случајног елемента
function partition(array vals): pair{j, i}

Primetimo da u slučaju da se izabrani slučajni element pojavljuje u vektoru tri ili više puta, moguće je da se vrednosti ovog elementa nalaze u sve tri particije vektora. Iako ova operacija ne deluje previše korisno, ona ima snažnu osobinu koja može da se iskoristi: kada se operacija particionisanja završi, slučajno izabrani element će se nalaziti na istom mestu u vektoru, na kom bi se nalazio da je izvršeno potpuno sortiranje vektora! Ova osobina možda ne deluje tako snažno, ali setite se optimizacije funkcije find-min-max: tada smo primetili da uzimanjem elemenata iz vektora u parovima i prvo njihovim međusobnim poređenjem, možemo smanjiti ukupan, potreban broj poređenja (zato što tekuće vrednosti min i max trebaju da se porede sa samo jednom vrednošću, a ne sa dve). Sličan koncept je primenjen i ovde. Dok kod za partition i nije neka magija, on ima neke složene granične slučajeve:

// partition -- разбија низ у три партиције од случајног елемента
function partition(array vals): pair{j, i}
  let m := 0
  let n := vals.length - 2   //  за низ vals, vals[vals.length-1] је последњи елемент, који носи партицију, 
                                     // тако да је последњи сортирани елемент vals[vals.length-2]
  let irand := random(m, n)   // враћа било коју вредност од m до n
  let x := vals[irand]
  swap( irand,n+ 1 ) // n+1 = vals.length-1 , који је најдешњији елемент и представља складиште за партиционе елемента и стражара за m
  // вредности у 'vals[n..] су веће од x
  // вредности у vals[0..m] су мање од x
  while (m <= n  ) // погледати објашњење у брзом сортирању зашто је m <= n уместо да је m < n у случају 2 елемента, 
                  // vals.length -2 = 0 = n = m, али ако је случај 2-елемента неуређен у односу на уређен, онда мора постојати друга акција.
                  // имплицирањем, друга акција се јавља заједно са петљом, тако треба да процесира m = n случај.
     while vals[m] <= x  // у случају 2-елемента, други елемент је партиција, а први елемент је у m. Ако је уређен, m ће се инкрементирати
        m++
     endwhile
     while x <  vals[n] && n > 0   // стаје ако vals[n] припада левој партицији или погоди почетак низа
        n--
     endwhile
     if ( m >= n) break;
     swap(m,n)                // замениvals[n] и vals[m]
     m++   // не освежавај замењене елементе
     n--
     
  endwhile
  // партиција: [0..m-1]   []   [n+1..]  приметити да m=n+1
  // ако је потребан непразан низ:
  swap(m,vals.length - 1)  // ставити пратиционирани елемент између леве и десне партиције
   // у случају 2-елемента који су неуређени, m=0 (није инкрементиран у петљи), и први и последњи (други) елементи ће размени места.
  // партиција: [0..n-1]   [n..n]   [n+1..]
end

Operaciju partition možemo da koristimo i kao podrutinu za opštu operaciju find:

// find -- помера елементе у vals тако да локација k садржи вредности када буду сортирани
function find(array vals, integer k)
  assert (0 <= k < vals.length)        // k мора бити валидан индекс
  if vals.length <= 1:
    return
  fi
  
  let pair (j, i) := partition(vals)
  if k <= i:
    find(a[0,..,i], k)
  else-if j <= k:
    find(a[j,..,n], k - j)
  fi
  
end

Što nas dovodi do poente:

 // find-median -- враћа средњу вредност у vals
function find-median(array vals): element
  assert (vals.length > 0)
  
  let median_index := vals.length / 2;
  find(vals, median_index)
  return vals[median_index]
end

Možda vam je kroz glavu prošla sledeća misao „a da li je neophodan slučajni poziv?“. Na primer, umesto da uzmemo slučajnu tačku oslonca, uvek možemo da umesto nje izaberemo srednji element. Uzimajući u obzir da naš algoritam radi sa svim mogućim vektorima, možemo da zaključimo da će njegovo vreme izvršenja za sve moguće ulaze u proseku biti isto kao i prilikom korišćenja randomizovane funkcije. Ovde je rezon da je uzimajući u obzir skup svih mogućih vektora, srednji element isto tako „slučajan“ kao i bilo koji drugi. Ali u ovakvom razmišljanju postoji zamka: tipično, ulaz u neki algoritam nije uopšte slučajan. Na primer, velika je verovatnoća da ulazni vektor već bude sortiran i to ne slučajno. Isto tako, pošto se radi o realnim podacima iz realnih programa, podaci mogu da dođu u najrazličitijim oblicima koji mogu da dovedu do podoptimalnih rezultata. Račeno na drugačiji način: za randomizovani algorita za nalaženje srednje vrednosti, postoji mala verovatnoća da će njegovo izvršenje biti podoptimalno, nezavisno od toga kakav je ulaz, dok za deterministički algoritam koji uzima srednji element, postoji veća šansa da će imati loše performanse sa nekim od čestih oblika ulaza. To nas dovodi do sledeće preporuke:

Preporuka o randomizaciji:
Ako vaš algoritam zavisi od slučajnosti, obavezno uvedite slučajnost sami, umesto da zavistite od slučajnih podataka.

Treba primetiti da postoje tehnike „derandomizacije“, koje mogu da pretvore algoritam koji je brz za prosečne slučajeve u potpuno deterministički algoritam. Ponekad je dopunski trošak derandomizacije toliko velik, da su potrebni veoma veliki skupovi podataka da bi se dobili bilo kakvi dobici. Uprkos tome, derandomizacija sama po sebi ima teorijsku vrednost. Randomizovani algoritam find je izumeo britanski naučnik Ser Čarls Entoni Ričard Hor. Iako je Hor važna figura u računarskoj nauci, ono po čemu je najviše poznat u širim krugovima je algoritam za brzo sortiranje (quicksort algorithm) o kome ćemo raspravljati u sledećem odeljku.

Brzo sortiranje

Algoritam za pronalaženje srednje vrednosti particionisanjem, koji je opisan u prethodnom odeljku, je, ustvari, vrlo blizu implementacije algoritma sortiranja u punom opsegu. Izgradnju algoritma za brzo sotiranje ostavljamo čitaocu da uradi kao vežbu i preporučujemo da to učini pre čitanja sledećeg odeljka (brzo sortiranje je „brutalno“ u odnosu na sortiranje spajanjem koje ne koristi randomizaciju). Ključni deo algoritma brzog sortiranja je izbor prave srednje vrednosti. Ali da bi ga brzo napravili, počnimo sa pretpostavkom da vektor nije sortiran i da je verovatnoća da krajnji desni element bilo kog vektora sadrži srednju vrednost, ista kao i za sve ostale elemente i da smo potpuno optimistični u pogledu toga da se ne dešava da krajnje desni element ima najveći ključ, što bi značilo da bi uklanjali samo jedan element (element particije) u svakom koraku i ne bi imali desni vektor za sortiranje, već samo levi dužine n-1. Upravo zbog ovoga je randomizacija važna za brzo sortitranje, t.j. izbor optimalnijeg ključa particije je prilično važno za efikasan rad brzog sotiranja. Uporedite broj poređenja neophodnih za brzo sortiranje u odnosu na sortiranje umetanjem. Kod sortiranja umetanjem, prosečan broj poređenja potrebnih za pronalaženje najmanjeg prvog elementa u uzlaznom sortiranju randomizovanog vektora je n /2 . Prosečan broj poređenja za drugi element je (n-1)/2; za treći element ( n- 2) / 2. Ukupan broj poređenja je [ n + (n - 1) + (n - 2) + (n - 3) .. + (n - [n-1]) ] podeljeno sa 2, što je [ n x n - (n-1)! ] /2, ili oko O(n na kvadrat). U brzom sortiranju, broj poređenja će biti prepolovljen na svakom koraku podele ako je izabrana istinska srednja vrednost, pošto particija leve polovine ne treba da se poredi sa desnom, ali u svakom koraku, broj elemenata svih particija napravljenih na prethodnom nivou particionisanja će opet biti n. Broj nivoa poređenja n elemenata je broj koraka deljenja n sa dva, dok ne bude n = 1. Ili unazad, 2 ^ m ~ n, so m = log₂(n) n. Tako je ukupan broj poređenja n (elemenata) x m (nivoa skeniranja) ili n x log2n, Sledi da je broj poređenja O(n x log ₂(n) ), što je manje nego kod sortiranja ubacivanjem gde je taj broj O(n^2) ili O( n x n ). (Poređenjem O(n x log ₂(n)) sa O( n x n ), zajednički faktor n može da se eliminiše i poredi se log₂(n) u odnosu na n, što čini eksponencijalnu razliku kako n raste, na primer uporedite n = 2^16 , ili 16 sa 32768, ili 32 u odnosu 4 giga.) Da bi se implementiralo particionisanje „na mestu“ na delu vektora koji je određen prethodnim rekurzivnim pozivom, potrebno je skeniranje sa oba kraja particije, zamena lokacija kad god je vrednost tekuće lokacije levog skeniranja veća od vrendosti particije i uvek kada je vrednost tekuće lokacije desnog skeniranja manja od vrednosti particije. Tako je početni korak:

 Доделити вредност партиције крајњем десном елементу, заменити их ако то је потребно.

Korak particionisanja je:

 инкрементирати леви показивач, док тренутна вредност није мања од вредности партиције.
 декрементирати десни показивач, док тренутна вредност не буде већа од вредности партиције,
 или док није једнака или већа од крајњој левој локацији.
 изаћи из петље уколико су се показиваћи сусрели( l >= r), 
 ИНАЧЕ
 заменити места елементима на којима леви и десни показивачи показују,
 на вредностима где је вредност левог показивача већа од партиције,
 и где је вредност десног показивача мања од партиције.

 КОначно, након што изађемо из петље, јер су се леви и десни показивач сусрели,
 заменити места крајњој десној вредности партиције, 
 са последњом локацијом левог показивача који иде унапред ,   
 и тако се завршава између леве и десне партиције.

Uverite se u ovom trenutku da su posle poslednje zamene slučajevi dva elementa u uređenom i dva elementa u neuređenom vektoru ispravno obrađeni, što bi trebalo da znači da su svi slučajevo korektno obrađeni. Ovo je dobar korak za otklanjanje eventualnih grešaka u algoritmu. Za slučaj dva uređena elementa, levi pokazivač se zaustavlja na particiji ili na drugom elementu pošto je pronađena vrednost particije. Desni pokazivač, skenirajući unazad, počinje od prvog elementa pre particije i zaustavlja se pošto je u krajnje levoj poziciji. Pokazivači se ukrštaju i izlazi se iz petlje pre nego što se napravi zamena u petlji. Van petlje, sadržaji levog pokazivača na krajnje desnoj poziciji i pokazivača particije, takođe na krajnje desnoj poziciji, se zamenjuju, čime se postiže da nema promene u slučaju dva uređena elementa. Za slučaj dva neuređena elementa, levi pokazivač se zaustavlja na prvom elementu, pošto je veći od vrednosti particije (vrednost dobijena levim skeniranjem zaustavlja zamenu vrednosti koje su veće od vrednosti particije). Desni pokazivač kreće i zaustavlja se na prvom elementu, pošto je dostigao krajnje levi element. Iz petlje se izlazi zato što su levi i desni pokazivači jednaki i pokazuju na prvu poziciju i sadržaj na koji pokazuje levi pokazivač (prva pozicija) se zamenjuje sa vrednošću particije na krajnje desnoj poziciji. Time prethodno neuređeni elementi postaju uređeni. Još jedno pitanje implementacije je, kako pomerati pokazivače za vreme skeniranja. Pomeranje na kraju spoljne petlje deluje logično.

partition(a,l,r) {
  v = a[r];
  i = l;
  j = r -1;
 while ( i <= j ) {  // потребно је такође скенирати када осмотрити када је i = j као и када је i < j , 
                           // у 2 уређеном случају, 
                           // тако да је i инкементиран партицији 
                           // и ништа се не дешава у завршној замени места са партицијама на r.
    while ( a[i] < v) ++i;
    while ( v <= a[j] && j > 0  ) --j;
    if ( i >= j) break;
    swap(a,i,j);
    ++i; --j;
 }
 swap(a, i, r);
 return i;

Sa unarnim operatorima preinkrementiranja / dekrementiranja, skeniranje može da se uradi neposredno pre testiranja uslova while petlje, ali to znači da pokazivači, na početku, moraju da se pomere za -1 odnodno +1 respektivno, tako da sada algoritam izgleda ovako:

partition (a, l, r ) {
 v=a[r]; // v је вредност партиције на позицији a[r]
 i=l-1;
 j=r;
 while(true) {
  while(  a[++i] < v ); 
  while( v <= a[--j]  && j > l );
  if (i >= j) break;
  swap ( a, i, j);
 }
 swap (a,i,r);
 return i;
}

i algoritam za qsort je

qsort( a, l, r)  {
  if (l >= r) return ;
  p = partition(a, l, r)
  qsort(a , l, p-1)
  qsort( a, p+1, r)

}

i konačno, randomizacija elementa particije.

random_partition (a,l,r) {
 p = random_int( r-l) + l;
 // median of a[l], a[p] , a[r]
 if (a[p] < a[l]) p =l;
 if ( a[r]< a[p]) p = r;
 swap(a, p, r);
}

Ovo može biti pozvano neposredno pre poziva finkcije partition u qsort().

Mešanje (elemenata) vektora

  Ово одржава податак у током мешања
  temporaryArray = { }
  Ово This евидентира да ли је елемент измешан
  usedItemArray = { }
  Број елемената у низу
  itemNum = 0
  while ( itemNum != lengthOf( inputArray) ){
      usedItemArray[ itemNum ] = false Ни један од елемената није био измешан
      itemNum = itemNum + 1
  }
  itemNum = 0 искористићемо га опет
  itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
  while( itemNum != lengthOf( inputArray ) ){
      while( usedItemArray[ itemPosition ] != false ){
          itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
      }
      temporaryArray[ itemPosition ] = inputArray[ itemNum ]
      itemNum = itemNum + 1
  }
  inputArray = temporaryArray

Heš tabele

Heširanje se oslanja na funkciju hashcode koja obezbeđuje slučajno i ravnomerno raspoređivanje ključeva za raspoložive slotove. U Javi se to radi prilično direktnim metodom sabiranja prostog broja srednje veličine (31 * 17) sa celobrojnim ključem po modulu veličine heš tabele. Za ključeve tipa niza simbola, početna vrednost heš broja se dobija sabiranjem rezultata množenja rednog broja svakog simbola sa 31. Viki knjiga Strukture podataka u poglavlju Heš tabele dobro pokriva ovu temu.

Skip liste

Rečnik ili mapa, je opšti koncept u kome se vrednost ubacuje pod nekim ključem i nalazi na osnovu tog ključa. Na primer, u nekim jezicima koncept rečnika je ugrađen u sam jezik (Python) dok je u drugim on deo osnovnih biblioteka (C++ standardna biblioteka šablona i Java standardna biblioteka kolekcija). Jezici koji realizuju koncet rečnika u okviru biblioteka, obično pružaju mogućnost programeru da izabere između heš algoritma i implementacije zasnovane na uravnoteženom binarnom stablu (crveno-crna stabla). Nedavno su ponuđene skip liste (liste sa preskakanjem) koje pružaju velike prednosti prilikom implementacija u okviru aplikacija u konkurentnom okruženju sa više niti izvršenja. Hešovanje je tehnika koja zavisi od slučajnosti ključeva koji se propuštaju kroz heš funkciju da bi se našla vrednost koja odgovara indeksu linearne tabele.

Hešovanje radi onoliko brzo koliko i heš funkcija, ali radi dobro samo ako su ubačeni ključevi revnomerno raspoređeni u vektoru, kao i bilo koji ključevi koji se heširaju na isti indeks. Mora da postoji dogovor oko problema heš sudara, na primer čuvanje ulančane liste sudara za svaki slot tabele i iteracija kroz listu da bi se uporedio puni ključ za svaki par ključ-vrednost u odnosu na ključ pretraživanja. Nedostatak hešovanja je u tome što simetrični (in-order) obilazak nije moguć sa ovakvom strukturom podataka. Binarna stabla mogu da se koriste za predstavljanje rečnika, a simetrični obilazak binarnog stabla je moguć rekurzivnom posetom čvorova (poseta levog deteta, poseta korenu i poseta desnog deteta). Binarna stabla se loše pretražuju kada su „neuravnotežena“, npr. ključevi parova ključ-vrednost su umetnuti po rastućem ili po opadajućem redosledu, tako da efektivno izgledaju kao ulančane liste bez leve dece, samo sa desnom decom. Samouravnotežujuća (self-balancing) binarna stabla mogu da se naprave probabilistički (koristeći slučajnost) ili deterministički (bojenjem veza sa decom u crveno ili crno), preko operacija rotacije lokalnih stabala sa tri čvora. Rotacija je jednostavno zamena čvora roditelja sa čvorom detetom, ali uz očuvanje poretka. Na primer, za rotaciju levog deteta, njegovo desno dete postaje levo dete roditelja, a roditelj postaje njegovo desno dete.

Crveno-crna stabla mogu lakše da se razumeju ako se ispita odgovarajuće 2-3-4 stablo. 2-3-4 stablo može da ima 2-je, 3-je ili 4-oro dece, s tim da čvorovi sa 3-je dece imaju 2 ključa između 3 deteta i čvarovi sa 4-oro dece (4-čvorovi) imaju 3 ključa između 4 deteta. 4-čvorovi mogu da se podele na 3 2-čvora sa jednim ključem i srednji 2-čvor dodaje naviše da bi se spojio sa čvorom roditelja koji, ako je bio 2-čvor sa jednim ključem postaje 3-čvor sa dva ključa, ili ako je bio 3-čvor sa dva ključa postaje 4-čvor, koji će kasnije biti podeljen (na putu naviše). Čin podele 4-čvora sa tri ključa je ustvari operacija ponovnog uravnotežavanja koja sprečava da se niz od 3 čvora: pra-roditelj (deda), roditelj i dete, pojavljuju bez uravnotežujuće rotacije. 2-3-4 stabla su ograničen primer B-stabala, koji obično imaju dovoljno čvorova da se smeste u okviru jednog fizičkog bloka na disku i da olakšaju keširanje veoma velikih indeksa koji ne mogu da stanu u operativnu memoriju RAM (danas je to manje bitno).

Crveno-crno stablo je binarna predstava 2-3-4 stabla, gde su 3-čvorovi modelirani pomoću roditelja sa jednim crvenim detetom, a 4-čvorovi pomoću roditelja sa 2 crvena deteta. Cepanje 4-čvora je predstavljeno roditeljem sa 2 crvena deteta i preobraćanjem (flipping) crvene dece u crnu, a samog sebe u crveno. Ne postoji slučaj u kome je roditelj već crven, zato što se izvršavaju operacije uravnotežavanja kod kojih, ako postoji pra-roditelj sa crvenim detetom (roditeljem) koje ima crveno dete, pra-roditelj se rotira tako da postaje dete roditelja (svog deteta) i roditelj postaje crn, a pra-roditelj postaje crven; ovo objedinjuje prethodni scenario preobraćanja (flipping) jednog 4-čvora predstavljenog sa 2 crvena deteta. Zapravo, možda ova standardizacija 4-čvorova sa obaveznom rotacijom iskrivljenih ili cik-cak 4-čvorova, dovodi do ponovnog uravnoteženja binarnog stabla. Novija optimizacija je da se ulevo rotira bilo koje desno crveno i levo crveno dete, tako da samo desna rotacija levih iskrivljenja u okviru 4-čvorova (3 crvena čvora) može ikada da je pojavi, čime se pojednostavljajući kod za ponovno uravnotežavanje.

Skip liste su modelovane na usnovu jednostruko ulančanih lista, osim što su čvorovi višenivoski. Čvorovi višeg nivoa (visoki čvorovi) su ređi, ali operacija umetanja obezbeđuje povezanost čvorova na svakom nivou. Implementacija skip lista zahteva stvaranje nasumično visokih višenivoskih čvorova i zatim njihovo umetanje. Čvorovi se stvaraju iteracijom slučajne funkcije, u kojoj se čvorovi višeg nivoa pojavljuju u kasnijim iteracijama i ređi su, zato što je iteracijama već pređen veliki broj pragova slučajnosti (na primer 0,5, ako je slučajni broj između 0 i 1). Umetanje zahteva privremeni vektor prethodnog čvora nivoa generisanog čvora za umetanje. On se koristi za čuvanje poslednjeg pokazivača za zadati nivo, koji ima ključ manji od ključa umetanja. Skeniranje počinje od početka skip liste, na najvišem nivou i nastavlja se dok se ne nađe čvor čiji je ključ veći od ključa umetanja i dok se prethodni pokazivač ne sačuva u privremeni vektor prethodnog čvora. Tada se prelazi na sledeći, niži, nivo koji se skenira i tako dalje, idući u cik-cak, dok se ne dostigne najniži nivo. Umetanje se vrši na svakom nivou privremenog vektora prethodnog čvora, tako da naredni čvor prethodnog čvora na svakom nivou postaje naredni čvor za umetnuti čvor, a umetnuti čvor postaje naredni za prethodni čvor. Pretraživanje podrazumeva iteracije od najvišeg do najnižeg nivoa početnog čvora i skeniranje duž liste na svakom nivou dok se ne pronađe čvor čija je vrednost veća od traženog ključa, pomerajući se naniže na sledeći nivo i nastavljajući skeniranje dok se ne pronađe čvor sa većim ključem od traženog na najnižem nivou, ili se pronađe traženi ključ. Stvaranje čvorova slučajne visine koji su manje učestali kada su na višem nivou i proces povezivanja sa drugim čvorovima na svakom nivou, je ono što čini skip listu korisnom strukturom.

metoda za implementaciju skip liste: implementirajte jednostruko ulančanu listu, testirajte, zatim je transformišite u skip listu, onda ponovo testirajte i uporedite performanse

Ono što sledi je implementacija skip listi u jeziku Python. Prvo je implementirana jednostruko ulančana lista koja na sledeći čvor uvek gleda kao na tekući, a zatim sledi implementacija skip liste uz minimalne modifikacije i, na kraju, poređenje koje pomaže da se razjasni implementacija.

#copyright SJT 2014, GNU
#почети имплементацијом једноструко поверане листе:
#главни чвор има показивач на почетак листе и тренутни чвор испитује следећи чвор.
#Ово је много лакше од тога да је главни чвор један од ускладиштених чворова.
class LN:
  "a list node, so don't have to use dict objects as nodes" 
  def __init__(self):
     self.k=None
     self.v = None
     self.next = None

class single_list2:

  def __init__(self):
     self.h = LN() 

  def insert(self, k, v):
     prev = self.h
     while not prev.next is None and  k < prev.next.k :
       prev = prev.next
     n = LN()
     n.k, n.v = k, v
     n.next = prev.next
     prev.next = n 

  def  show(self):
     prev = self.h
     while not prev.next is None:
        prev = prev.next
        print prev.k, prev.v, ' '

  def find (self,k):
     prev = self.h
     while not prev.next is None and k < prev.next.k:
       prev = prev.next
     if prev.next is None:
       return None
     return prev.next.k

#онда након тестирања једноструко-повезане листе, моделовати SkipList након тога.
# Главне услове које треба запамтити када трансформишете код једноструко-повезане листе у код скип листе:
# * чворови виших-нивоа су убачени
# * главни чворови морају бити висине чворова коју су убачени
# * креће се уназад по доњим нивоима, од највишег до најнижег, када се врши убацивање или претрага, 
# ово је основа ефикасности алгоритма, како се виши чворови ређе појављују и шире разилазе.
import random
class SkipList3:
  def __init__(self):
      self.h = LN() 
      self.h.next = [None]

  def insert( self, k , v):
      ht = 1
      while random.randint(0,10) < 5:
        ht +=1
      if ht > len(self.h.next) :
          self.h.next.extend( [None] * (ht - len(self.h.next) ) )      
      prev = self.h 
      prev_list = [self.h] * len(self.h.next)

      # уместо да само prev.next у једноструко-повезаној листи, сваки ниво i има prev.next 
      for i in xrange( len(self.h.next)-1, -1, -1):
           
           while not prev.next[i] is None and prev.next[i].k > k:
              prev = prev.next[i]
           
           
           #евидентирати претходни показивач за сваки ниво
           prev_list[i] = prev

      n = LN()
      n.k,n.v = k,v

      # креирати next показивач који показује на висину чвора за тренутни чвор.
      n.next = [None] * ht
      #print "prev list is ", prev_list

      # уместо да се само повезују чворови у једноструко-повезаној листи, нпр. n.next = prev.next, prev.next =n
      # урадити за сваки ниво n.next користећи n.next[i] и prev_list[i].next[i]
      # може бити различитих prev чворова за сваки ниво, али исти нивои морају бити повезани,
      # тако се индекс [i] појављује два пута у prev_list[i].next[i]. 
      
      for i in xrange(0, ht):
         n.next[i] = prev_list[i].next[i]
         prev_list[i].next[i] = n
      
      #print "self.h ", self.h 
  
  def show(self):
      #print self.h
      prev = self.h
      while not prev.next[0] is None:
         print prev.next[0].k, prev.next[0].v
         prev = prev.next[0]

  def find(self, k):
      prev = self.h
      h = len(self.h.next)
      #print "height ", h
      for i in xrange( h-1, -1, -1):
      	while not prev.next[i] is None and prev.next[i].k > k:
             prev = prev.next[i]
        #if prev.next[i] <> None:
		#print "i, k, prev.next[i].k and .v", i, k, prev.next[i].k, prev.next[i].v
        if prev.next[i] <> None and prev.next[i].k ==  k:
             return prev.next[i].v 
      if pref.next[i] is None:
        return None
      return prev.next[i].k

  def clear(self):
      self.h= LN()
      self.h.next = [None]

#driver
if __name__ == "__main__":
  #l  = single_list2() 
  l  = SkipList3() 
  test_dat = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  pairs =  enumerate(test_dat) 
  m = [ (x,y) for x,y in pairs ]
  while len(m) > 0:
    i = random.randint(0,len(m)-1)
    print "inserting ", m[i]
    l.insert(m[i][0], m[i][1])     
    del m[i]
  #  l.insert( 3, 'C')
  #  l.insert(2, 'B') 
  #  l.insert(4, 'D')
  #  l.insert(1, 'A')
  l.show()
  
  n = int(raw_input("How many elements to test?") )
  if n <0: n = -n
  l.clear()
  import time 
  l2 = [ x for x in xrange(0, n)]
  random.shuffle(l2)
  for x in l2:
    l.insert(x , x)
  l.show()
  print
  print "finding.."
  f = 0
  t1 = time.time()
  nf = []
  for x in l2: 
     if l.find(x) == x:
           f += 1
     else:
       nf.append(x)
  t2 = time.time()
  
  print "time", t2 - t1
  td1 = t2 - t1
  print "found ", f 
  print "didn't find", nf 
  dnf = []
  for x in nf:
    tu = (x,l.find(x))
    dnf.append(tu)
  print "find again ", dnf
  sl = single_list2()
  for x in l2:
    sl.insert(x,x)
  print "finding.."
  f  = 0
  t1 = time.time()
  for x in l2: 
     if sl.find(x) == x:
           f += 1
  t2 = time.time()
  print "time", t2 - t1
  print "found ", f
  td2 = t2 - t1
  print "factor difference time", td2/td1

Uloga slučajnosti

Ideja da se čvorovi višeg nivoa prave slučajno sa geometrijski manjom verovatnoćom, znači da na višim nivoima postoji manji broj ključeva koje treba porediti, a pošto su čvorovi slučajno izabrani, trebalo bi da budemo pošteđeni problema degenerisanih ulaza koji u algoritmima stabla zahtevaju da se ono uravnotežava. Pošto liste višeg nivoa imaju šire razdvojene elemente, a algoritam pretraživanja se premešta na niži nivo svaki put kada završi sa tekućem nivou, viši nivo pomaže da se „preskoče“ pretraživanja ranijih elemenata u listama nižeg nivoa. Pošto ima više nivoa preskakanja, postaje manje verovatno da oskudan preskok na višem nivou neće biti kompenzovan sa boljim preskocima na nižim nivoima. Pju (Pugh) tvrdi da su opšte performanse algoritma pretraživanja skip liste O(logN). Konceptualno, da je lakše razumeti skip liste od uravnotežavanja stabala i stoga ih lakše implementirati? Razvoj ideja binarnih stabala, uravnoteženih binarnih stabala, 2-3 stabala, crveno-crnih stabala i B-stabala, daju čvršću konceptualnu osnovu, ali i sporost u razvoju, tako da verovatno, jednom kada se razumeju crveno-crna stabla ona poseduju više konceptualnog konteksta koji može da pomogne ili osveži pamćenje.

primena konkurentnog pristupa

Sem upotrebe randomizacije radi unapređenja osnovnih struktura podataka kao što je ulančana lista, skip lista može da se proširi kao globalna struktura podataka koja se koristi u višeprocesorkim primenama. Vidi dopunsku temu na kraju poglavlja.

Ideja za vežbu

Zameni sasvim solidan raspoređivač (dispečer) Linux-a zasnovan na implementaciji crveno-crnog stabla sa skip listom i vidi kako tvoja vrsta Linux-a radi posle rekompilacije.

Dekartova stabla

Dekartovo stablo je binarno stablo sa dva ključa, koje koristi drugi, slučajno generisani ključ i prethodno razmotrene operacije rotacije roditelj-dete, da nasumično rotira stablo, tako da je ono na kraju postane uravnoteženo. Setimo se da binarna stabla rade tako što sadrže sve čvorove manje od zadatog u levom podstablu, a sve veće u desnom. Setimo se, takođe, da rotacija čvorova ne narušava ovaj poredak (neki ovo zovu invarijantnost roracije) ali menja odnos roditelja i deteta, tako što, ako je roditelj bio manji od desnog deteta, onda roditelj postaje levo dete svog, prethodno desnog deteta. Ideja hip stabla ili Dekartovog stabla je da se binarna hip relacija održava između roditelja i dece i da čvor roditelja ima veći prioritet od čvorova svoje dece, što nije isto kao i levi i desni poredak ključeva kod binarnog stabla. Stoga novoumetnuti čvor lista u binarno stablo, za koji se desi da ima visoki slučajni prioritet, može da bude rotiran tako da bude na relativno višoj poziciji u stablu i da pri tome nema roditelja sa nižim prioritetom. Dekartovo stablo je alternativa i crveno-crnim stablima i skip listama, kao samouravnotežujuća, sortirana struktura podataka.

primer implementacije Dekartovog stabla u Javi

// Treap example: 2014 SJT, copyleft GNU .
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class Treap1<K extends Comparable<K>, V> {
	public Treap1(boolean test) {
		this.test = test;
	}

	public Treap1() {}
	boolean test = false;
	static Random random = new Random(System.currentTimeMillis());

	class TreapNode {
		int priority = 0;
		K k;
		V val;
		TreapNode left, right;

		public TreapNode() {
			if (!test) {
				priority = random.nextInt();
			}
		}
	}

	TreapNode root = null;

	void insert(K k, V val) {
		root = insert(k, val, root);
	}

	TreapNode insert(K k, V val, TreapNode node) {
		TreapNode node2 = new TreapNode();
		node2.k = k;
		node2.val = val;
		if (node == null) {
			node = node2;
		} else if (k.compareTo(node.k) < 0) {

			node.left = insert(k, val, node.left);

		} else {

			node.right = insert(k, val, node.right);

		}

		if (node.left != null && node.left.priority > node.priority) {
			// десна ротација (ротирањем левог чвора на горе, тренутни чвор постаје десно дете)
			TreapNode tmp = node.left;
			node.left = node.left.right;
			tmp.right = node;
			node = tmp;
		} else if (node.right != null && node.right.priority > node.priority) {
			// лева ротација (ротирањем десног чвора на горе, тренутни чвор постаје лево дете)
			TreapNode tmp = node.right;
			node.right = node.right.left;
			tmp.left = node;
			node = tmp;
		}
		return node;
	}

	V find(K k) {
		return findNode(k, root);
	}

	private V findNode(K k, Treap1<K, V>.TreapNode node) {
		if (node == null)
			return null;
		if (k.compareTo(node.k) < 0) {
			return findNode(k, node.left);
		} else if (k.compareTo(node.k) > 0) {
			return findNode(k, node.right);
		} else {
			return node.val;
		}
	}

	public static void main(String[] args) {
		LinkedList<Integer> dat = new LinkedList<Integer>();

		for (int i = 0; i < 15000; ++i) {
			dat.add(i);
		}
	
			testNumbers(dat, true); // нема балансирања случајног приоритета
			testNumbers(dat, false);
	}

	private static void testNumbers(LinkedList<Integer> dat,
			boolean test) {
		Treap1<Integer, Integer> tree= new Treap1<>(test);

		for (Integer integer : dat) {
			tree.insert(integer, integer);
		}

		long t1 = System.currentTimeMillis();
		Iterator<Integer> iter = dat.iterator();
		int found = 0;
		while (iter.hasNext()) {
			Integer j = desc.next();
			Integer i = tree.find(j);
			if (j.equals(i)) {
				++found;
			}
		}
		long t2 = System.currentTimeMillis();
		System.out.println("found = " + found + " in " + (t2 - t1));
	}
}

Poređenje Dekartovih i raširenih stabala

Raširena stabla su slična Dekartovim u tome što se koristi rotacija da se čvor većeg prioriteta dovede na vrh bez da se pri tome menja osnovni redosled ključeva, osim što umesto upotrebe slučajnog ključa za prioritet, rotira se poslednji čvor kome se pristupilo u koren stabla, tako da će se čvorovi kojima se češće pristupa nalaziti blizu vrha. To znači da će u Dekartovm stablima umetnuti čvorovi rotirati najviše do prioriteta koji im određuje slučajni ključ prioriteta, dok kod raširenih stabala, umetnuti čvor rotira do korena, i svako pretraživanje u raširenom stablu će rezltirati u ponovnom uravnotežavanju, što nije slučaj kod Dekartovog stabla.

Derandomizacija

Vežbe

1. Napišite funkciju find-min i izvršite je sa više različiti ulaza da bi pokazali njenu ispravnost.

Dopunska tema: skip liste i višeprocesorski algoritmi

Višeprocesorski hardver obezbeđuje atomičke operacije CAS (uporedi i postavi) ili CMPEXCHG (uporedi i razmeni) (intel manual 253666.pdf, str. 3-188), gde se očekivana vrednost puni u akumulator, čiji se sadržaj poredi sa sadržajem ciljne memorijske lokacije i, ako su isti, sadržaj izvorne memorijske lokacije se puni u ciljnu memorijsku lokaciju i podiže se (signalna) zastavica nule (zero flag set), u suprotnom, ako su različiti, sadržaj ciljne memorijske lokacije se vraća u akumulator i zastavica nule se spušta (zero flag unset), označavajući da je, na primer, došlo do pokušaja istovremnog zaključavanja. U intel arhitekturi instrukcija LOCK se izdaje pre CMPEXCHG, koja za sledeću inskrukciju, ili zaključava keš za konkurentne pristupe ako je memorijska lokacija keširana, ili zaključava lokaciju zajedničke memorije ako lokacija nije u kešu. CMPEXCHG može da se koristi za implementaciju zaključavanja od kojih su spinlokovi najjednostavniji (npr. neprestani pokušaji, dok se zastavica nule ne podigne). Pristup bez zaključavanja povećava efikasnost, tako što se izbegava čekanja na zaključavanje. Standardna biblioteka jezika Java ima implementaciju neblokirajućih konkurentnih skip lista, zasnovanu na radu pod nazivom "Pragmatična implementacija neblokirajućih jednostruko ulančanih lista“ Implementacija za skip liste je proširenje implementacije za jednostruko ulančane liste bez zaključavanja. Opis sledi:

Operacija insert je: X -> Y umetni N , N -> Y, X -> N i očekivani rezultat je X -> N -> Y. Utrkivanje (race condition) je ako se M umeće između X i Y i ubacivanje M se prvo završava, a zatim se završava umetanje N, tako da se dobija sledeća situacija X -> N -> Y <- M. M nije u listi. Operacija CAS izbegava ovo, zato što se pre ažuriranja X ->, prvo proverava kopija -> Y u odnosu na trenutnu vrednost X ->. Ako N uspe prvi da ažurira X -> onda, kada M pokuša da ažurira X ->, kopija X -> Y, koja se pravi pre M -> Y, ne odgovara X -> N, tako da CAS vraća podignutu zastavicu ne-nula (non-zero flag set). Proces koji je probao da umetne M, može ponovo da pokuša umetanje posle X, ali sada CAS proverava da li je ->N sledeći pokazivač na X, tako da je posle ponovljenog pokušaja X->M->N->Y i nijedno umetanje nije izgubljeno. Ako M prvo ažurira X->, kopija X->Y koja se pravi pre umetanja N, ne odgovara X -> M, tako da će CAS i ovde biti neuspešan i gore pomenuti ponovni pokušaj umetanja N imaće kao rezultat X ->N -> M -> Y. Operacija delete zavisi od posebnog „logičkog“ koraka brisanja, pre „fizičkog“ brisanja. „Logičko“ brisanje podrazumeva da CAS izvrši pretvaranje pokazivača na sledeći čvor u „obeleženi“ pokazivač. Implementacija u Javi zamenjuje ovo sa atomičkim umetanjem obeleženog zastupajućeg (proxy) čvora ispred sledećeg čvora. Ove sprečava buduća umetanja posle čvora koji ima „obeležen“ pokazivač na sledeći i time čini da je potonji čvor „logički“ izbrisan. Operacija insert se oslanja na drugu funkciju search koja prilikom poziva vraća 2 unmarked, pokazivača čvora: prvi koji pokazuje na čvor čiji je pokazivač na sledeći jednak drugom. Prvi čvor je čvor pre mesta umetanja.

Operacija insert CAS-a obezbeđuje da tekući pokazivač prvog čvora na sledeći odgovara neobeleženoj referenci na drugi, tako da će biti „logički“ neispešna ako pokazivač na sledeći prvog čvora postane obeležen posle poziva funkcije search, zato što je prvi čvor istovremeno logički izbrisan. Ovo zadovoljava zahtev da se spreči pojava istovremenog umetanja, pošto je čvor već obrisan. Ako je operacija umetanja u CAS-u neuspešna zbog pokazivača na sledeći prethodnog čvora, traženje mesta umetanja ponovo počinje od početka cele liste, pošto novi neobeleženi prethodni čvor mora da se pronađe, a ne postoji pokazivač na prethodni pošto je lista jednostruko ulančana.

Operacija delete izložena gore, takođe se oslanja na operaciju search koja vraća dva neobeležena čvora, a dve CAS operacije brisanja: jedna za logičko brisanje ili obeležavanje pokazivača na sledeći drugog pokazivača i druga za fizičko brisanje tako što čini da pokazivač na sledeći prvog čvora pokazuje isto što i neobeleženi pokazivač na sledeći drugog čvora. Prva CAS operacija brisanja se dešava samo posle provere da li je kopija originalnog pokazivača na sledeći drugog čvora neobeležena i obezbeđuje da uspe samo jedno konkurentno brisanje, koje čita tekući pokazivač na sledeći drugog čvora koji je isto tako neobeležen. Druga CAS operacija utvrđuje da prethodni čvor nije logički obrisan, pošto njegov pokazivač na sledeći nije isti kao neobeleženi pokazivač na tekući drugi čvor, koji vraća funkcija search, tako da se samo aktivni pokazivač na sledeći prethodnog čvora „fizički“ ažurira prema kopiji originalnog, neobeleženog pokazivača na sledeći čvora koji se briše (čiji je pokazivač na sledeći već obeležen u prvom CAS-u). Ako drugi CAS ne uspe, onda je prethodni čvor logički obrisan, a njegov pokazivač na sledeći je obeležen, isto kao i pokazivač na sledeći tekućeg čvora. Poziv funkcije search, ponovo sve dovodi u red, pošto nastojeći da nađe ključ tekućeg čvora i da vrati susedne neobeležene pokazivače na prethodni i tekući čvor i dok to radi skraćuje nizove logički obrisanih čvorova.

Pitanja programiranja bez zaključavanja

Iscrpljivanje je moguće kada neuspešna umetanja moraju da se ponavljaju od početka liste. Bez čekanja (wait-freedom) je koncept u kome algoritam ima sve niti izvršenja zaštićene od iscrpljivanja. Kod ABA problema, gde sakupljač smeća (garbage collector) reciklira pokazivač A, ali se adresa puni na različite načine i pokazivač se ponovno dodaje u tački gde se vrši provera A od strane druge niti izvršenja koja čita A i izvršava CAS da utvrdi da se A nije promenio; Adresa je ista i nije obeležena, ali je sadržaj A promenjen.