Список с пропусками — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Поиск элемента: Исправлена оценка на время исполнения операций)
м (rollbackEdits.php mass rollback)
 
(не показано 88 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
[[Файл:Skip list example.png|thumb|550px|Пример списка с пропусками]]
 
[[Файл:Skip list example.png|thumb|550px|Пример списка с пропусками]]
  
'''Список с пропусками''' (англ. ''skip list'') — структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
+
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на <tex>i</tex>-ом уровне, то он также расположен на <tex>(i-1)</tex>-ом, <tex>(i-2)</tex>-ом и более низких уровнях.
+
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях, номера которых меньше <tex>i</tex>.
  
 
==Построение==
 
==Построение==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
+
[[Файл:SimpleList.png|thumb|600px|Односвязный отсортированный список]]
  
[[Файл:SimpleList.png]]
+
[[Файл:SkipList.png|thumb|600px|Получившийся список с пропусками]]
 +
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять <tex>O(\log(n))</tex>.
+
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
  
[[Файл:SkipList.png]]
+
====Псевдокод====
 +
 
 +
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <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):
 +
        '''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.size > 2                   
 +
            lvl = build_lvl(lvl)                     
 +
        '''return''' lvl                                            <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
  
 
==Операции над структурой==
 
==Операции над структурой==
 
===Поиск элемента===
 
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем (<tex>L_1</tex>) будет исходный список.
+
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
 +
# Начинаем поиск элемента в самом верхнем уровне
 +
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
 +
# Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину
 +
 
 +
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
  
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
+
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет <tex>k</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{1/k}</tex> раз элементов больше, чем уровнем выше. В таком случае время поиска элемента <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
# Начинаем поиск элемента в верхнем списке (<tex>L_k</tex>), рассмотрим первый элемент
 
# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
 
# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска
 
  
Пример поиска числа <tex>8</tex> в списке из описания:
+
====Псевдокод====
  
[[Файл:SkipListSearch.png]]
+
Функция <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_1</tex> и <tex>L_2</tex>. Поскольку элементы по уровням распределяются равномерно, то в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет составлять <tex>\dfrac{n}{\vert L_2 \vert}</tex>. Оценим среднее время доступа к элементу. Мы пройдём не более <tex>\vert L_2 \vert</tex> элементов на втором уровне, однако, если на каком-нибудь шаге мы спустимся на нижней уровень, то пройдём в среднем не более <tex>\dfrac{n}{\vert L_2 \vert}</tex> элементов (в противном случае мы могли бы пройти ещё один элемент на втором уровне). Минимизируем величину <tex>\vert L_2 \vert + \dfrac{n}{\vert L_2 \vert}</tex>. Очевидно, что при <tex> \vert L_2 \vert = \sqrt{n}</tex> сумма достигает минимального значения. Таким образом, время поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrt{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>. 
+
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
  
Допустим, что у нас имеется не два, а <tex>k</tex> уровней. Тогда оптимально на каждом из <tex>k</tex> уровней проходить не более <tex>\sqrt[k]{n}</tex> элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная <tex>O(\sqrt[k]{n})</tex>.
+
    find(skip.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>\dfrac{n}{2}</tex>, на третьем уровне <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
+
Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в список с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию
  
Используя монетку с распределением отличным от <tex>\{\dfrac{1}{2}</tex>, <tex>\dfrac{1}{2}\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex>}, математическое ожидание количества элементов на уровне <tex>l</tex> равно <tex dpi=150>n q^l</tex>, каждый уровень будет составлять <tex>q</tex> от предыдущего; время поиска будет равно <tex>O(\dfrac{k}{q} + nq^k)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
+
    '''function''' insert_element('''list''' skip, '''K''' key)
Для крайних распределений:
+
        '''node''' res = insert(skip.head, key)
* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>
+
        '''if''' res <tex>\neq</tex> ''null''
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)
+
            '''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> следующим образом:
* <tex>next</tex> {{---}} следующий узел
 
* <tex>down</tex> {{---}} тот же узел на следующем уровне
 
* <tex>data</tex> {{---}} данные типа T
 
* <tex>key</tex> {{---}} ключ типа K
 
  
Конструктор
+
     delete(skip.head, key)
