Алгоритми/Рандомизација

Пошто детерминистички алгоритми долазе до својих крајњих граница приликом решавања тешких проблема, корисна техника за убрзање обраде је рандомизација. У рандомизованим алгоритмима, алгоритам има приступ извору случаја (random source) који може да буде замишљен као бацање новчића током извршења. У зависности од резултата бацања, алгоритам може да раздвоји путању обраде. Постоје два основна типа рандомизованих алгоритама: Лас Вегас и Монте Карло. Код Лас Вегас алгоритама случај се користи за убрзање извршења, али алгоритам увек мора да да исправан резултат за задате улазе. Монте Карло алгоритми немају претходно ограничење, што значи да они могу да дају и погрешан резултат. Ипак, давање погрешног резултата мора да буде мало вероватно, јер би у супротном Монте Карло алгоритми били потпуно бескорисни. Многи апроксимациони алгоритми користе рандомизацију.

Статистика редова

Пре но што покријемо технике рандомизације, почећемо са детерминистичким проблемом који ће нас довести до проблема који користи рандомизацију. Претпоставимо да имамо несортирани вектор вредности и да желимо на нађемо:

максималну вредност,
минималну вредност и
средњу вредност.

Да поменем бесмртне речи једног од наших бивших професора "Како би то урадили?"

find-max

Прво, релативно је просто наћи највећи елемент:

// 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

Иницијализација result на $-\infty$ би такође била прихватљива, али бескорисна, пошто би први позив функције max као резлтат дао први елемент вектора. Иницијализација променљиве result као у горњем примеру, омогућава извршење само n-1 поређења. (Штавише, у језицима који пружају могућност мета-програмирања, тип податка не мора обавезно да буде нумерички и тада не постоји добар начин да се престави ; коришћење vals[1] је безбедно у односу на тип елемената.) Слична рутина за проналажење најмањег елемента може да се направи позивом функције min уместо max.

find-min-max

Предпоставимо да хоћемо истовремено да нађемо и min и max. Ево једног решења:

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

Пошто и find-max и find-min праве по n-1 позива функције max односно min (када vals садржи n елемената) укупан број поређења функције find-min-max је $2n-2$ . Међутим, овде се извршавају и нека редундантна поређења. Ове редундасе могу да се уклоне заједничким „ткањем“ функција min и 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

Овде се кроз петљу пролази $n/2$ пута уместо n пута, али је за сваки пролаз потребно извршити три поређења. Тако је број поређења који треба да се изведе $(3/2)n=1.5n$ , што доводи до убрзања за $3/4$ у односу на оригинални алгоритам. Потребно је извршити само три поређења уместо четири, зато што је према конструкцији алоритма, увек $a\leq b$ . (У првом делу if-а, добро знамо да је $a<b$ , али у else делу можемо само да закључимо да је $a\leq b$ .) Ово својство је искоришћено тако што нема више потребе да се a пореди са текућим максимумом, зато што је b већ веће или једнако a и исто тако нема потребе за поређењем b са текућим минимумом, зато што је a већ мање или једнако b.

У софтверској струци постоји борба између коришћења библиотека и писања посебних (специјалних) алгоритама који су максимално прилагођени за решавање конкретног проблема. У нашем случају библиотечке функције min и max нису коришћене за добијање брже рутине find-min-max. Коришћење ових функција, вероватно не би представљало уско грло у реланом животу, међутим, ако се тестирањем открије да рутина треба да буде бржа, онда би требало да се примени приступ који је и овде примењен. Решења која користе библиотеке су углавном боља од специјалних решења. Технике као што су отворене имплементације и аспектно-оријентисано програмирање могу да помогну у разрешењу наведене дилеме, коришћењем оног најбољег из оба приступа. Без обзира на све, важно је да се разлика између коришћења стандардних библиотечких функција и писања специјалног кода јасно препозна.

find-median

Коначно, треба да размотримо како да нађемо средњу вредност. Један од могућих приступа је да сортирамо дати вектор и онда средњу вредност издвојимо из vals[n/2]:

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

