Википедија:Семинарски радови/Скип листа

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

Скип листа[уреди]

Скип листа је пробабилистичка структура података, базирана на паралелним повезаним листама. Представљају алтернативу балансираним стаблима. Иако скип листе имају лоше перформансе за одабир најгорег случаја, ниједан улазни низ не производи коензистентно најлошије перформансе.

Опис[уреди]

Скип листа се гради по нивоима. На 0-том нивоу имамо обичну повезану листу. Сваки виши ниво понаша се као "експрес линија" за листе на нижем нивоу, где се елемент на нивоу i појављује на нивоу i+1 са неком фиксном вероватноћом p (најчешће коришћене вредности за p су 1/2 или 1/4). У просеку се сваки елемент појављује у 1/(1-p) листи, и највиши елемент (обично глава листе) \log_{1/p}n

Претрага листе почиње од главе листе и са највишег нивоа и наставља се хоризонтално показивачима док год тренутни елемент листе не постане већи или једнак од траженог, уколико је тренутни елемент листе једнак траженом завршили смо претрагу. Ако је тренутни елемент већи од траженог, или претрага стигне до краја листе, враћамо се на претходни елемент и спуштамо се на следећи нижи ниво листе. Просечан број корака је О(logn).

Имплементација[уреди]

Скип листа је структура која садржи хијерархију уређених једноструко повезаних листи. Постоје два облика скип листе: регуларна и ирегуларна.

Регуларна скип листа је она у којој одабрани посдкупови генеришу парно раздовјене прескоке, тј. на 0-том нивоу имамо обичну уређену повезану скип листу на 1-ом нивоу имамо показиваче на сваки други елемент листе, на 2-ом имамо показиваче на сваки четврти елемент листе, на 3-ем на сваки осми елемент листе, и тако даље.
Ирегуларна скип листа је она у којој одабрани посдкупови не генеришу парно раздвојене прескоке.

По конвенцији, кажемо да сваки чвор припада нивоу к-1 уколико има к показивaча. скип листа

Уметање елемената у скип листу[уреди]

У идеалној скип листи би било:

  • 1/2 чворова је на 0-том нивоу, 1/4 чворова је на 1-вом нивоу, 1/8 на другом итд.
  • чворови на 0-том нивоу показују на следећи чвор; чворови на 1-вом нивоу показују на следећи и сваки други чвор;

чворови на 2-гом нивоу показују на следећи, на сваки други и на сваки четврти чвор; итд

  • ниво чвора директно следи на основу његове позиције у скип листи


Ми ћемо редуковати цену уметања на следећи начин:

  • бирањем случајног нивоа за нови чвор, са одговарајућом вероватноћом за ниво 0, па за ниво 1, итд.
  • чвор 0-тог нивоа показује на следећи
  • чвор 1-вог нивоа показује на следећи који припада 1-вом нивоу; чвор 2-гог нивоа показује на следећи који припада другом нивоу итд.

Први корак је пронаћи чвор у листи са највећом вредношћу која је мања или једнака од нове вредности (вредност чвора који се уноси). Нови чвор постаће следбеник овом чвору. Одређивање нивоа чвора врши се генератором случајних бројева (бацање новчића). Нпр. уколико падне глава повећавамо ниво и бацамо поново новчић, уколико падне писмо стајемо. Сада када смо нашли ниво и место потребно је модификовати неке показиваче. уметање

Током претраге морамо запамтити чворове који садрже показиваче који следе пре уноса новог чвора. За ово нам је потребан помоћни низ са n+1 показивача, где је n максималан број нивоа између чворова.

У току претраге сваки пут када се спустимо за један ниво памтимо чвор у ком се тај спуст десио и памтимо претходни чвор. уметање чвора

Преусмеравање показивача приликом уметања:

Уметање у скип листу

Бирање нивоа чвора[уреди]

Постоје разни начини за генерисање нивоа, ево једног врло једноставног:

int randomLevel() 
{
      int Level;
      for(Level = 0; rand() % 2 == 0; Level++);
 
      return Level;
}

Алгоритам претраге скип листе[уреди]

Node* x := &HeadNode;
int i;
for (i = MaximumLevel; i>=0 ;i--) 
{
 //go as far as possible on current level
while (x->forward[i]->keyField < searchKey) 
    x = x->forward[i];
// drop to previous level (via for loop)
}
x = x->forward[0];  // step to next Node
if (x->keyField == searchKey)
      return x->Data;
else
     return failure;

Сложеност О(log n).

Брисање елемента из скип листе[уреди]

Како је брисање супротна операција уметању, користићемо сличне принципе:

  1. Наћи елемент који треба обрисати (ако постоји)
  2. Ажурирати показиваче
  3. Обрисати тражени чвор
  4. Уколико је потребно, редуковати број нивоа у листи

Рецимо да хоћемо да уклонимо чвор 10 :

Брисање

Прво, морамо наћи претходника и да идентификујемо чворове чији ће се показивачи ресетовати. Брисање елемента

Вршимо преусмеравање показивача и деалоцирамо чвор који желимо да обришемо. Сложеност брисања је О(log n).

Примене[уреди]

Листа апликација које користе скип листе:

  • Cyrus IMAP server нуди skiplist бекенд ДБ имплементацију (source file)
  • Lucene користи скип листу да претражи делта-кодиране листе у логаритмаском времену.
  • QMap (up to Qt 4) темеплејт класа Qt која имплментира речник.
  • Redis, ANSI-C open-source постојано кључ/вредност складиште за Posix системе, користи скип листу као имплементацију за уређене скупове.[1]
  • nessDB,веома брза кључ-вредност уграђена машина за складиштење података користи скип листу за своју табелу чланова.
  • skipdb је open-source формат базе који користи уређене кључ-вредност парове.
  • ConcurrentSkipListSet и ConcurrentSkipListMap у Java 1.6 API.
  • leveldb, брза кључ-вредност библиотека написана у Google-у која омогућава уређено мапирање стринг kључева у стринг вредности.

Види још[уреди]

Референце[уреди]

Спољашње везе[уреди]