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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Использование нечестной монеты)
м (Использование нечестной монеты)
 
(не показано 9 промежуточных версий этого же участника)
Строка 65: Строка 65:
 
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{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>.
  
 
====Псевдокод====
 
====Псевдокод====
Строка 90: Строка 90:
  
 
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более чем на один.
 +
 +
Заметим, что вставка элемента <tex>-</tex> поиск элемента и за <tex>O(1)</tex> добавляем не более, чем в <tex>k</tex> уровней элемент. Итого время работы <tex>O(k \cdot n^{1/k})</tex>.
  
 
====Псевдокод====
 
====Псевдокод====
Строка 133: Строка 135:
 
         '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
 
         '''if''' res.next <tex>\neq</tex> ''null'' '''and''' res.next.key = key
 
             res.next = res.next.next
 
             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>\mathtt{key}</tex> из списка с пропусками <tex>\mathtt{skip}</tex>, необходимо вызвать функцию <tex>\mathtt{delete} \ </tex> следующим образом:
Строка 141: Строка 145:
 
Вместо честной монеты с распределением <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>\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{\log{n} \left( \log {(1/x)} - 1 \right)}{x^2 \log^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>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> почти невозможно, поэтому на практике лучше всего использовать честную монету.
  
 
Для крайних распределений:
 
Для крайних распределений:

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

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

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