Ако наши бројеви нису блиски по вредности или не могу да се сортирају позиционим сортирањем (radix sort) горњи алгоритам ће захтевати $O(n\log n)$ корака. Међутим, могуће је добити статистику n-тог реда у $O(n)$ времена. Кључно је да се избаци сортирање: није нам, заправо, потребно да цео вектор буде сортран да би нашли средњу вредност, и зато постоје одређени губици када се прво сортира цео вектор. Техника коју ћемо користити да би ово постигли је случајност. Пре ного што прикажемо функцију find-median без сортирања, увешћемо операцију у стилу подели и владај, познату као партиционисање. Оно што желимо је рутина која налази случајни елемент вектора и онда партиционише (дели) вектор на три дела:

елементи који су мањи или једнаки случајном елементу;
елементи који једнаки случајном елементу; и
елементи који су већи или једнаки случајном елементу.

Ова три дела су означена целобројним променљивим: j и i. Партиционисање се изведи "на месту", у вектору:

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

Приметимо да у случају да се изабрани случајни елемент појављује у вектору три или више пута, могуће је да се вредности овог елемента налазе у све три партиције вектора. Иако ова операција не делује превише корисно, она има снажну особину која може да се искористи: када се операција партиционисања заврши, случајно изабрани елемент ће се налазити на истом месту у вектору, на ком би се налазио да је извршено потпуно сортирање вектора! Ова особина можда не делује тако снажно, али сетите се оптимизације функције find-min-max: тада смо приметили да узимањем елемената из вектора у паровима и прво њиховим међусобним поређењем, можемо смањити укупан, потребан број поређења (зато што текуће вредности min и max требају да се пореде са само једном вредношћу, а не са две). Сличан концепт је примењен и овде. Док код за partition и није нека магија, он има неке сложене граничне случајеве:

// 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

Операцију partition можемо да користимо и као подрутину за општу операцију 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

Што нас доводи до поенте:

 // 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

Можда вам је кроз главу прошла следећа мисао „а да ли је неопходан случајни позив?“. На пример, уместо да узмемо случајну тачку ослонца, увек можемо да уместо ње изаберемо средњи елемент. Узимајући у обзир да наш алгоритам ради са свим могућим векторима, можемо да закључимо да ће његово време извршења за све могуће улазе у просеку бити исто као и приликом коришћења рандомизоване функције. Овде је резон да је узимајући у обзир скуп свих могућих вектора, средњи елемент исто тако „случајан“ као и било који други. Али у оваквом размишљању постоји замка: типично, улаз у неки алгоритам није уопште случајан. На пример, велика је вероватноћа да улазни вектор већ буде сортиран и то не случајно. Исто тако, пошто се ради о реалним подацима из реалних програма, подаци могу да дођу у најразличитијим облицима који могу да доведу до подоптималних резултата. Рачено на другачији начин: за рандомизовани алгорита за налажење средње вредности, постоји мала вероватноћа да ће његово извршење бити подоптимално, независно од тога какав је улаз, док за детерминистички алгоритам који узима средњи елемент, постоји већа шанса да ће имати лоше перформансе са неким од честих облика улаза. То нас доводи до следеће препоруке:

Препорука о рандомизацији:
Ако ваш алгоритам зависи од случајности, обавезно уведите случајност сами, уместо да завистите од случајних података.

Треба приметити да постоје технике „дерандомизације“, које могу да претворе алгоритам који је брз за просечне случајеве у потпуно детерминистички алгоритам. Понекад је допунски трошак дерандомизације толико велик, да су потребни веома велики скупови података да би се добили било какви добици. Упркос томе, дерандомизација сама по себи има теоријску вредност. Рандомизовани алгоритам find је изумео британски научник Сер Чарлс Ентони Ричард Хор. Иако је Хор важна фигура у рачунарској науци, оно по чему је највише познат у ширим круговима је алгоритам за брзо сортирање (quicksort algorithm) о коме ћемо расправљати у следећем одељку.

Брзо сортирање

