Изменения

'''Список [[Файл:Skip list example.png|thumb|550px|Пример списка с пропусками''' (''skip-list'') — вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.]]

Отсортированный связный список является простейшей структурой '''Список с временем поиска <tex>\Thetaпропусками''' (nангл. ''skip list'')</tex>. Добавление дополнительных уровней— вероятностная структура данных, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до позволяющая в среднем за <tex>\ThetaO(\log(n))</tex>времени выполнять операции добавления, удаления и поиска элементов.

==Описание==Список с пропусками строится состоит из нескольких уровней, на основе существующего односвязного отсортированного спискакаждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть — на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях, номера которых меньше <tex>i</tex>.

==Построение==[[Файл:SimpleList.png|thumb|600px|Односвязный отсортированный список]]

Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов[[Файл:SkipList.png|thumb|600px|Получившийся список с пропусками]]Допустим, что нам задан односвязный отсортированный список и мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям хотим построить на его основе список с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственнопропусками, асимптотика этих операций будет составлять позволяющий в среднем за <tex>\ThetaO(\log({n)})</tex>времени выполнять операции добавления, удаления и поиска элементов.

[[ФайлНа самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни. ====Псевдокод==== Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head} \ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне. Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:* <tex>\mathtt{next}</tex> — ссылка на следующий элемент списка на данном уровне* <tex>\mathtt{key}</tex> — ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже  '''struct''' node: '''node''' next, down '''K''' key Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>,  Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.  '''list''' build_lvl('''list''' lvl) '''list''' next_lvl next_lvl.head.down = lvl.head next_lvl.tail.down = lvl.tail '''node''' i = lvl.head.next.next '''node''' cur = next_lvl.head '''while''' i <tex>\neq</tex> ''null'' '''and''' i.next <tex>\neq</tex> ''null'' cur.next = node(key, i, cur.next) <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key, ссылками down на нижний и next на следующий элемент</font> cur = cur.next i = i.next.next <font color=darkgreen>// Переход к следующему чётному элементу</font> '''return''' next_lvl  Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.  '''list''' skip_list('''list''' l):SkipList '''list''' lvl <font color=darkgreen>// Построение первого уровня</font> '''node''' i = l.head '''node''' j = lvl.head '''while''' j <tex>\neq</tex> l.tail i.next = node(j.key, ''null'', j.next) i = i.next j = j.next '''while''' lvl.png]]size > 2 lvl = build_lvl(lvl) '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

Допустим, что Алгоритм поиска элемента в нашем списке с пропусками существуют два уровнясостоит из следующих операций: # Начинаем поиск элемента в самом верхнем уровне# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше# Переместимся на один уровень вниз и перейти к шагу <tex>L_12</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне. Если в котором содержатся все элементы и качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет <tex>L_2k</tex>уровней, тогда на каждом уровне в среднем будет в котором присутствует только часть из них<tex>n^{1/k}</tex> раз элементов больше, чем уровнем выше. Между одинаковыми элементами этих двух списков существуют ссылкиВ таком случае время поиска элемента <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.

Пример поиска числа 8 Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке из описания:с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками. '''T''' find('''node''' res, '''K''' key) '''while''' res.key < key res = res.next '''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> '''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> '''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>

Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex> find(skip. Представимhead, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:key)

===Вставка элемента===Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:# Начинаем вставку на самом верхнем уровне# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex> \approx \vert L_2\vert + \dfrac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \dfrac{n}{\vert L_2\vert }2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.

МинимизируяОтдельно стоит обработать случай, мы получаемкогда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что <tex>\vert L_2 \vert ^ 2 = n</tex>вставка каждого нового элемента увеличивает число уровней не более чем на один.

В итоге время Заметим, что вставка элемента <tex>-</tex> поиск элемента и за которое мы найдем <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент в списке с пропусками с двумя уровнями будет равняться:. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.

====Псевдокод====Функция <tex> \sqrtmathtt{ninsert} + \dfrac{n}{\sqrt{n}} = 2 </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\sqrtmathtt{nres}</tex>, или ''null'', если на монете выпала «Решка».

Делая аналогичные подсчеты для списков с пропусками '''node''' insert('''node''' res, в которых содержится больше уровней, получаем:'''K''' key)* Для трех уровней: '''while''' res.next <tex> 3 \sqrt[3]{n}neq</tex>''null'' '''and''' res.next.key < key* Для четырех уровней: <tex> 4 \sqrt[4]{n}</tex> res = res.next * Для пяти уровней: <tex> 5 \sqrt[5]{n}</tex> '''node''' down_node* Для <tex>\log{n}</tex> уровней: <tex> \log{n} \times \sqrt[\log{n}]{n} '''if''' res.down = n ^ {\frac{1}{log{n}}} \log{n} = n ^ {\log_n{2}} \log{n} ''null'' down_node = 2\log{n}</tex>''null'' '''else'''В списках с пропусками down_node = insert(res.down, в которых содержится key) '''if''' down_node <tex>\log{n}neq</tex> уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска''null'' '''or''' res. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в down = ''null'' <texfont color=darkgreen>\log{n}// Если выпал «Орёл» или мы находимся на первом уровне</texfont> списке с пропусками будет осуществляться за асимптотическое время res.next = node(key, down_node, res.next) '''if''' coin_flip() = ''head'' <texfont color=darkgreen>O(\log{n})// Если выпал «Орёл»</texfont> '''return''' res.next '''return''' ''null'' '''return''' ''null''

===Вставка элемента===Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:# Найти с помощью алгоритма поиска позициютого, куда нам надо чтобы вставить этот элемент# Вставить наш элемент с ключом <tex>\mathtt{key}</tex> в нижний уровень списка список с пропусками# «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше# Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат<tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию

Таким образом '''function''' insert_element('''list''' skip, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>'''K''' key) '''node''' res = insert(skip.head, на третьем уровне key) '''if''' res <tex>\dfrac{n}{4}neq</tex> и т''null'' '''list''' lvl lvl.дhead. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>next = node(key, res, на третий <tex>\dfrac{1}{4}</tex> и т.дlvl. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>tail) skip = lvl

Алгоритм удаления достаточно тривиален. элемента выглядит следующим образом:# Найти удаляемый Начинаем удалять элементс верхнего уровня# Переходим к следующему элементу, пока значение следующего элемента меньше ключа# Удалить Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.====Псевдокод====Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.  '''function''' delete('''node''' res, '''K''' key) '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key res = res.next '''if''' res.down <tex>\neq</tex> ''null'' delete(res.down, key) '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key res.next = res.next.next

Для того, чтобы удалить элемент <codetex> const float P = 0.5 int random_level() int lvl = (int)(log(frand())\mathtt{key}</log(1.-P)) if lvl tex> из списка с пропусками < 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 tex>\mathtt{skip}< 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/tex>, 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 tex> 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 \mathtt{delete} \ < 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 /tex> 0 or header.forward[level] == NULL level--следующим образом:

==Использование нечестной монеты==Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{1/p} {n} \right)</tex> <tex>(</tex>на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{1/p} {n}</tex><tex>)</codetex>.

Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>\left\{ p, q \right\}</tex>, при котором функция <tex>\dfrac{1}{x} \log_{1/x} {n}</tex> принимает минимальное значение. Производная этой функции равна <tex>-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}</tex>. При <tex>x = \dfrac{1}{e}</tex> производная равна нулю, вторая производная в точке <tex>x_0 = \dfrac{1}{e}</tex> больше <tex>0</tex>, значит <tex>x_0</tex> <tex>-</tex> точка минимума. Значит при распределении <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением <tex>\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}</tex> почти невозможно, поэтому на практике лучше всего использовать честную монету. Для крайних распределений:* <tex>\{0, 1\}</tex> — <tex>O(n)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.* <tex>\{1, 0\}</tex> — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>. ==СсылкиПрименение== Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Проще реализовать, чем сбалансированные деревья или хеш-таблицы* Следующий элемент достаётся за <tex>O(1)</tex> (при условии, что у нас есть ссылка не текущий)*Легко модифицировать под различные задачи ===Нахождение всех отрезков, покрывающих данную точку=== {{Задача|definition = Пусть у нас есть запросы двух видов:# Добавить отрезок <tex>[L, R]</tex># Для заданной точки <tex>x</tex> вычислить количество отрезков, которые её покрывают. Необходимо для каждого запроса второго типа вывести ответ.}} Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</tex> в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие <tex>l</tex> и <tex>r</tex>, что значение <tex>l</tex> меньше <tex>L</tex>, а значение следующего за <tex>l</tex> элемента уже не меньше <tex>L</tex>. Аналогично ищем такое же <tex>r</tex>, только относительно <tex>R</tex>. Если значения <tex>l.next</tex> и <tex>r</tex> лежат полностью внутри отрезка <tex>[L, R]</tex>, то к самому отрезку <tex>[l.next, r]</tex> прибавляем <tex>1</tex>, а сам отрезок <tex>[L, R]</tex> разбиваем на три <tex>[L, l.next.key - 1]</tex>, <tex>[l.next.key, r.key]</tex> и <tex>[r.key + 1, R]</tex> и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[http:L, R]</tex> на <tex>3</habrahabrtex> части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна <tex>l.next.rukey</posttex> или <tex>r.key</111913tex>. Итого время обработки запроса <tex>O(\log{n})</ Хабрахабр — Списки tex>. Для запросов второго типа мы снова будем спускать с пропускамиверхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>. ==См. также==*[[Список]]*[[Рандомизированное бинарное дерево поиска]]*[[Поисковые структуры данных]]*[[Skip quadtree: определение, время работы|Skip quadtree]] ==Источники информации==*[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)]*[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)]*[http://bit.ly/LiNe8M Курс kiev-clrs Wikipedia — Списки с пропускамиskip list]