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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение)
м (rollbackEdits.php mass rollback)
 
(не показаны 53 промежуточные версии 2 участников)
Строка 3: Строка 3:
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях с номерами меньших <tex>i</tex>.
+
Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях, номера которых меньше <tex>i</tex>.
  
 
==Построение==
 
==Построение==
Строка 11: Строка 11:
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
+
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
  
 
====Псевдокод====
 
====Псевдокод====
  
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
+
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head} \ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
  
Элементы односвязного списка состоят из вершин <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
+
Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
* <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент списка
+
* <tex>\mathtt{next}</tex> ссылка на следующий элемент списка на данном уровне
* <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине
+
* <tex>\mathtt{key}</tex> ключ, который хранится в данной вершине
* <tex>\mathtt{down}</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже
+
* <tex>\mathtt{down}</tex> ссылка на соответственный элемент, лежащий уровнем ниже
  
Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</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> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
 
Функция <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
 +
        '''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)                       
 
             lvl = build_lvl(lvl)                       
         '''return''' lvl                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
+
         '''return''' lvl                                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
  
 
==Операции над структурой==
 
==Операции над структурой==
 
===Поиск элемента===
 
===Поиск элемента===
 
+
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]]
+
# Начинаем поиск элемента в самом верхнем уровне
 
 
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем будет исходный список.
 
 
 
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
 
 
 
# Начинаем поиск элемента в самом верхнем (<tex>k</tex>-ом) уровне
 
 
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
 
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
# Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже были на первом уровне <tex>-</tex> прекратить поиск.
+
# Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину
  
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>key</tex> или ссылку на хвост списка на первом уровне.
+
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне.
  
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
+
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Если же у нас будет <tex>k</tex> уровней, тогда на каждом уровне в среднем будет в <tex>n^{1/k}</tex> раз элементов больше, чем уровнем выше. В таком случае время поиска элемента <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
  
 
====Псевдокод====
 
====Псевдокод====
Строка 63: Строка 71:
 
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
 
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками.
 
   
 
   
     '''T''' find ('''node''' res, '''K''' key)
+
     '''T''' find('''node''' res, '''K''' key)
         '''while''' res.key < key                                        <font color=darkgreen>// Пока значение вершины меньше ключа</font>
+
         '''while''' res.key < key                                         
             res = res.next()                                      <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font>
+
             res = res.next                                        
         '''if''' res.down = ''null''                                         <font color=darkgreen>// Если мы находимся на первом уровне</font>
+
         '''if''' res.down = ''null''                                   <font color=darkgreen>// Если мы находимся на первом уровне</font>
             '''return''' res                                             <font color=darkgreen>// Мы нашли искомый элемент</font>
+
             '''return''' res                                       <font color=darkgreen>// Мы нашли искомый элемент</font>
         '''return''' find(res.down, key)                                 <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
+
         '''return''' find(res.down, key)                           <font color=darkgreen>// Иначе спустимся на один уровень ниже</font>
  
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{list}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
+
Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом
  
     find(list.head(), key)
+
     find(skip.head, key)
  
 
===Вставка элемента===
 
===Вставка элемента===
Для того, чтобы вставить элемент в список с пропусками, нужно запустить рекурсивную функцию, которая в каждом из уровней найдёт позицию, где должен был стоять элемент. Если это первый уровень, то просто вставляем элемент в список, а также возвращаем результат броска монетки. Если же это не самый нижний уровень <tex>-</tex> то рекурсивно вызываем функцию. Если в результате броска монетки выпал «Орёл», то вставляем элемент в список текущего уровня, а также вернуть результат броска монетки. Если же выпала «Решка», то просто возвращаем такой же результат. Нужно также обработать тот случай, если на всех уровнях выпал «Орёл». В таком случае надо создать новый верхний уровень и вставить в него текущий элемент, а также вернуть ссылку на начало нового уровня.
+
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
 +
# Начинаем вставку на самом верхнем уровне
 +
# Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
 +
# Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу <tex>2</tex>. Если нам вернули не ''null'' — вставляем элемент на текущем уровне тоже.
 +
# Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — ''null''. Если мы были не на первом уровне и нам вернули ''null'' — возвращаем его без броска монетки.
 +
 
 +
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 +
 
 +
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
 +
 
 +
====Псевдокод====
 +
Функция <tex>\mathtt{insert} \ </tex> возвращаем ссылку на вставленный элемент в списке, в котором находится <tex>\mathtt{res}</tex>, или ''null'', если на монете выпала «Решка».
 +
 
 +
    '''node''' insert('''node''' res, '''K''' key)
 +
        '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
 +
            res = res.next                                   
 +
        '''node''' down_node
 +
        '''if''' res.down = ''null''
 +
            down_node = ''null''
 +
        '''else'''
 +
            down_node = insert(res.down, key)
 +
        '''if''' down_node <tex>\neq</tex> ''null'' '''or''' res.down = ''null''                <font color=darkgreen>// Если выпал «Орёл» или мы находимся на первом уровне</font>
 +
            res.next = node(key, down_node, res.next)
 +
            '''if''' coin_flip() = ''head''                              <font color=darkgreen>// Если выпал «Орёл»</font>
 +
                '''return''' res.next
 +
            '''return''' ''null''
 +
        '''return''' ''null''
 +
 
 +
Для того, чтобы вставить элемент с ключом <tex>\mathtt{key}</tex> в список с пропусками <tex>\mathtt{skip}</tex> необходимо вызвать следующую функцию
 +
 
 +
    '''function''' insert_element('''list''' skip, '''K''' key)
 +
        '''node''' res = insert(skip.head, key)
 +
        '''if''' res <tex>\neq</tex> ''null''
 +
            '''list''' lvl
 +
            lvl.head.next = node(key, res, lvl.tail)
 +
            skip = lvl
  
 
===Удаление элемента===
 
===Удаление элемента===
Для того, чтобы удалить элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом уровне, подобно поиску, найдёт позицию, где должен был стоять элемент. Во время рекурсии если это самый нижний уровень, то удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем уровне. После удаления элемента могло так получить, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на начало самого верхнего уровня.
+
Алгоритм удаления элемента выглядит следующим образом:
 +
# Начинаем удалять элемент с верхнего уровня
 +
# Переходим к следующему элементу, пока значение следующего элемента меньше ключа
 +
# Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
 +
====Псевдокод====
 +
Функция <tex>\mathtt{delete}</tex> удаляет элемент <tex>\mathtt{key}</tex> со всех уровней.
 +
 
 +
    '''function''' delete('''node''' res, '''K''' key)
 +
        '''while''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key < key
 +
            res = res.next
 +
        '''if''' res.down <tex>\neq</tex> ''null''
 +
            delete(res.down, key)
 +
        '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
 +
            res.next = res.next.next
 +
 
 +