Алгоритам за проналажење средње вредности партиционисањем, који је описан у претходном одељку, је, уствари, врло близу имплементације алгоритма сортирања у пуном опсегу. Изградњу алгоритма за брзо сотирање остављамо читаоцу да уради као вежбу и препоручујемо да то учини пре читања следећег одељка (брзо сортирање је „брутално“ у односу на сортирање спајањем које не користи рандомизацију). Кључни део алгоритма брзог сортирања је избор праве средње вредности. Али да би га брзо направили, почнимо са претпоставком да вектор није сортиран и да је вероватноћа да крајњи десни елемент било ког вектора садржи средњу вредност, иста као и за све остале елементе и да смо потпуно оптимистични у погледу тога да се не дешава да крајње десни елемент има највећи кључ, што би значило да би уклањали само један елемент (елемент партиције) у сваком кораку и не би имали десни вектор за сортирање, већ само леви дужине n-1. Управо због овога је рандомизација важна за брзо сортитрање, т.ј. избор оптималнијег кључа партиције је прилично важно за ефикасан рад брзог сотирања. Упоредите број поређења неопходних за брзо сортирање у односу на сортирање уметањем. Код сортирања уметањем, просечан број поређења потребних за проналажење најмањег првог елемента у узлазном сортирању рандомизованог вектора је n /2 . Просечан број поређења за други елемент је (n-1)/2; за трећи елемент ( n- 2) / 2. Укупан број поређења је [ n + (n - 1) + (n - 2) + (n - 3) .. + (n - [n-1]) ] подељено са 2, што је [ n x n - (n-1)! ] /2, или око O(n на квадрат). У брзом сортирању, број поређења ће бити преполовљен на сваком кораку поделе ако је изабрана истинска средња вредност, пошто партиција леве половине не треба да се пореди са десном, али у сваком кораку, број елемената свих партиција направљених на претходном нивоу партиционисања ће опет бити n. Број нивоа поређења n елемената је број корака дељења n са два, док не буде n = 1. Или уназад, 2 ^ m ~ n, so m = log₂(n) n. Тако је укупан број поређења n (елемената) x m (нивоа скенирања) или n x log2n, Следи да је број поређења O(n x log ₂(n) ), што је мање него код сортирања убацивањем где је тај број O(n^2) или O( n x n ). (Поређењем O(n x log ₂(n)) са O( n x n ), заједнички фактор n може да се елиминише и пореди се log₂(n) у односу на n, што чини експоненцијалну разлику како n расте, на пример упоредите n = 2^16 , или 16 са 32768, или 32 у односу 4 гига.) Да би се имплементирало партиционисање „на месту“ на делу вектора који је одређен претходним рекурзивним позивом, потребно је скенирање са оба краја партиције, замена локација кад год је вредност текуће локације левог скенирања већа од врендости партиције и увек када је вредност текуће локације десног скенирања мања од вредности партиције. Тако је почетни корак:

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

Корак партиционисања је:

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

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

Уверите се у овом тренутку да су после последње замене случајеви два елемента у уређеном и два елемента у неуређеном вектору исправно обрађени, што би требало да значи да су сви случајево коректно обрађени. Ово је добар корак за отклањање евентуалних грешака у алгоритму. За случај два уређена елемента, леви показивач се зауставља на партицији или на другом елементу пошто је пронађена вредност партиције. Десни показивач, скенирајући уназад, почиње од првог елемента пре партиције и зауставља се пошто је у крајње левој позицији. Показивачи се укрштају и излази се из петље пре него што се направи замена у петљи. Ван петље, садржаји левог показивача на крајње десној позицији и показивача партиције, такође на крајње десној позицији, се замењују, чиме се постиже да нема промене у случају два уређена елемента. За случај два неуређена елемента, леви показивач се зауставља на првом елементу, пошто је већи од вредности партиције (вредност добијена левим скенирањем зауставља замену вредности које су веће од вредности партиције). Десни показивач креће и зауставља се на првом елементу, пошто је достигао крајње леви елемент. Из петље се излази зато што су леви и десни показивачи једнаки и показују на прву позицију и садржај на који показује леви показивач (прва позиција) се замењује са вредношћу партиције на крајње десној позицији. Тиме претходно неуређени елементи постају уређени. Још једно питање имплементације је, како померати показиваче за време скенирања. Померање на крају спољне петље делује логично.

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;

Са унарним операторима преинкрементирања / декрементирања, скенирање може да се уради непосредно пре тестирања услова while петље, али то значи да показивачи, на почетку, морају да се помере за -1 однодно +1 респективно, тако да сада алгоритам изгледа овако:

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;
}

и алгоритам за qsort је

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

}

и коначно, рандомизација елемента партиције.

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);
}

