Список с пропусками — различия между версиями
Gaporf (обсуждение | вклад) |
Gaporf (обсуждение | вклад) (→Вставка элемента) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов. | '''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов. | ||
− | Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на <tex> | + | Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем <tex>L_i</tex>, то он соответственно расположен и на всех уровнях <tex>L_j</tex>, где <tex>j < i</tex>. |
==Построение== | ==Построение== | ||
− | + | ||
+ | Допустим, что нам задан односвязный отсортированный список. | ||
+ | |||
[[Файл:SimpleList.png]] | [[Файл:SimpleList.png]] | ||
− | + | ||
+ | Тогда на первом уровне мы расположим заданный список, на втором <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>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>n</tex> элементов, то количество уровней в среднем будет равно <tex>\log{n}</tex>. Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{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>2</tex> | ||
+ | # Иначе закончить операцию вставки | ||
− | + | Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>. | |
+ | |||
+ | Используя монетку с распределением отличным от <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> | <code> |
Версия 23:59, 20 марта 2019
Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за
времени выполнять операции добавления, удаления и поиска элементов.Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть
на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем , то он соответственно расположен и на всех уровнях , где .Содержание
Построение
Допустим, что нам задан односвязный отсортированный список.
Тогда на первом уровне мы расположим заданный список, на втором только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем с номерами, кратными , и так далее. Такой список будет позволять в среднем за выполнять операции поиска, добавления и удаления элементов.
Функция возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
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
Функция
принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.list skipList (list l): list lvl = buildLvl(l) // Построение первого уровня while lvl.size() > 2 // Добавление следующих уровней; последний содержит не более двух элементов lvl = buildLvl (lvl) return lvl // Возвращает ссылку на начало верхнего уровня
Операции над структурой
Поиск элемента
Допустим, что в нашем списке с пропусками существуют
уровней, при этом первым уровнем будет исходный список.В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
- Начинаем поиск элемента в верхнем списке ( ), рассмотрим первый элемент
- Переходить к следующему элементу списка, пока значение в следующей ячейке меньше или равно ключу
- Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне выйти из поиска
Пример поиска числа
в списке из описания:Если в качестве случайного источника использовать честную монету, то тогда если в списке будет
элементов, то количество уровней в среднем будет равно . Тогда на последнем уровне будет не более двух элементов, а на каждом следующем будет почти в два раза больше. Тогда на каждом уровне мы проверим не более двух элементов (если бы на каком-нибудь уровне проверили три элемента, то в среднем это значило, что мы могли пройти на верхнем уровне на один элемент больше). Уровней всего , откуда вытекает оценка времени поиска элемента в .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
Вставка элемента
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
- Найти с помощью алгоритма поиска позицию, где мог бы находиться элемент.
- Вставить наш элемент в текущий уровень списка с пропусками
- Подбросить монету.
- Если выпал «Орёл» то перейти на уровень выше и вернуться к шагу
- Иначе закончить операцию вставки
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется
, на третьем уровне и т.д. На уровне у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это , на третий и т.д. Вероятность попасть на уровень равна .Используя монетку с распределением отличным от
, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением математическое ожидание количества элементов на уровне равно , на каждом следующем уровне будет в среднем в раз больше элементов. Таким образом, время поиска будет равно . Соответственно при честной монетке и уровней получаем оценку, полученную ранее. Для крайних распределений:- —
- — (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе )
Удаление элемента
Алгоритм удаления достаточно тривиален.
- Найти удаляемый элемент
- Удалить его со всех уровней
Псевдокод
Наглядный, но не очень эффективный по памяти вариант списка с пропусками.
В узлах списка хранятся:
- — следующий узел
- — тот же узел на следующем уровне
- — данные типа T
- — ключ типа 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
- Масштабируемые параллельные приоритетные очереди и словари
В вычислительной геометрии широко применяются структуры на основе списка с пропусками.
См. также
Структуры на основе списка с пропусками: