Изменения

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

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

5179 байт добавлено, 22 апрель
м
Использование нечестной монеты
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях с номерами меньших , номера которых меньше <tex>i</tex>.
==Построение==
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
====Псевдокод====
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое которого есть начало <tex>\mathtt{head}\ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
Элементы односвязного списка <tex>-</tex> вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:* <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент спискана данном уровне* <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине* <tex>\mathtt{down}</tex> <tex>-</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) <font color=darkgreen>// Отсеивание нечётных элементов</font> '''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 != lvl.tail)next <tex>\neq</tex> ''null'' next_lvlcur.push_back(next = node(i.key, i, cur.next)) <font color=darkgreen>// Конструктор node(key, down, next) возвращает новую вершину с ключом key , ссылками down на нижний и ссылкой 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): '''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 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
lvl = build_lvl(lvl)
'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
==Операции над структурой==
===Поиск элемента===
 [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] Алгоритм поиска элементе элемента в списке с пропусками состоит из следующих операций:
# Начинаем поиск элемента в самом верхнем уровне
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
# Переместиться Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</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>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
'''T''' find ('''node''' res, '''K''' key) '''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font> res = res.next <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font> '''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> '''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> '''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
# Начинаем вставку на самом верхнем уровне
# Пока следующих элемент следующего элемента Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа <tex>-</tex> идём по списку вправо.# Если мы на первом уровне <tex>-</tex> вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе <tex>-</tex> ''null''. Если мы были не на первом уровне и нам вернули ''null'' <tex>-</tex> возвращаем его без броска монетки. Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
Отдельно стоит обработать случайЗаметим, когда что вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, <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) '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.next <tex>\neqkey </tex> ''null''key res = res.next '''node''' down_node
'''if''' res.down = ''null''
res.next down_node = node(key, ''null'', res.next) '''ifelse''' random(0, 1) > 0.5 '''return''' res.next '''return''' ''null'' node i down_node = insert(res.down, key) '''if''' i down_node <tex>\neq</tex> ''null'''''or''' res.down = ''null'' <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font> res.next = node(key, idown_node, res.next) '''if''' randomcoin_flip(0, 1) = ''head'' <font color=darkgreen>// Если выпал «Орёл»</font> 0.5
'''return''' res.next
'''return''' ''null''
Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в список с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию
 
'''function''' insert_element('''list''' skip, '''K''' key)
'''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>-</tex> , то просто удаляем элемент# Иначе спускаемся ниже и также удаляем элемент ещё с текущего нижнего уровня, если он есть.
====Псевдокод====
Функция <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
 
Аналогично со вставкой удаление <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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
Для крайних распределений:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex> <tex>-</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.* <tex>\{1, 0\}</tex> {{---}} зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</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] — структура данных, основанная на списке с пропусками
==Источники информации==
385
правок

Навигация