Ово може бити позвано непосредно пре позива финкције partition у qsort().

Мешање (елемената) вектора

  Ово одржава податак у током мешања
  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

Хеш табеле

Хеширање се ослања на функцију hashcode која обезбеђује случајно и равномерно распоређивање кључева за расположиве слотове. У Јави се то ради прилично директним методом сабирања простог броја средње величине (31 * 17) са целобројним кључем по модулу величине хеш табеле. За кључеве типа низа симбола, почетна вредност хеш броја се добија сабирањем резултата множења редног броја сваког симбола са 31. Вики књига Структуре података у поглављу Хеш табеле добро покрива ову тему.

Скип листе

Речник или мапа, је општи концепт у коме се вредност убацује под неким кључем и налази на основу тог кључа. На пример, у неким језицима концепт речника је уграђен у сам језик (Python) док је у другим он део основних библиотека (C++ стандардна библиотека шаблона и Јава стандардна библиотека колекција). Језици који реализују концет речника у оквиру библиотека, обично пружају могућност програмеру да изабере између хеш алгоритма и имплементације засноване на уравнотеженом бинарном стаблу (црвено-црна стабла). Недавно су понуђене скип листе (листе са прескакањем) које пружају велике предности приликом имплементација у оквиру апликација у конкурентном окружењу са више нити извршења. Хешовање је техника која зависи од случајности кључева који се пропуштају кроз хеш функцију да би се нашла вредност која одговара индексу линеарне табеле.

Хешовање ради онолико брзо колико и хеш функција, али ради добро само ако су убачени кључеви ревномерно распоређени у вектору, као и било који кључеви који се хеширају на исти индекс. Мора да постоји договор око проблема хеш судара, на пример чување уланчане листе судара за сваки слот табеле и итерација кроз листу да би се упоредио пуни кључ за сваки пар кључ-вредност у односу на кључ претраживања. Недостатак хешовања је у томе што симетрични (in-order) обилазак није могућ са оваквом структуром података. Бинарна стабла могу да се користе за представљање речника, а симетрични обилазак бинарног стабла је могућ рекурзивном посетом чворова (посета левог детета, посета корену и посета десног детета). Бинарна стабла се лоше претражују када су „неуравнотежена“, нпр. кључеви парова кључ-вредност су уметнути по растућем или по опадајућем редоследу, тако да ефективно изгледају као уланчане листе без леве деце, само са десном децом. Самоуравнотежујућа (self-balancing) бинарна стабла могу да се направе пробабилистички (користећи случајност) или детерминистички (бојењем веза са децом у црвено или црно), преко операција ротације локалних стабала са три чвора. Ротација је једноставно замена чвора родитеља са чвором дететом, али уз очување поретка. На пример, за ротацију левог детета, његово десно дете постаје лево дете родитеља, а родитељ постаје његово десно дете.

Црвено-црна стабла могу лакше да се разумеју ако се испита одговарајуће 2-3-4 стабло. 2-3-4 стабло може да има 2-је, 3-је или 4-оро деце, с тим да чворови са 3-је деце имају 2 кључа између 3 детета и чварови са 4-оро деце (4-чворови) имају 3 кључа између 4 детета. 4-чворови могу да се поделе на 3 2-чвора са једним кључем и средњи 2-чвор додаје навише да би се спојио са чвором родитеља који, ако je био 2-чвор са једним кључем постаје 3-чвор са два кључа, или ако је био 3-чвор са два кључа постаје 4-чвор, који ће касније бити подељен (на путу навише). Чин поделе 4-чвора са три кључа је уствари операција поновног уравнотежавања која спречава да се низ од 3 чвора: пра-родитељ (деда), родитељ и дете, појављују без уравнотежујуће ротације. 2-3-4 стабла су ограничен пример B-стабала, који обично имају довољно чворова да се сместе у оквиру једног физичког блока на диску и да олакшају кеширање веома великих индекса који не могу да стану у оперативну меморију RAM (данас је то мање битно).