<code>
 
     '''list''' skip_list ('''list''' l):
 
        '''list''' lvl = build_lvl(l)                <font color=darkgreen>// Здесь происходит построение первого уровня</font>
 
        '''while''' lvl.size() > 2
 
            lvl = build_lvl (lvl)               <font color=darkgreen>// Добавление следующих уровней; последний содержит два элемента</font>
 
        '''return''' t
 
  
    '''list''' build_lvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
+
==Использование нечестной монеты==
        '''list''' next_lvl
+
Вместо честной монеты с распределением <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>)</tex>.  
        '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
+
 
        '''while''' (i != ''null'') '''and''' (i != lvl.tail())
+
Пусть у нас добавлено <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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
            next_lvl.push_back(node(i.key, i))  <font color=darkgreen>// Добавление чётного элемента;</font>
 
            i = i.next.next                    <font color=darkgreen>// он содержит ключ и ссылку на предыдущий уровень</font>
 
        '''return''' next_lvl
 
</code>
 
Поиск элемента по ключу:
 
<code>
 
    '''T''' find ('''list''' skip_list, '''K''' key)
 
        '''node''' res
 
        '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref)
 
                                            <font color=darkgreen>// Cпускаемся на шаг вниз, если можем (п. 3)</font>
 
            '''while''' res.key <= key            <font color=darkgreen>// Переходим к следующему элементу (п. 2)</font>
 
                res = res.next()
 
        '''return''' res.data
 
</code>
 
Вставка:
 
<code>
 
    '''node''' insert ('''node''' i, '''K''' key, '''T''' data)
 
        '''while''' i.key <= key                  <font color=darkgreen>// Ищем подходящее место</font>
 
            i = i.next()
 
        '''node''' tmp = ''null''                      <font color=darkgreen>// Для записи в поле down</font>
 
        '''if''' i.ref != ''null''                    <font color=darkgreen>// Мы не на нижнем уровне</font>
 
            tmp = insert (i.ref, key)        <font color=darkgreen>// Рекурсивный вызов на более низком уровне</font>
 
            '''if''' tmp == ''null''                  <font color=darkgreen>// Проверка броска монетки</font>
 
                '''return''' ''null''
 
        i.next = '''new''' node (i.next, tmp, data, key)  <font color=darkgreen>//Непосредственно вставка</font>
 
        '''if''' random(0,1) > 0.5                <font color=darkgreen>// Бросок монетки</font>
 
            return i.next                    <font color=darkgreen>// Нужно передать новый элемент для вставки выше</font>
 
        '''else'''
 
            return ''null''
 
  
    '''void''' insert ('''list''' skip_list, '''K''' key, '''T''' data) <font color=darkgreen>// Обёрточка</font>
+
Для крайних распределений:
        insert(skip_list.head, key, data)  
+
* <tex>\{0, 1\}</tex> <tex>O(n)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
</code>
+
* <tex>\{1, 0\}</tex> — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.
Удаление:
 
<code>
 
    '''void''' erase ('''node''' i, '''K''' key)
 
        '''if''' i == ''null''
 
            '''return'''
 
        '''while''' i.key <= key                  <font color=darkgreen>// Ищем элемент</font>
 
            i = i.next()
 
        erase(i.ref, key)                    <font color=darkgreen>// Удаляем с нижних уровней</font>
 
        '''if''' i.key == key                      <font color=darkgreen>// Если ключ совпадает</font>
 
            '''delete'''(i)                       <font color=darkgreen>// удаляем и с этого уровня</font>
 
  
    '''void''' erase ('''list''' skip_list, '''K''' key) <font color=darkgreen>// Обёрточка</font>
 
        erase(skip_list.head, key)
 
</code>
 
 
==Применение==
 
==Применение==
* Базы данных
+
 
