Список с пропусками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Увеличены дроби)
(Исправлено определение, добавлено описание и картиночки.)
Строка 1: Строка 1:
'''Список с пропусками''' (''skip-list'') — одна из вероятностных структур данных, на ряде параллельных отсортированных связных списков с эффективностью, сравнимой с бинарными деревьями поиска. Все операции со списком с пропусками осуществляются за <tex>O(\log{n})</tex> с большой вероятностью.
+
'''Список с пропусками''' (''skip-list'') — вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.
  
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.  
+
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до <tex>\Theta(\log(n))</tex>.
 +
 
 +
==Описание==
 +
Список с пропусками строится на основе существующего односвязного отсортированного списка.
 +
 
 +
[[Файл:SimpleList.png]]
 +
 
 +
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>.
 +
 
 +
[[Файл:SkipList.png]]
  
 
==Операции над структурой==
 
==Операции над структурой==
Строка 11: Строка 20:
 
# Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу
 
# Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу
 
# Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex>   
 
# Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex>   
 +
 +
Пример поиска числа 8 в списке из описания:
 +
 +
[[Файл:SkipListSearch.png]]
  
 
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
 
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
Строка 114: Строка 127:
 
*[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)]
 
*[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)]
 
*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками]
 
*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками]
 +
*[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating]

Версия 04:08, 16 июня 2014

Список с пропусками (skip-list) — вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.

Отсортированный связный список является простейшей структурой с временем поиска [math]\Theta(n)[/math]. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до [math]\Theta(\log(n))[/math].

Описание

Список с пропусками строится на основе существующего односвязного отсортированного списка.

SimpleList.png

Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять [math]\Theta(\log(n))[/math].

SkipList.png

Операции над структурой

Поиск элемента

Допустим, что в нашем списке с пропусками существуют два уровня: [math]L_1[/math], в котором содержатся все элементы и [math]L_2[/math], в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.

В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:

  1. Начинаем поиск элемента в верхнем левом углу
  2. Передвигаться будем по списку [math]L_2[/math], пока значение в следующей ячейке меньше или равно ключу
  3. Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку [math]L_1[/math]

Пример поиска числа 8 в списке из описания:

SkipListSearch.png

Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне [math]L_2[/math]. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:

[math] \approx \vert L_2\vert + \dfrac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \dfrac{n}{\vert L_2\vert }[/math]

Минимизируя, мы получаем, что [math]\vert L_2 \vert ^ 2 = n[/math]

В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:

[math] \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}[/math]

Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:

  • Для трех уровней: [math] 3 \sqrt[3]{n}[/math]
  • Для четырех уровней: [math] 4 \sqrt[4]{n}[/math]
  • Для пяти уровней: [math] 5 \sqrt[5]{n}[/math]
  • Для [math]\log{n}[/math] уровней: [math] \log{n} \times \sqrt[\log{n}]{n} = n ^ {\frac{1}{log{n}}} \log{n} = n ^ {\log_n{2}} \log{n} = 2\log{n}[/math]

В списках с пропусками, в которых содержится [math]\log{n}[/math] уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в [math]\log{n}[/math] списке с пропусками будет осуществляться за асимптотическое время [math]O(\log{n})[/math].

Вставка элемента

Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:

  1. Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
  2. Вставить наш элемент в нижний уровень списка с пропусками
  3. «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
  4. Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат

Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется [math]\dfrac{n}{2}[/math], на третьем уровне [math]\dfrac{n}{4}[/math] и т.д. На уровне [math]\log{n}[/math] у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это [math]\dfrac{1}{2}[/math], на третий [math]\dfrac{1}{4}[/math] и т.д. Вероятность попасть на уровень [math]\log{n}[/math] равна [math]\dfrac{1}{n}[/math]

Удаление элемента

Алгоритм удаления достаточно тривиален.

  1. Найти удаляемый элемент
  2. Удалить его со всех уровней

Псевдокод

 const float P = 0.5
 
 int random_level()
     int lvl = (int)(log(frand())/log(1.-P))
     if lvl < MAX_LEVEL
          return lvl
     return MAX_LEVEL  
 
 boolean Find (int key)
     SkipNode x = header
     for i = level to 0
       while x.forward[i] != NULL and x.forward[i].value < key
           x = x.forward[i]
   x = x.forward[0]
     return x != NULL && x.value == key
   
   
   
 
 void Insert(int value) 
     SkipNode x = header
     SkipNode update
     update.assign(MAX_LEVEL + 1, 0)
   
     for i = level to 0
       while x.forward[i] != NULL and x.forward[i].value < value
           x = x.forward[i]
       update[i] = x
     x = x.forward[0]
     if x == NULL or x.value != value        
         int lvl = random_level()
         if lvl > level
           for i = level + 1 to lvl
               update[i] = header
           level = lvl
         x = new SkipNode(lvl, value)
       for i = 0 to lvl
           x.forward[i] = update[i].forward[i]
           update[i].forward[i] = x
           
           
 void Erase(int value)
     SkipNode x = header
     SkipNode update
   update.assign(MAX_LEVEL + 1, 0)
     for i = level to 0
       while x.forward[i] != NULL and x.forward[i].value < value
           x = x.forward[i]
       update[i] = x
   x = x.forward[0]
     if x.value == value
         for i = 0 to level
           if update[i].forward[i] != x
               break
           update[i].forward[i] = x.forward[i];
         delete x
         while level > 0 or header.forward[level] == NULL
           level--


Ссылки