Црвено-црно стабло је бинарна представа 2-3-4 стабла, где су 3-чворови моделирани помоћу родитеља са једним црвеним дететом, а 4-чворови помоћу родитеља са 2 црвена детета. Цепање 4-чвора је представљено родитељем са 2 црвена детета и преобраћањем (flipping) црвене деце у црну, а самог себе у црвено. Не постоји случај у коме је родитељ већ црвен, зато што се извршавају операције уравнотежавања код којих, ако постоји пра-родитељ са црвеним дететом (родитељем) које има црвено дете, пра-родитељ се ротира тако да постаје дете родитеља (свог детета) и родитељ постаје црн, а пра-родитељ постаје црвен; ово обједињује претходни сценарио преобраћања (flipping) једног 4-чвора представљеног са 2 црвена детета. Заправо, можда ова стандардизација 4-чворова са обавезном ротацијом искривљених или цик-цак 4-чворова, доводи до поновног уравнотежења бинарног стабла. Новија оптимизација је да се улево ротира било које десно црвено и лево црвено дете, тако да само десна ротација левих искривљења у оквиру 4-чворова (3 црвена чвора) може икада да је појави, чиме се поједностављајући код за поновно уравнотежавање.

Скип листе су моделоване на уснову једноструко уланчаних листа, осим што су чворови вишенивоски. Чворови вишег нивоа (високи чворови) су ређи, али операција уметања обезбеђује повезаност чворова на сваком нивоу. Имплементација скип листа захтева стварање насумично високих вишенивоских чворова и затим њихово уметање. Чворови се стварају итерацијом случајне функције, у којој се чворови вишег нивоа појављују у каснијим итерацијама и ређи су, зато што је итерацијама већ пређен велики број прагова случајности (на пример 0,5, ако је случајни број између 0 и 1). Уметање захтева привремени вектор претходног чвора нивоа генерисаног чвора за уметање. Он се користи за чување последњег показивача за задати ниво, који има кључ мањи од кључа уметања. Скенирање почиње од почетка скип листе, на највишем нивоу и наставља се док се не нађе чвор чији је кључ већи од кључа уметања и док се претходни показивач не сачува у привремени вектор претходног чвора. Тада се прелази на следећи, нижи, ниво који се скенира и тако даље, идући у цик-цак, док се не достигне најнижи ниво. Уметање се врши на сваком нивоу привременог вектора претходног чвора, тако да наредни чвор претходног чвора на сваком нивоу постаје наредни чвор за уметнути чвор, а уметнути чвор постаје наредни за претходни чвор. Претраживање подразумева итерације од највишег до најнижег нивоа почетног чвора и скенирање дуж листе на сваком нивоу док се не пронађе чвор чија је вредност већа од траженог кључа, померајући се наниже на следећи ниво и настављајући скенирање док се не пронађе чвор са већим кључем од траженог на најнижем нивоу, или се пронађе тражени кључ. Стварање чворова случајне висине који су мање учестали када су на вишем нивоу и процес повезивања са другим чворовима на сваком нивоу, је оно што чини скип листу корисном структуром.

метода за имплементацију скип листе: имплементирајте једноструко уланчану листу, тестирајте, затим је трансформишите у скип листу, онда поново тестирајте и упоредите перформансе

Оно што следи је имплементација скип листи у језику Python. Прво је имплементирана једноструко уланчана листа која на следећи чвор увек гледа као на текући, а затим следи имплементација скип листе уз минималне модификације и, на крају, поређење које помаже да се разјасни имплементација.

#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

Улога случајности

Идеја да се чворови вишег нивоа праве случајно са геометријски мањом вероватноћом, значи да на вишим нивоима постоји мањи број кључева које треба поредити, a пошто су чворови случајно изабрани, требало би да будемо поштеђени проблема дегенерисаних улаза који у алгоритмима стабла захтевају да се оно уравнотежава. Пошто листе вишег нивоа имају шире раздвојене елементе, а алгоритам претраживања се премешта на нижи ниво сваки пут када заврши са текућем нивоу, виши ниво помаже да се „прескоче“ претраживања ранијих елемената у листама нижег нивоа. Пошто има више нивоа прескакања, постаје мање вероватно да оскудан прескок на вишем нивоу неће бити компензован са бољим прескоцима на нижим нивоима. Пју (Pugh) тврди да су опште перформансе алгоритма претраживања скип листе O(logN). Концептуално, да је лакше разумети скип листе од уравнотежавања стабала и стога их лакше имплементирати? Развој идеја бинарних стабала, уравнотежених бинарних стабала, 2-3 стабала, црвено-црних стабала и B-стабала, дају чвршћу концептуалну основу, али и спорост у развоју, тако да вероватно, једном када се разумеју црвено-црна стабла она поседују више концептуалног контекста који може да помогне или освежи памћење.

