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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вставка элемента)
(не показано 5 промежуточных версий этого же участника)
Строка 3: Строка 3:
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
 
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на <tex>i</tex>-ом уровне, то он также расположен на <tex>(i-1)</tex>-ом, <tex>(i-2)</tex>-ом и более низких уровнях.
+
Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем <tex>L_i</tex>, то он соответственно расположен и на всех уровнях <tex>L_j</tex>, где <tex>j < i</tex>.
  
 
==Построение==
 
==Построение==
Список с пропусками строится на основе существующего односвязного отсортированного списка.
+
 
 +
Допустим, что нам задан односвязный отсортированный список.
 +
 
  
 
[[Файл:SimpleList.png]]
 
[[Файл:SimpleList.png]]
  
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Соответственно, асимптотика этих операций будет составлять <tex>O(\log(n))</tex>.
+
 
 +
Тогда на первом уровне мы расположим заданный список, на втором <tex>-</tex> только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем <tex>-</tex> с номерами, кратными <tex>4</tex>, и так далее. Такой список будет позволять в среднем за <tex>O(\log{n})</tex> выполнять операции поиска, добавления и удаления элементов.
 +
 
  
 
[[Файл:SkipList.png]]
 
[[Файл:SkipList.png]]
 +
 +
 +
Функция <tex>\ \mathtt{buildLvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
 +
 +
    '''list''' buildLvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
 +
        '''list''' nextLvl
 +
        '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
 +
        '''while''' (i != ''null'') '''and''' (i != lvl.tail())
 +
            nextLvl.push_back(node(i.key, i))  <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
 +
            i = i.next.next                    <font color=darkgreen>// Переход к следующему чётному элементу</font>
 +
        '''return''' nextLvl
 +
 +
Функция <tex>\ \mathtt{skipList} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
 +
 +
    '''list''' skipList ('''list''' l):
 +
        '''list''' lvl = buildLvl(l)                <font color=darkgreen>// Построение первого уровня</font>
 +
        '''while''' lvl.size() > 2              <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
 +
            lvl = buildLvl (lvl)                     
 +
        '''return''' lvl                        <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
  
 
==Операции над структурой==
 
==Операции над структурой==
 
===Поиск элемента===
 
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем (<tex>L_1</tex>) будет исходный список.
+
Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем <tex>L_1</tex> будет исходный список.
  
 
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
 
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
 +
 
# Начинаем поиск элемента в верхнем списке (<tex>L_k</tex>), рассмотрим первый элемент
 
# Начинаем поиск элемента в верхнем списке (<tex>L_k</tex>), рассмотрим первый элемент
 
# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
 
# Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне - выйти из поиска
+
# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне <tex>-</tex> выйти из поиска
  
 
Пример поиска числа <tex>8</tex> в списке из описания:
 
Пример поиска числа <tex>8</tex> в списке из описания:
Строка 27: Строка 51:
 
[[Файл:SkipListSearch.png]]
 
[[Файл:SkipListSearch.png]]
  
В качестве примера рассмотрим список с двумя уровнями <tex>L_1</tex> и <tex>L_2</tex>. Поскольку элементы по уровням распределяются равномерно, то в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет составлять <tex>\dfrac{n}{\vert L_2 \vert}</tex>. Оценим среднее время доступа к элементу. Мы пройдём не более <tex>\vert L_2 \vert</tex> элементов на втором уровне, однако, если на каком-нибудь шаге мы спустимся на нижней уровень, то пройдём в среднем не более <tex>\dfrac{n}{\vert L_2 \vert}</tex> элементов (в противном случае мы могли бы пройти ещё один элемент на втором уровне). Минимизируем величину <tex>\vert L_2 \vert + \dfrac{n}{\vert L_2 \vert}</tex>. Очевидно, что при <tex> \vert L_2 \vert = \sqrt{n}</tex> сумма достигает минимального значения. Таким образом, время поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrt{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>.
+
Если в качестве случайного источника использовать честную монету, то тогда если в списке будет <tex>n</tex> элементов, то количество уровней в среднем будет равно <tex>\log{n}</tex>. Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>.
  
Допустим, что у нас имеется не два, а <tex>k</tex> уровней. Тогда оптимально на каждом из <tex>k</tex> уровней проходить не более <tex>\sqrt[k]{n}</tex> элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная <tex>O(\sqrt[k]{n})</tex>.
+
    '''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()  
 +
        '''return''' res.data
  
 
===Вставка элемента===
 
===Вставка элемента===
 
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
 
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
# Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
 
# Вставить наш элемент в нижний уровень списка с пропусками
 
# «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
 
# Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
 
  
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.
+
# Найти с помощью алгоритма поиска позицию, где мог бы находиться элемент.
 +
# Вставить наш элемент в текущий уровень списка с пропусками
 +
# Подбросить монету.
 +
# Если выпал «Орёл» то перейти на уровень выше и вернуться к шагу <tex>2</tex>
 +
# Иначе закончить операцию вставки
  
Используя монетку с распределением отличным от <tex>\{\dfrac{1}{2}</tex>, <tex>\dfrac{1}{2}\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex>}, математическое ожидание количества элементов на уровне <tex>l</tex> равно <tex dpi=150>n q^l</tex>, каждый уровень будет составлять <tex>q</tex> от предыдущего; время поиска будет равно <tex>O(\dfrac{k}{q} + nq^k)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.
+
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <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>.
 +
 
 +
Используя монетку с распределением отличным от <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>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>
Строка 59: Строка 90:
 
* <tex>key</tex>  {{---}} ключ типа K
 
* <tex>key</tex>  {{---}} ключ типа K
  
Конструктор
 
<code>
 
    '''list''' skip_list ('''list''' l):
 
        '''list''' lvl = build_lvl(l)                <font color=darkgreen>// Здесь происходит построение первого уровня</font>
 
        '''while''' lvl.size() > 2
 
            lvl = build_lvl (lvl)              <font color=darkgreen>// Добавление следующих уровней; последний содержит два элемента</font>
 
        '''return''' t
 
 
    '''list''' build_lvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
 
        '''list''' next_lvl
 
        '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
 
        '''while''' (i != ''null'') '''and''' (i != lvl.tail())
 
            next_lvl.push_back(node(i.key, i))  <font color=darkgreen>// Добавление чётного элемента;</font>
 
            i = i.next.next                    <font color=darkgreen>// он содержит ключ и ссылку на предыдущий уровень</font>
 
        '''return''' next_lvl
 
</code>
 
Поиск элемента по ключу:
 
<code>
 
    '''T''' find ('''list''' skip_list, '''K''' key)
 
        '''node''' res
 
        '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref)
 
                                            <font color=darkgreen>// Cпускаемся на шаг вниз, если можем (п. 3)</font>
 
            '''while''' res.key <= key            <font color=darkgreen>// Переходим к следующему элементу (п. 2)</font>
 
                res = res.next()
 
        '''return''' res.data
 
</code>
 
 
Вставка:
 
Вставка:
 
<code>
 
<code>

Версия 23:59, 20 марта 2019

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

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

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

Построение

Допустим, что нам задан односвязный отсортированный список.


SimpleList.png


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


SkipList.png


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

   list buildLvl (list lvl)                   // Отсеивание нечётных элементов
       list nextLvl 
       node i = lvl.head()                     // Перебор всех элементов lvl
       while (i != null) and (i != lvl.tail())
           nextLvl.push_back(node(i.key, i))  // Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня
           i = i.next.next                     // Переход к следующему чётному элементу
       return nextLvl 

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

   list skipList (list l):
       list lvl = buildLvl(l)                 // Построение первого уровня
       while lvl.size() > 2              // Добавление следующих уровней; последний содержит не более двух элементов
           lvl = buildLvl (lvl)                       
       return lvl                        // Возвращает ссылку на начало верхнего уровня

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

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

Допустим, что в нашем списке с пропусками существуют [math]k[/math] уровней, при этом первым уровнем [math]L_1[/math] будет исходный список.

В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:

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

Пример поиска числа [math]8[/math] в списке из описания:

SkipListSearch.png

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

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

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

Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:

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

Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется [math]\dfrac{n}{2}[/math], на третьем уровне [math]-[/math] [math]\dfrac{n}{4}[/math] и т.д. На уровне [math]\log{n}[/math] у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это [math]\dfrac{1}{2}[/math], на третий [math]\dfrac{1}{4}[/math] и т.д. Вероятность попасть на уровень [math]\log{n}[/math] равна [math]\dfrac{1}{n}[/math].

Используя монетку с распределением отличным от [math]\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}[/math], можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением [math]\{p,q\}[/math] математическое ожидание количества элементов на уровне [math]k[/math] равно [math]n q^k[/math], на каждом следующем уровне будет в среднем в [math]q[/math] раз больше элементов. Таким образом, время поиска будет равно [math]O\left(\dfrac{k}{q} + nq^k\right)[/math]. Соответственно при честной монетке и [math]\log(n)[/math] уровней получаем оценку, полученную ранее. Для крайних распределений:

  • [math]\{0, 1\}[/math][math]O(k+n)[/math]
  • [math]\{1, 0\}[/math][math]\infty[/math] (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе [math]O(n)[/math])

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

Алгоритм удаления достаточно тривиален.

  1. Найти удаляемый элемент
  2. Удалить его со всех уровней

Псевдокод

Наглядный, но не очень эффективный по памяти вариант списка с пропусками.

В узлах списка хранятся:

  • [math]next[/math] — следующий узел
  • [math]down[/math] — тот же узел на следующем уровне
  • [math]data[/math] — данные типа T
  • [math]key[/math] — ключ типа K

Вставка:

   node insert (node i, K key, T data)
       while i.key <= key                   // Ищем подходящее место
           i = i.next() 
       node tmp = null                      // Для записи в поле down
       if i.ref != null                     // Мы не на нижнем уровне
           tmp = insert (i.ref, key)        // Рекурсивный вызов на более низком уровне
           if tmp == null                   // Проверка броска монетки
               return null 
       i.next = new node (i.next, tmp, data, key)  //Непосредственно вставка
       if random(0,1) > 0.5                 // Бросок монетки
           return i.next                    // Нужно передать новый элемент для вставки выше
       else
           return null 
   void insert (list skip_list, K key, T data) // Обёрточка
       insert(skip_list.head, key, data) 

Удаление:

   void erase (node i, K key)
       if i == null
           return 
       while i.key <= key                   // Ищем элемент
           i = i.next() 
       erase(i.ref, key)                    // Удаляем с нижних уровней
       if i.key == key                      // Если ключ совпадает
           delete(i)                        // удаляем и с этого уровня
   void erase (list skip_list, K key) // Обёрточка
       erase(skip_list.head, key) 

Применение

  • Базы данных
  • Распределённые вычисления и p2p
  • Масштабируемые параллельные приоритетные очереди и словари

В вычислительной геометрии широко применяются структуры на основе списка с пропусками.

См. также

Структуры на основе списка с пропусками:

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