Изменения

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

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

Тогда на первом уровне мы расположим заданный списокЭлементы односвязного списка — вершины <tex>\mathtt{node}</tex>, на втором у которых есть <tex>-3</tex> только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем поля:* <tex>-\mathtt{next}</tex> с номерами, кратными — ссылка на следующий элемент списка на данном уровне* <tex>4\mathtt{key}</tex>— ключ, и так далее. Такой список будет позволять который хранится в среднем за данной вершине* <tex>O(\logmathtt{ndown})</tex> выполнять операции поиска— ссылка на соответственный элемент, добавления и удаления элементов.лежащий уровнем ниже

[[Файл:SkipListТакже известно, что <tex>\mathtt{head{.png]]}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</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>\mathtt{buildLvl} \ 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

'''list''' buildLvl ('''list''' lvl) Функция <font color=darkgreentex>// Отсеивание нечётных элементов\ \mathtt{skip\_list} \ </fonttex> '''list''' nextLvl '''node''' i = lvl.head() <font color=darkgreen>// Перебор всех элементов lvl</font> '''while''' (i != ''null'') '''and''' (i != lvl.tail()) nextLvl.push_back(node(i.key, i)) <font color=darkgreen>// Конструктор node(key, down) принимает в качестве аргумента односвязный отсортированный список и возвращает новую вершину новый список с ключом key и ссылкой down пропусками, построенный на соответствующую вершину предыдущего уровеня</font> i = i.nextего основе.next <font color=darkgreen>// Переход к следующему чётному элементу</font> '''return''' nextLvl

Функция <tex>\ \mathtt{skipList} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.  '''list''' skipList skip_list('''list''' l): '''list''' lvl = buildLvl(l) <font color=darkgreen>// Построение первого уровня</font> '''whilenode''' i = l.head '''node''' j = lvl.size() > 2 head '''while''' j <font color=darkgreentex>// Добавление следующих уровней; последний содержит не более двух элементов\neq</fonttex> l.tail i.next = node(j.key, ''null'', j.next) i = i.next j = j.next '''while''' lvl.size >2 lvl = buildLvl build_lvl(lvl) '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>

Допустим, что Алгоритм поиска элемента в нашем списке с пропусками существуют <tex>k</tex> уровнейсостоит из следующих операций:# Начинаем поиск элемента в самом верхнем уровне# Переходим к следующему элементу списка, при этом первым уровнем пока значение в следующей ячейке меньше# Переместимся на один уровень вниз и перейти к шагу <tex>L_12</tex> будет исходный список.Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину

В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.

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

[[Файл:SkipListSearchФункция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>.png]]В случае, если все элементы в списке с пропусками меньше <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>n</tex> элементов, то количество уровней в среднем будет равно чтобы найти элемент с ключом <tex>\logmathtt{nkey}</tex>. Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего списке с пропусками <tex>\logmathtt{nskip}</tex>, откуда вытекает оценка времени поиска элемента в необходимо запустить <tex>O(\logmathtt{nfind})</tex>.следующим образом

'''T''' find ('''list''' skip_list, '''K''' key) '''node''' res '''for''' (res = skip_listskip.head; res.ref != ''null''; res = res.ref) <font color=darkgreen>// Пока ещё не дошли до первого уровня </font> '''while''' res.key < , key <font color=darkgreen>// Переходим к следующему элементу</font> res = res.next() '''return''' res.data

Для Алгоритм вставки элемента элементов в список с пропускамисостоит из следующих шагов:# Начинаем вставку на самом верхнем уровне# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам необходимо выполнить следующие шаги:вернули ''null'' — возвращаем его без броска монетки.

# Найти с помощью алгоритма поиска позициюОтдельно стоит обработать случай, где мог бы находиться элементкогда вставка нового элемента увеличивает число уровней.# Вставить наш элемент Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий уровень списка элемент, и не забыть присвоить списку с пропусками# Подбросить монетуновую ссылку на верхний уровень.# Если выпал «Орёл» то перейти Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на уровень выше и вернуться к шагу <tex>2</tex># Иначе закончить операцию вставкиодин.

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

Используя монетку с распределением отличным от ====Псевдокод====Функция <tex>\left\mathtt{\dfrac{1insert}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять возвращаем ссылку на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex dpi=150>n q^k</tex>вставленный элемент в списке, на каждом следующем уровне будет в среднем в котором находится <tex>q</tex> раз больше элементов. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k}mathtt{qres} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.Для крайних распределений:* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>* <tex>\{1или ''null'', 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)на монете выпала «Решка».

'''node''' insert ('''node''' ires, '''K''' key, '''T''' data) '''while''' ires.key next <= key <font color=darkgreentex>// Ищем подходящее место\neq</fonttex> i = i.next() '''node''' tmp = ''null'' <font color=darkgreen>// Для записи в поле down</font> '''ifand''' ires.next.ref != ''null'' key <font color=darkgreen>// Мы не на нижнем уровне</font>key tmp res = insert (ires.ref, key) <font color=darkgreen>// Рекурсивный вызов на более низком уровне</font>next '''if''' tmp == 'node'null'' <font color=darkgreen>// Проверка броска монетки</font>down_node '''returnif''' res.down = ''null'' i.next down_node = '''new''' node (i.next, tmp, data, key) <font color=darkgreen>//Непосредственно вставка</font> null'''if''' random(0,1) > 0.5 <font color=darkgreen>// Бросок монетки</font> return i.next <font color=darkgreen>// Нужно передать новый элемент для вставки выше</font>

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> необходимо вызвать следующую функцию

'''voidfunction''' insert insert_element('''list''' skip_listskip, '''K''' key) '''node''' res = insert(skip.head, key) '''Tif''' data) res <font color=darkgreentex>// Обёрточка\neq</fonttex>''null'' '''list''' lvl insert(skip_list lvl.head.next = node(key, keyres, datalvl.tail) skip = lvl