примена конкурентног приступа

Сем употребе рандомизације ради унапређења основних структура података као што је уланчана листа, скип листа може да се прошири као глобална структура података која се користи у вишепроцесорким применама. Види допунску тему на крају поглавља.

Идеја за вежбу

Замени сасвим солидан распоређивач (диспечер) Linux-а заснован на имплементацији црвено-црног стабла са скип листом и види како твоја врста Linux-а ради после рекомпилације.

Декартова стабла

Декартово стабло је бинарно стабло са два кључа, које користи други, случајно генерисани кључ и претходно размотрене операције ротације родитељ-дете, да насумично ротира стабло, тако да је оно на крају постане уравнотежено. Сетимо се да бинарна стабла раде тако што садрже све чворове мање од задатог у левом подстаблу, а све веће у десном. Сетимо се, такође, да ротација чворова не нарушава овај поредак (неки ово зову инваријантност рорације) али мења однос родитеља и детета, тако што, ако је родитељ био мањи од десног детета, онда родитељ постаје лево дете свог, претходно десног детета. Идеја хип стабла или Декартовог стабла је да се бинарна хип релација одржава између родитеља и деце и да чвор родитеља има већи приоритет од чворова своје деце, што није исто као и леви и десни поредак кључева код бинарног стабла. Стога новоуметнути чвор листа у бинарно стабло, за који се деси да има високи случајни приоритет, може да буде ротиран тако да буде на релативно вишој позицији у стаблу и да при томе нема родитеља са нижим приоритетом. Декартово стабло је алтернатива и црвено-црним стаблима и скип листама, као самоуравнотежујућа, сортирана структура података.

пример имплементације Декартовог стабла у Јави

// 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));
	}
}

Поређење Декартових и раширених стабала

Раширена стабла су слична Декартовим у томе што се користи ротација да се чвор већег приоритета доведе на врх без да се при томе мења основни редослед кључева, осим што уместо употребе случајног кључа за приоритет, ротира се последњи чвор коме се приступило у корен стабла, тако да ће се чворови којима се чешће приступа налазити близу врха. То значи да ће у Декартовм стаблима уметнути чворови ротирати највише до приоритета који им одређује случајни кључ приоритета, док код раширених стабала, уметнути чвор ротира до корена, и свако претраживање у раширеном стаблу ће резлтирати у поновном уравнотежавању, што није случај код Декартовог стабла.

Дерандомизација

Вежбе

1. Напишите функцију find-min и извршите је са више различити улаза да би показали њену исправност.

Допунска тема: скип листе и вишепроцесорски алгоритми

Вишепроцесорски хардвер обезбеђује атомичке операције CAS (упореди и постави) или CMPEXCHG (упореди и размени) (intel manual 253666.pdf, стр. 3-188), где се очекивана вредност пуни у акумулатор, чији се садржај пореди са садржајем циљне меморијске локације и, ако су исти, садржај изворне меморијске локације се пуни у циљну меморијску локацију и подиже се (сигнална) заставица нуле (zero flag set), у супротном, ако су различити, садржај циљне меморијске локације се враћа у акумулатор и заставица нуле се спушта (zero flag unset), означавајући да је, на пример, дошло до покушаја истовремног закључавања. У intel архитектури инструкција LOCK се издаје пре CMPEXCHG, која за следећу инскрукцију, или закључава кеш за конкурентне приступе ако је меморијска локација кеширана, или закључава локацију заједничке меморије ако локација није у кешу. CMPEXCHG може да се користи за имплементацију закључавања од којих су спинлокови најједноставнији (нпр. непрестани покушаји, док се заставица нуле не подигне). Приступ без закључавања повећава ефикасност, тако што се избегава чекања на закључавање. Стандардна библиотека језика Јава има имплементацију неблокирајућих конкурентних скип листа, засновану на раду под називом "Прагматична имплементација неблокирајућих једноструко уланчаних листа“ Имплементација за скип листе је проширење имплементације за једноструко уланчане листе без закључавања. Опис следи:

