Изменения

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

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

4734 байта добавлено, 14:22, 22 апреля 2019
м
Использование нечестной монеты
====Псевдокод====
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <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''
'''list''' skip_list('''list''' l):
'''list''' lvl = build_lvl(l) <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.size > 2
lvl = build_lvl(lvl)
==Операции над структурой==
===Поиск элемента===
 [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] Алгоритм поиска элементе элемента в списке с пропусками состоит из следующих операций:
# Начинаем поиск элемента в самом верхнем уровне
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
# Переместиться Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратить прекратим поиск и вернуть вернём ссылку на текущую вершину
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего Если же у нас будет <tex>\logk</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{n1/k}</tex>раз элементов больше, откуда вытекает оценка времени чем уровнем выше. В таком случае время поиска элемента в <tex>-</tex> <tex>O(k \logcdot n^{n1/k})</tex>.
====Псевдокод====
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
# Начинаем вставку на самом верхнем уровне
# Пока Переходим к следующему элементу списка пока значение следующего элемента следующей ячейки меньше ключа — переходим к следующему элементу.# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более, чем на один. Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
====Псевдокод====
Функция <tex>\mathtt{insert}\ </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
'''node''' insert('''node''' res, '''K''' key)
'''else'''
down_node = insert(res.down, key)
'''if''' down_node <tex>\neq</tex> ''null'''''or''' res.down = ''null'' <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font>
res.next = node(key, down_node, res.next)
'''if''' randomcoin_flip(0, 1) > 0.5 = ''head'' <font color=darkgreen>// Бросок монетыЕсли выпал «Орёл»</font>
'''return''' res.next
'''return''' ''null''
'''node''' res = insert(skip.head, key)
'''if''' res <tex>\neq</tex> ''null''
'''list''' lvl;
lvl.head.next = node(key, res, lvl.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
delete(res.down, key)
'''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
res.next = res.next.next; Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O(k \cdot n^{1/k})</tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>. Для того, чтобы удалить элемент <tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:  delete(skip.head, key)
==Использование нечестной монеты==
Вместо честной монеты с распределением <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_{\frac{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>)</tex>.  Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>\left\frac{ p, q \right\}</tex>, при котором функция <tex>\dfrac{1}{px}\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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
Для крайних распределений:
==Применение==
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.:
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
* Легко модифицировать под различные задачи
===Нахождение всех интерваловотрезков, покрывающих данную точку===
{{Задача
|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>[L, R]</tex> на <tex>3</tex> части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, иначе спускаемся внизпоскольку левая или правая часть отрезка будет равна <tex>l.next.key</tex> или <tex>r.key</tex>. Итого время обработки запроса <tex>O(\log{n})</tex>. Когда нам приходит запрос  Для запросов второго типа — на мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне находим такие два элементанайдём тот элемент, что значение которого не меньше точки <tex>x</tex> лежит между ними. Если такой элемент нашёлся, и то прибавляем к ответу прибавляем значение на данном отрезкеотрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Итого оба запросы Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обрабатываем обработаем за <tex>O(\log{n})</tex>.
==См. также==
*[[Поисковые структуры данных]]
*[[Skip quadtree: определение, время работы|Skip quadtree]]
*[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками
==Источники информации==
390
правок

Навигация