Алгоритм удаления достаточно тривиален. элемента выглядит следующим образом:# Найти удаляемый Начинаем удалять элементс верхнего уровня# Переходим к следующему элементу, пока значение следующего элемента меньше ключа# Удалить Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.====Псевдокод====Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.

'''voidfunction''' erase delete('''node''' ires, '''K''' key) '''ifwhile''' i == res.next <tex>\neq</tex> ''null'' '''returnand''' res.next.key < key res = res.next '''whileif''' ires.key <= key down <font color=darkgreentex>// Ищем элемент\neq</fonttex>''null'' i = i.next() erasedelete(ires.refdown, key) <font color=darkgreen>// Удаляем с нижних уровней</font> '''if''' ires.key == key next <font color=darkgreentex>// Если ключ совпадает\neq</fonttex> ''null'' '''deleteand'''(i) <font colorres.next.key = key res.next =darkgreen>// удаляем и с этого уровня</font>res.next.next

'''void''' erase Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O('''list''' skip_list, '''K''' keyk \cdot n^{1/k}) <font color=darkgreen/tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</ Обёрточкаtex> <tex>O(k \cdot n^{1/k})</fonttex> erase(skip_list.head, key)

==Псевдокод==НаглядныйДля того, но не очень эффективный по памяти вариант чтобы удалить элемент <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>nextn \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>)</tex>. * Пусть у нас добавлено <tex>n</tex> элементов. Найдём такое распределение <tex>down\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>data. При <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} данные типа T\right\}</tex> почти невозможно, поэтому на практике лучше всего использовать честную монету. Для крайних распределений:* <tex>key\{0, 1\}</tex> — <tex>O(n)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.* <tex>\{{---1, 0\}} ключ типа K</tex> — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.

 Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:* Базы данныхБыстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)* Распределённые вычисления и p2pПроще реализовать, чем сбалансированные деревья или хеш-таблицы* Следующий элемент достаётся за <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>[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(En)]

*[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)]*[http://en.wikipedia.org/wiki/Skip_list Википедия Wikipedia — списки с пропусками(En)]*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропускамиskip list]