Операција insert је: X -> Y уметни N , N -> Y, X -> N и очекивани резултат је X -> N -> Y. Утркивање (race condition) је ако се M умеће између X и Y и убацивање M се прво завршава, а затим се завршава уметање N, тако да се добија следећа ситуација X -> N -> Y <- M. M није у листи. Операција CAS избегава ово, зато што се пре ажурирања X ->, прво проверава копија -> Y у односу на тренутну вредност X ->. Ако N успе први да ажурира X -> онда, када M покуша да ажурира X ->, копија X -> Y, која се прави пре M -> Y, не одговара X -> N, тако да CAS враћа подигнуту заставицу не-нула (non-zero flag set). Процес који је пробао да уметне M, може поново да покуша уметање после X, али сада CAS проверава да ли је ->N следећи показивач на X, тако да је после поновљеног покушаја X->M->N->Y и ниједно уметање није изгубљено. Ако M прво ажурира X->, копија X->Y која се прави пре уметања N, не одговара X -> M, тако да ће CAS и овде бити неуспешан и горе поменути поновни покушај уметања N имаће као резултат X ->N -> M -> Y. Операција delete зависи од посебног „логичког“ корака брисања, пре „физичког“ брисања. „Логичко“ брисање подразумева да CAS изврши претварање показивача на следећи чвор у „обележени“ показивач. Имплементација у Јави замењује ово са атомичким уметањем обележеног заступајућег (proxy) чвора испред следећег чвора. Ове спречава будућа уметања после чвора који има „обележен“ показивач на следећи и тиме чини да је потоњи чвор „логички“ избрисан. Операција insert се ослања на другу функцију search која приликом позива враћа 2 unmarked, показивача чвора: први који показује на чвор чији је показивач на следећи једнак другом. Први чвор је чвор пре места уметања.

Операција insert CAS-а обезбеђује да текући показивач првог чвора на следећи одговара необележеној референци на други, тако да ће бити „логички“ неиспешна ако показивач на следећи првог чвора постане обележен после позива функције search, зато што је први чвор истовремено логички избрисан. Ово задовољава захтев да се спречи појава истовременог уметања, пошто је чвор већ обрисан. Ако је операција уметања у CAS-у неуспешна због показивача на следећи претходног чвора, тражење места уметања поново почиње од почетка целе листе, пошто нови необележени претходни чвор мора да се пронађе, а не постоји показивач на претходни пошто је листа једноструко уланчана.

Операција delete изложена горе, такође се ослања на операцију search која враћа два необележена чвора, а две CAS операције брисања: једна за логичко брисање или обележавање показивача на следећи другог показивача и друга за физичко брисање тако што чини да показивач на следећи првог чвора показује исто што и необележени показивач на следећи другог чвора. Прва CAS операција брисања се дешава само после провере да ли је копија оригиналног показивача на следећи другог чвора необележена и обезбеђује да успе само једно конкурентно брисање, које чита текући показивач на следећи другог чвора који је исто тако необележен. Друга CAS операција утврђује да претходни чвор није логички обрисан, пошто његов показивач на следећи није исти као необележени показивач на текући други чвор, који враћа функција search, тако да се само активни показивач на следећи претходног чвора „физички“ ажурира према копији оригиналног, необележеног показивача на следећи чвора који се брише (чији је показивач на следећи већ обележен у првом CAS-у). Ако други CAS не успе, онда је претходни чвор логички обрисан, а његов показивач на следећи је обележен, исто као и показивач на следећи текућег чвора. Позив функције search, поново све доводи у ред, пошто настојећи да нађе кључ текућег чвора и да врати суседне необележене показиваче на претходни и текући чвор и док то ради скраћује низове логички обрисаних чворова.

Питања програмирања без закључавања

Исцрпљивање је могуће када неуспешна уметања морају да се понављају од почетка листе. Без чекања (wait-freedom) је концепт у коме алгоритам има све нити извршења заштићене од исцрпљивања. Код ABA проблема, где сакупљач смећа (garbage collector) рециклира показивач A, али се адреса пуни на различите начине и показивач се поновно додаје у тачки где се врши провера А од стране друге нити извршења која чита А и извршава CAS да утврди да се А није променио; Адреса је иста и није обележена, али је садржај А промењен.