Изменения

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

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

6325 байт добавлено, 14:22, 22 апреля 2019
м
Использование нечестной монеты
'''Список с пропусками''' (англ. ''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 <font color.next.next '''node''' cur =darkgreen>// Перебор всех элементов lvl</font>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{listskip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
find(listskip.head(), key)
===Вставка элемента===
Для того, чтобы вставить элемент Алгоритм вставки элементов в список с пропусками, нужно запустить рекурсивную функцию, которая в каждом состоит из уровней найдёт позицию, где должен был стоять элементследующих шагов:# Начинаем вставку на самом верхнем уровне# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа. # Если это первый уровень, то просто мы на первом уровне — вставляем элемент в список, а также бросаем монетку . Иначе спускаемся ниже и возвращаем результатвозвращаемся к шагу <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) '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key res = res.next '''node''' down_node '''if''' res.down = ''null'' down_node = ''null'' '''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''' coin_flip() = ''head'' <font color=darkgreen>// Если выпал «Орёл»</font> '''return''' res.next '''return''' ''null'' '''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>\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>\{1, 0\}</tex> {{---}} — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>\inftyO(n)</tex>.
==Применение==
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.:
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
* Следующий элемент достаётся за <tex>O(1)</tex>(при условии, что у нас есть ссылка не текущий)
* Легко модифицировать под различные задачи
===Нахождение всех интерваловотрезков, покрывающих данную точку=== 
{{Задача
|definition = Есть <tex>q</tex> запросов Пусть у нас есть запросы двух видов:# Добавить интервал отрезок <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
правок

Навигация