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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
м (Использование нечестной монеты)
 
(не показаны 72 промежуточные версии этого же участника)
Строка 3: Строка 3:
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровне, то он также расположен на всех нижележащих уровнях.
+
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях, номера которых меньше <tex>i</tex>.
  
 
==Построение==
 
==Построение==
 +
[[Файл:SimpleList.png|thumb|600px|Односвязный отсортированный список]]
  
 +
[[Файл:SkipList.png|thumb|600px|Получившийся список с пропусками]]
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
 +
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
  
[[Файл:SimpleList.png]]
+
====Псевдокод====
  
 +
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head} \ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
  
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элемента, номера которых кратны четырём. Аналогично построим и последующие уровни.
+
Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
 +
* <tex>\mathtt{next}</tex> — ссылка на следующий элемент списка на данном уровне
 +
* <tex>\mathtt{key}</tex> — ключ, который хранится в данной вершине
 +
* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже
  
[[Файл:SkipList.png]]
+
    '''struct''' node:
 +
        '''node''' next, down
 +
        '''K''' key
  
 +
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>,
  
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
 
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
  
     '''list''' build_lvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
+
     '''list''' build_lvl('''list''' lvl)                   
         '''list''' next_lvl  
+
         '''list''' next_lvl
         '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
+
        next_lvl.head.down = lvl.head
         '''while''' (i != ''null'') '''and''' (i != lvl.tail())
+
        next_lvl.tail.down = lvl.tail
             next_lvl.push_back(node(i.key, i)<font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
+
         '''node''' i = lvl.head.next.next                     
             i = i.next.next                     <font color=darkgreen>// Переход к следующему чётному элементу</font>
+
        '''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  
 
         '''return''' next_lvl  
  
 
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
 
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
  
     '''list''' skip_list ('''list''' l):
+
     '''list''' skip_list('''list''' l):
         '''list''' lvl = build_lvl(l)                <font color=darkgreen>// Построение первого уровня</font>
+
         '''list''' lvl                                               <font color=darkgreen>// Построение первого уровня</font>
         '''while''' lvl.size() > 2                  <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
+
         '''node''' i = l.head
             lvl = build_lvl (lvl)                       
+
        '''node''' j = lvl.head
         '''return''' lvl                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
+
        '''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>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину
  
Допустим, что в нашем списке с пропусками существуют <tex>k</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>2</tex>. Если мы уже были на первом уровне <tex>-</tex> прекратить поиск.
 
  
Пример поиска числа <tex>8</tex> в списке из описания:
+
Функция <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>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
  
 +
    find(skip.head, key)
  
[[Файл:SkipListSearch.png]]
+
===Вставка элемента===
 +
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
 +
# Начинаем вставку на самом верхнем уровне
 +
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
 +
# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
 +
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
  
 +
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
  
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
+
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
  
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
+
====Псевдокод====
+
Функция <tex>\mathtt{insert} \ </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
    '''T''' find ('''list''' skip_list, '''K''' key)
 
        '''node''' res
 
        '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref)    <font color=darkgreen>// Пока ещё не дошли до первого уровня </font>
 
            '''while''' res.key < key                                        <font color=darkgreen>// Пока значение вершины меньше ключа</font>
 
                res = res.next()                                      <font color=darkgreen>// Перейти к следующей вершине в текущем уровне</font>
 
        '''return''' res
 
  
===Вставка элемента===
+
    '''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> необходимо вызвать следующую функцию
# Вставить наш элемент в текущий уровень списка с пропусками
 
# Подбросить монету.
 
# Если выпал «Орёл» то перейти на уровень выше и вернуться к шагу <tex>2</tex>
 
# Иначе закончить операцию вставки
 
  
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</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>.
+
    '''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>\left\{\dfrac{1}{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}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
+
===Удаление элемента===
Для крайних распределений:
+
Алгоритм удаления элемента выглядит следующим образом:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>
+
# Начинаем удалять элемент с верхнего уровня
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)
+
# Переходим к следующему элементу, пока значение следующего элемента меньше ключа
 +
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
 +
====Псевдокод====
 +
Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.
  
     '''node''' insert ('''node''' i, '''K''' key, '''T''' data)
+
     '''function''' delete('''node''' res, '''K''' key)
         '''while''' i.key <= key                  <font color=darkgreen>// Ищем подходящее место</font>
+
         '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
            i = i.next()
+
            res = res.next
        '''node''' tmp = ''null''                     <font color=darkgreen>// Для записи в поле down</font>
+
         '''if''' res.down <tex>\neq</tex> ''null''
         '''if''' i.ref != ''null''                     <font color=darkgreen>// Мы не на нижнем уровне</font>
+
             delete(res.down, key)
             tmp = insert (i.ref, key)       <font color=darkgreen>// Рекурсивный вызов на более низком уровне</font>
+
        '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
            '''if''' tmp == ''null''                  <font color=darkgreen>// Проверка броска монетки</font>
+
            res.next = res.next.next
                '''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>
+
Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O(k \cdot n^{1/k})</tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
        insert(skip_list.head, key, data)
 
  
===Удаление элемента===
+
Для того, чтобы удалить элемент <tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:
Алгоритм удаления достаточно тривиален.
 
# Найти удаляемый элемент
 
# Удалить его со всех уровней
 
  
Функция <tex>\mathtt{erase}</tex> удаляет вершину <tex>i</tex> из списка с пропусками.
+
    delete(skip.head, key)
  
    '''void''' erase ('''node''' i, '''K''' key)
+
==Использование нечестной монеты==
        '''if''' i == ''null''
+
Вместо честной монеты с распределением <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>.
            '''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>
 
  
Для того, чтобы удалить элемент с ключом <tex>key</tex> из списка с пропусками <tex>list</tex> достаточно вызвать функцию <tex>\mathtt{erase}</tex> следующим образом:
+
Пусть у нас добавлено <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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
  
    erase(list.head, key)
+
Для крайних распределений:
 +
* <tex>\{0, 1\}</tex> — <tex>O(n)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
 +
* <tex>\{1, 0\}</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]]
*[[Skip quadtree: определение, время работы]]
 
*[http://en.wikipedia.org/wiki/Skip_graph Википедия — Skip graph(En)]
 
  
 
==Источники информации==
 
==Источники информации==
Строка 134: Строка 182:
 
*[http://en.wikipedia.org/wiki/Skip_list Wikipedia — skip list]
 
*[http://en.wikipedia.org/wiki/Skip_list Wikipedia — skip list]
 
*[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]
*[https://link.springer.com/chapter/10.1007/BFb0028258 springer.com The interval skip list]
+
*[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]
 +
 
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 14:22, 22 апреля 2019

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

Список с пропусками (англ. 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].

См. также[править]

Источники информации[править]