* Распределённые вычисления и 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]]
*[[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 Википедия — списки с пропусками]
*[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 skip list]
*[http://en.wikipedia.org/wiki/Skip_list Википедия списки с пропусками(En)]
 
*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками]
 
 
*[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating]
 
*[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating]
 +
*[http://ticki.github.io/blog/skip-lists-done-right/ ticki.github.io — Skip Lists: Done Right]
 +
*[https://books.google.ru/books?id=NRrcsIJZAYMC&pg=PA157&lpg=PA157&dq=the+interval+skiplist&source=bl&ots=yqad5WH8im&sig=ACfU3U2vzUeMu_psDaWNJ4sztarLzJQsnw&hl=en&sa=X&ved=2ahUKEwi7ta6KyJbhAhWq5aYKHTmPBjgQ6AEwC3oECAkQAQ#v=onepage&q=the%20interval%20skiplist&f=false Eric N. Hanson — A Data Structure for Finding All Intervals That Overlap a Point стр. 155-164]
 +
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 19:15, 4 сентября 2022

Пример списка с пропусками

Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за [math]O(\log(n))[/math] времени выполнять операции добавления, удаления и поиска элементов.

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

Построение

Односвязный отсортированный список
Получившийся список с пропусками

Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за [math]O(\log{n})[/math] времени выполнять операции добавления, удаления и поиска элементов.

На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.

Псевдокод

Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало [math]\mathtt{head} \ [/math] и конец [math]\mathtt{tail}[/math]. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.

Элементы односвязного списка — вершины [math]\mathtt{node}[/math], у которых есть [math]3[/math] поля:

  • [math]\mathtt{next}[/math] — ссылка на следующий элемент списка на данном уровне
  • [math]\mathtt{key}[/math] — ключ, который хранится в данной вершине
  • [math]\mathtt{down}[/math] — ссылка на соответственный элемент, лежащий уровнем ниже
   struct node:
       node next, down
       K key

Также известно, что [math]\mathtt{head{.}key} = -\infty \ [/math] и [math]\mathtt{tail{.}key} = \infty[/math],

Функция [math]\ \mathtt{build\_lvl} \ [/math] возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.

   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 [math]\neq[/math] null and i.next [math]\neq[/math] null
           cur.next = node(key, i, cur.next)                  // Конструктор node(key, down, next) возвращает новую вершину с ключом key, ссылками down на нижний и next на следующий элемент
           cur = cur.next
           i = i.next.next                                    // Переход к следующему чётному элементу
       return next_lvl 

Функция [math]\ \mathtt{skip\_list} \ [/math] принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.

   list skip_list(list l):
       list lvl                                               // Построение первого уровня
       node i = l.head
       node j = lvl.head
       while j [math]\neq[/math] l.tail
           i.next = node(j.key, null, j.next)
           i = i.next
           j = j.next
       while lvl.size > 2                     
           lvl = build_lvl(lvl)                       
       return lvl                                             // Возвращает ссылку на начало верхнего уровня

Операции над структурой

Поиск элемента

Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:

  1. Начинаем поиск элемента в самом верхнем уровне
  2. Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
  3. Переместимся на один уровень вниз и перейти к шагу [math]2[/math]. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину

В конце алгоритма функция вернёт элемент, значение которого не меньше ключа [math]\mathtt{key}[/math] или ссылку на конец списка на первом уровне.

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

Псевдокод

Функция [math]\mathtt{find}[/math] возвращает ссылку на элемент, значение которого не меньше [math]\mathtt{key}[/math]. В случае, если все элементы в списке с пропусками меньше [math]\mathtt{key}[/math], то возвращается ссылка на конец списка с пропусками.

   T find(node res, K key)
       while res.key < key                                        
           res = res.next                                         
       if res.down = null                                    // Если мы находимся на первом уровне
           return res                                        // Мы нашли искомый элемент
       return find(res.down, key)                            // Иначе спустимся на один уровень ниже

Для того, чтобы найти элемент с ключом [math]\mathtt{key}[/math] в списке с пропусками [math]\mathtt{skip}[/math] необходимо запустить [math]\mathtt{find}[/math] следующим образом

   find(skip.head, key)

Вставка элемента

Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:

  1. Начинаем вставку на самом верхнем уровне
  2. Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
  3. Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу [math]2[/math]. Если нам вернули не null — вставляем элемент на текущем уровне тоже.
  4. Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — null. Если мы были не на первом уровне и нам вернули null — возвращаем его без броска монетки.

Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.

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

Псевдокод

Функция [math]\mathtt{insert} \ [/math] возвращаем ссылку на вставленный элемент в списке, в котором находится [math]\mathtt{res}[/math], или null, если на монете выпала «Решка».

   node insert(node res, K key)
       while res.next [math]\neq[/math] 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 [math]\neq[/math] null or res.down = null                // Если выпал «Орёл» или мы находимся на первом уровне
           res.next = node(key, down_node, res.next)
           if coin_flip() = head                              // Если выпал «Орёл»
               return res.next
           return null
       return null

Для того, чтобы вставить элемент с ключом [math]\mathtt{key}[/math] в список с пропусками [math]\mathtt{skip}[/math] необходимо вызвать следующую функцию

   function insert_element(list skip, K key)
       node res = insert(skip.head, key)
       if res [math]\neq[/math] null
           list lvl
           lvl.head.next = node(key, res, lvl.tail)
           skip = lvl

Удаление элемента

Алгоритм удаления элемента выглядит следующим образом:

  1. Начинаем удалять элемент с верхнего уровня
  2. Переходим к следующему элементу, пока значение следующего элемента меньше ключа
  3. Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.

Псевдокод

Функция [math]\mathtt{delete}[/math] удаляет элемент [math]\mathtt{key}[/math] со всех уровней.

   function delete(node res, K key)
       while res.next [math]\neq[/math] null and res.next.key < key
           res = res.next
       if res.down [math]\neq[/math] null
           delete(res.down, key)
       if res.next [math]\neq[/math] null and res.next.key = key
           res.next = res.next.next

Аналогично со вставкой удаление [math]-[/math] поиск элемента за [math]O(k \cdot n^{1/k})[/math] плюс удаление на каждом уровне за [math]O(1)[/math]. Итого [math]-[/math] [math]O(k \cdot n^{1/k})[/math].

Для того, чтобы удалить элемент [math]\mathtt{key}[/math] из списка с пропусками [math]\mathtt{skip}[/math], необходимо вызвать функцию [math]\mathtt{delete} \ [/math] следующим образом:

   delete(skip.head, key)

Использование нечестной монеты

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

Пусть у нас добавлено [math]n[/math] элементов. Найдём такое распределение [math]\left\{ p, q \right\}[/math], при котором функция [math]\dfrac{1}{x} \log_{1/x} {n}[/math] принимает минимальное значение. Производная этой функции равна [math]-\dfrac{\ln{n} \left( \ln {(1/x)} - 1 \right)}{x^2 \ln^2{(1/x)}}[/math]. При [math]x = \dfrac{1}{e}[/math] производная равна нулю, вторая производная в точке [math]x_0 = \dfrac{1}{e}[/math] больше [math]0[/math], значит [math]x_0[/math] [math]-[/math] точка минимума. Значит при распределении [math]\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}[/math] время поиска меньше всего. Но не стоит забывать, что это лишь теоретическая оценка и в действительности придумать источник с распределением [math]\left\{ \dfrac{1}{e}, \dfrac{e - 1}{e} \right\}[/math] почти невозможно, поэтому на практике лучше всего использовать честную монету.

Для крайних распределений:

  • [math]\{0, 1\}[/math][math]O(n)[/math] — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
  • [math]\{1, 0\}[/math] — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным [math]n[/math], значит время поиска будет равным [math]O(n)[/math].

Применение

Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:

  • Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
  • Проще реализовать, чем сбалансированные деревья или хеш-таблицы
  • Следующий элемент достаётся за [math]O(1)[/math] (при условии, что у нас есть ссылка не текущий)
  • Легко модифицировать под различные задачи

Нахождение всех отрезков, покрывающих данную точку

Задача:
Пусть у нас есть запросы двух видов:
  1. Добавить отрезок [math][L, R][/math]
  2. Для заданной точки [math]x[/math] вычислить количество отрезков, которые её покрывают.
Необходимо для каждого запроса второго типа вывести ответ.


Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа [math]L[/math] и [math]R[/math] в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие [math]l[/math] и [math]r[/math], что значение [math]l[/math] меньше [math]L[/math], а значение следующего за [math]l[/math] элемента уже не меньше [math]L[/math]. Аналогично ищем такое же [math]r[/math], только относительно [math]R[/math]. Если значения [math]l.next[/math] и [math]r[/math] лежат полностью внутри отрезка [math][L, R][/math], то к самому отрезку [math][l.next, r][/math] прибавляем [math]1[/math], а сам отрезок [math][L, R][/math] разбиваем на три [math][L, l.next.key - 1][/math], [math][l.next.key, r.key][/math] и [math][r.key + 1, R][/math] и по отдельности решаем задачу уже для полученных отрезков (если для какого-то отрезка левая граница стала больше правой, то мы ничего не делаем). Допустим, что на каком-то уровне у нас получилось разделить отрезок [math][L, R][/math] на [math]3[/math] части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза только с одной стороны, поскольку левая или правая часть отрезка будет равна [math]l.next.key[/math] или [math]r.key[/math]. Итого время обработки запроса [math]O(\log{n})[/math].

Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки [math]x[/math]. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего [math]\log{n}[/math], а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за [math]O(\log{n})[/math].

См. также

Источники информации