Изменения

Перейти к: навигация, поиск

Список с пропусками

2409 байт добавлено, 19:24, 7 июня 2015
Нет описания правки
'''Список с пропусками''' (англ. ''skip-list'') — вероятностная — поисковая структура данных, основанная на нескольких отсортированных односвязных спискахпозволяющая производить операции поиска, добавления и удаления элемента в списке за достаточно малое время.
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до Поиск элемента в списке производится за <tex>\Theta(\log(n))</tex>; добавление и удаление элемета происходит за то же время, что и поиск, однако эти операции могут замедлить поиск в структуре.
Такая производительность достигается за счёт добавления новых уровней. При этом нижним уровнем является исходный список, а каждый следующий уровень - список, содержащий часть элементов предыдущего уровня со ссылками на эти элементы. ==ОписаниеПостроение==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
[[Файл:SimpleList.png]]
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>.
[[Файл:SkipList.png]]
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>L_1k</tex>уровней, в котором содержатся все элементы и при этом первым уровнем (<tex>L_2L_1</tex>, в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки) будет исходный список.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
# Начинаем поиск элемента в верхнем левом углу# Передвигаться будем по списку списке (<tex>L_2L_k</tex>), рассмотрим первый элемент# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу# Переместиться в нижний на один уровень вниз и продолжить аналогичный метод перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска по списку <tex>L_1</tex>
Пример поиска числа 8 в списке из описания:
[[Файл:SkipListSearch.png]]
Рассмотрим время работы для списка с двумя уровнями.
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
Делая аналогичные подсчеты для списков Также можно убедиться, что список с пропусками, в которых содержится больше уровней, получаем:* Для трех уровней: имеющий <tex> 3 \sqrt[3]{n}k</tex>* Для четырех уровней: , будет лучше всего работать с <texdpi=150> 4 \sqrt[4k]{n}</tex>* Для пяти уровней: элементами на уровне; время работы такого списка будет равно <texdpi=150> 5 k \sqrt[5k]{n}</tex>.* Для <tex>\loglog_2{n}</tex> уровней: же время работы составит <texdpi=150> \loglog_2{n} \times cdot \sqrt[\loglog_2{n}]{n} = n ^ {\frac{1}{loglog_2{n}}} \logcdot \log_2{n} = n ^ {\log_n{2}} \logcdot \log_2{n} = 2\log{n}</tex> В списках с пропусками, в которых содержится <tex>\log{n}</tex> уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в <tex>\log{n}</tex> списке с пропусками будет осуществляться за асимптотическое время <tex>O(\loglog_2{n})</tex>.
===Вставка элемента===
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
Используя монетку с распределением отличным от {<tex>\{\dfrac{1}{2}</tex>, <tex>\dfrac{1}{2}\}</tex>}, можно влиять на количество элементов на верхних уровнях (и соответственно. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex>}, математическое ожидание количества элементов на количество уровнейуровне <tex>l</tex> равно <tex dpi=150>n q^l</tex>, каждый уровень будет составлять <tex>q</tex> от предыдущего; время поиска будет равно <tex>O(\dfrac{k}{q} + nq^k)</tex>. Однако как Соответственно при большем количестве проталкиваний элементов на уровень выше, так честной монетке и при меньшем<tex>\log(n)</tex> уровней получаем оценку, количество шагов при поиске элемента возрастаетполученную ранее. При распределении Для крайних распределений:* {<tex>0, 1</tex>} структура превращается в обыкновенный список, при - <tex>O(k+n)</tex>* {<tex>1, 0</tex>} {{---}} в <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex> параллельных списков. В обоих случаях )
===Удаление элемента===
==Псевдокод==
Наглядный, но не очень эффективный по памяти вариант списка с пропусками.
 
В узлах списка хранятся:
* <tex>next</tex> {{---}} следующий узел
* <tex>down</tex> {{---}} тот же узел на следующем уровне
* <tex>data</tex> {{---}} данные типа T
* <tex>key</tex> {{---}} ключ типа K
Конструктор
<code>
const float P = 0.5 int random_level skip_list (list l): int list lvl = build_lvl(int)(log(frand()l); //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 updatelvl.assignsize(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(> 2) if lvl > level for i = level + 1 to lvl update[i] = header level = lvl x = new SkipNodebuild_lvl (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] '''return''' t; delete x while level > 0 or header.forward[level] == NULL level--
list build_lvl (list lvl) // Отсеивание нечётных элементов
list next_lvl;
node i = lvl.head(); // Перебор всех элементов lvl
while ((i != NULL) '''and''' (i != lvl.tail()))
next_lvl.push_back(node(i.key, i)); // Добавление чётного элемента;
i = i.next.next; // он содержит ключ и ссылку на предыдущий уровень
'''return''' next_lvl;
</code>
Поиск элемента по ключу:
<code>
T find (list skip_list, K key)
node res;
'''for''' (res = skip_list.head; res.ref != NULL; res = res.ref) {
// Cпускаемся на шаг вниз, если можем (п. 3)
'''while''' (res.key <= key) // Переходим к следующему элементу (п. 2)
res = res.next();
'''return''' res.data;
</code>
Вставка:
<code>
node insert (node i, K key, T data)
'''while''' (i.key <= key) // Ищем подходящее место
i = i.next();
node tmp = '''NULL'''; // Для записи в поле down
'''if''' i.ref != '''NULL''' // Мы не на нижнем уровне
tmp = insert (i.ref, key); // Рекурсивный вызов на более низком уровне
'''if''' tmp == '''NULL''' // Проверка броска монетки
'''return''' '''NULL''';
i.next = '''new''' node (i.next, tmp, data, key); //Непосредственно вставка
'''if''' random(0,1) > 0.5 // Бросок монетки
return i.next; // Нужно передать новый элемент для вставки выше
'''else'''
return '''NULL''';
void insert (list skip_list, K key, T data) // Обёрточка
insert(skip_list.head, key, data);
</code>
Удаление:
<code>
'''void''' erase (node i, K key)
'''if''' (i == '''NULL''')
'''return''';
'''while''' (i.key <= key) // Ищем элемент
i = i.next();
erase(i.ref, key); // Удаляем с нижних уровней
'''if''' (i.key == key) // Если ключ совпадает
'''delete'''(i); // удаляем и с этого уровня
void erase (list skip_list, K key) // Обёрточка erase(skip_list.head, key);</code>==СсылкиСм. также==*[[Список]]*[[Рандомизированное бинарное дерево поиска]]*[[Поисковые структуры данных]]==Источники информации==
*[http://habrahabr.ru/post/111913/ Хабрахабр — Списки с пропусками]
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D1%81_%D0%BF%D1%80%D0%BE%D0%BF%D1%83%D1%81%D0%BA%D0%B0%D0%BC%D0%B8 Википедия — списоки с пропусками(Ru)]
Анонимный участник

Навигация