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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение)
Строка 7: Строка 7:
 
==Построение==
 
==Построение==
  
Допустим, что нам задан односвязный отсортированный список.
+
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов.
  
  
Строка 13: Строка 13:
  
  
Тогда на первом уровне мы расположим заданный список, на втором <tex>-</tex> только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем <tex>-</tex> с номерами, кратными <tex>4</tex>, и так далее. Такой список будет позволять в среднем за <tex>O(\log{n})</tex> выполнять операции поиска, добавления и удаления элементов.
+
На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элемента, номера которых кратны четырём. Аналогично построим и последующие уровни.
 
 
  
 
[[Файл:SkipList.png]]
 
[[Файл:SkipList.png]]
  
  
Функция <tex>\ \mathtt{buildLvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
+
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
  
     '''list''' buildLvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
+
     '''list''' build_lvl ('''list''' lvl)                  <font color=darkgreen>// Отсеивание нечётных элементов</font>
         '''list''' nextLvl
+
         '''list''' next_lvl
 
         '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
 
         '''node''' i = lvl.head()                    <font color=darkgreen>// Перебор всех элементов lvl</font>
 
         '''while''' (i != ''null'') '''and''' (i != lvl.tail())
 
         '''while''' (i != ''null'') '''and''' (i != lvl.tail())
             nextLvl.push_back(node(i.key, i))  <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
+
             next_lvl.push_back(node(i.key, i))  <font color=darkgreen>// Конструктор node(key, down) возвращает новую вершину с ключом key и ссылкой down на соответствующую вершину предыдущего уровеня</font>
 
             i = i.next.next                    <font color=darkgreen>// Переход к следующему чётному элементу</font>
 
             i = i.next.next                    <font color=darkgreen>// Переход к следующему чётному элементу</font>
         '''return''' nextLvl
+
         '''return''' next_lvl
  
Функция <tex>\ \mathtt{skipList} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
+
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.
  
     '''list''' skipList ('''list''' l):
+
     '''list''' skip_list ('''list''' l):
         '''list''' lvl = buildLvl(l)                 <font color=darkgreen>// Построение первого уровня</font>
+
         '''list''' lvl = build_lvl(l)               <font color=darkgreen>// Построение первого уровня</font>
         '''while''' lvl.size() > 2             <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
+
         '''while''' lvl.size() > 2                   <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font>
             lvl = buildLvl (lvl)                       
+
             lvl = build_lvl (lvl)                       
         '''return''' lvl                       <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
+
         '''return''' lvl                             <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font>
  
 
==Операции над структурой==
 
==Операции над структурой==

Версия 21:04, 21 марта 2019

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

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

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

Построение

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


SimpleList.png


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

SkipList.png


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

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

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

   list skip_list (list l):
       list lvl = build_lvl(l)                // Построение первого уровня
       while lvl.size() > 2                   // Добавление следующих уровней; последний содержит не более двух элементов
           lvl = build_lvl (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])
   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) 

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

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

  1. Найти удаляемый элемент
  2. Удалить его со всех уровней
   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) 

Псевдокод

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

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

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

Применение

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

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

См. также

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

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