Аналогично со вставкой удаление <tex>-</tex> поиск элемента за <tex>O(k \cdot n^{1/k})</tex> плюс удаление на каждом уровне за <tex>O(1)</tex>. Итого <tex>-</tex> <tex>O(k \cdot n^{1/k})</tex>.
 +
 
 +
Для того, чтобы удалить элемент <tex>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:
 +
 
 +
    delete(skip.head, key)
  
 
==Использование нечестной монеты==
 
==Использование нечестной монеты==
Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex> (на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{\frac{1}{p}} {n}</tex>).  
+
Вместо честной монеты с распределением <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>.
 +
 
 +
Пусть у нас добавлено <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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
  
 
Для крайних распределений:
 
Для крайних распределений:
* <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex>
+
* <tex>\{0, 1\}</tex> <tex>O(n)</tex> — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex>
+
* <tex>\{1, 0\}</tex> — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>.
  
 
==Применение==
 
==Применение==
  
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.
+
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
 
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы
* Следующий элемент достаётся за <tex>O(1)</tex>
+
* Следующий элемент достаётся за <tex>O(1)</tex> (при условии, что у нас есть ссылка не текущий)
 
* Легко модифицировать под различные задачи
 
* Легко модифицировать под различные задачи
  
===Нахождение всех интервалов, покрывающих данную точку===
+
===Нахождение всех отрезков, покрывающих данную точку===
 +
 
 +
{{Задача
 +
|definition = Пусть у нас есть запросы двух видов:
 +
# Добавить отрезок <tex>[L, R]</tex>
 +
# Для заданной точки <tex>x</tex> вычислить количество отрезков, которые её покрывают.
 +
Необходимо для каждого запроса второго типа вывести ответ.
 +
}}
  
Список с пропусками используют для решение одной из классических задач <tex>-</tex> нахождения количество интервалов, которые покрывают данную точку. Более подробное условие задачи: пусть у нас есть поле, координаты которого <tex>-</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>[L, R]</tex>
 
# Задана точка <tex>x</tex>. Найти количество интервалов, которые покрывают данную точку
 
Список с пропусками позволяет решать данную задачу онлайн за <tex>O(\log{q})</tex> времени, где <tex>q</tex> <tex>-</tex> количество запросов. В отличии от дерева отрезков, для которого требуется, чтобы координаты были целыми числами в небольшом диапазоне, списку с пропусками не важно, какого типа координаты, главное, чтобы их можно было сравнивать.
 
  
Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. Очевидно, что оба запроса мы обрабатываем за <tex>O(\log{n})</tex>, при этом нет никакой необходимости знать запросы заранее.
+
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Поскольку уровней всего <tex>\log{n}</tex>, а на каждом уровне обойдём не более двух элементов, то данный тип запросов мы обработаем за <tex>O(\log{n})</tex>.
  
 
==См. также==
 
==См. также==
Строка 109: Строка 177:
 
*[[Поисковые структуры данных]]
 
*[[Поисковые структуры данных]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
 
*[[Skip quadtree: определение, время работы|Skip quadtree]]
*[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками
 
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 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].

См. также

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