Список с пропусками — различия между версиями
Gaporf (обсуждение | вклад) (→Использование нечестной монеты) |
Gaporf (обсуждение | вклад) (→Псевдокод) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 28: | Строка 28: | ||
'''list''' build_lvl('''list''' lvl) | '''list''' build_lvl('''list''' lvl) | ||
'''list''' next_lvl | '''list''' next_lvl | ||
− | '''node''' i = lvl.head | + | '''node''' i = lvl.head.next.next |
'''node''' cur = next_lvl.head | '''node''' cur = next_lvl.head | ||
'''while''' i <tex>\neq</tex> ''null'' '''and''' i.next <tex>\neq</tex> ''null'' | '''while''' i <tex>\neq</tex> ''null'' '''and''' i.next <tex>\neq</tex> ''null'' | ||
Строка 39: | Строка 39: | ||
'''list''' skip_list('''list''' l): | '''list''' skip_list('''list''' l): | ||
− | '''list''' lvl | + | '''list''' lvl <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 | '''while''' lvl.size > 2 | ||
lvl = build_lvl(lvl) | lvl = build_lvl(lvl) | ||
Строка 49: | Строка 55: | ||
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] | [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] | ||
− | Алгоритм поиска | + | Алгоритм поиска элемента в списке с пропусками состоит из следующих операций: |
# Начинаем поиск элемента в самом верхнем уровне | # Начинаем поиск элемента в самом верхнем уровне | ||
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | # Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | ||
− | # Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и | + | # Переместимся на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину |
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне. | В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне. | ||
Строка 132: | Строка 138: | ||
==Применение== | ==Применение== | ||
− | Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ | + | Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ: |
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент) | * Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент) | ||
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы | * Проще реализовать, чем сбалансированные деревья или хеш-таблицы | ||
Строка 141: | Строка 147: | ||
{{Задача | {{Задача | ||
− | |definition = | + | |definition = Пусть у нас есть запросы двух видов: |
− | # Добавить | + | # Добавить отрезок <tex>[L, R]</tex> |
# Для заданной точки <tex>x</tex> вычислить количество интервалов, которые её покрывают. | # Для заданной точки <tex>x</tex> вычислить количество интервалов, которые её покрывают. | ||
+ | Необходимо для каждого запроса второго типа вывести ответ. | ||
}} | }} | ||
− | Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа <tex>L</tex> и <tex>R</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.key]</tex> и <tex>[r.next.key, R]</tex>. Допустим, что на каком-то уровне у нас получилось разделить отрезок <tex>[L, R]</tex> на <tex>3</tex>. части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза и только с одной стороны, поскольку другая часть отрезка уже будет иметь чёткую границу, за которую он не переходит. Итого время обработки запроса <tex>O(\log{n})</tex>. |
+ | |||
+ | Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки <tex>x</tex>. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Очевидно, что данный тип запросов мы обрабатываем за <tex>O(\log{n})</tex>. | ||
==См. также== | ==См. также== |
Версия 08:29, 25 марта 2019
Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за
времени выполнять операции добавления, удаления и поиска элементов.Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть — на третьем и так далее, но при этом известно, что если элемент расположен на уровне
, то он также расположен на всех уровнях, номера которых меньше .Содержание
Построение
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за
времени выполнять операции добавления, удаления и поиска элементов.На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне — всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.
Псевдокод
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало
и конец . Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.Элементы односвязного списка — вершины
, у которых есть поля:- — ссылка на следующий элемент списка
- — ключ, который хранится в данной вершине
- — ссылка на соответственный элемент, лежащий уровнем ниже
Также известно, что
и .Функция
возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.list build_lvl(list lvl) list next_lvl node i = lvl.head.next.next node cur = next_lvl.head while inull and i.next 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
Функция
принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе. list skip_list(list l):
list lvl // Построение первого уровня
node i = l.head
node j = lvl.head
while j
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 // Возвращает ссылку на начало верхнего уровня
Операции над структурой
Поиск элемента
Алгоритм поиска элемента в списке с пропусками состоит из следующих операций:
- Начинаем поиск элемента в самом верхнем уровне
- Переходим к следующему элементу списка, пока значение в следующей ячейке меньше
- Переместимся на один уровень вниз и перейти к шагу . Если мы уже на первом уровне — прекратим поиск и вернём ссылку на текущую вершину
В конце алгоритма функция вернёт элемент, значение которого не меньше ключа
или ссылку на конец списка на первом уровне.Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет
уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего , откуда вытекает оценка времени поиска элемента в .Псевдокод
Функция
возвращает ссылку на элемент, значение которого не меньше . В случае, если все элементы в списке с пропусками меньше , то возвращается ссылка на конец списка с пропусками.T find(node res, K key) while res.key < key res = res.next if res.down = null // Если мы находимся на первом уровне return res // Мы нашли искомый элемент return find(res.down, key) // Иначе спустимся на один уровень ниже
Для того, чтобы найти элемент с ключом
в списке с пропусками необходимо запустить следующим образомfind(skip.head, key)
Вставка элемента
Алгоритм вставки элементов в список с пропусками состоит из следующих шагов:
- Начинаем вставку на самом верхнем уровне
- Переходим к следующему элементу списка пока значение следующей ячейки меньше ключа.
- Если мы на первом уровне — вставляем элемент. Иначе спускаемся ниже и возвращаемся к шагу .
- Кидаем монетку и если выпал «Орёл», то возвращаем ссылку на текущий элемент, иначе — null. Если мы были не на первом уровне и нам вернули null — возвращаем его без броска монетки.
Отдельно стоит обработать случай, когда вставка нового элемента увеличивает число уровней. Тогда необходимо создать ещё один отсортированный список, в котором будет всего один текущий элемент, и не забыть присвоить списку с пропусками новую ссылку на верхний уровень. Будем считать, что вставка каждого нового элемента увеличивает число уровней не более, чем на один.
Псевдокод
Функция
возвращаем ссылку на вставленный элемент в списке, в котором находится , или null, если на монете выпала «Решка».node insert(node res, K key) while res.nextnull 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 null res.next = node(key, down_node, res.next) if random(0, 1) > 0.5 // Бросок монеты return res.next return null return null
Для того, чтобы вставить элемент с ключом
в список с пропусками необходимо вызвать следующую функцию function insert_element(list skip, K key)
node res = insert(skip.head, key)
if res
null
list lvl
lvl.head.next = node(key, res, lvl.tail)
skip = lvl
Удаление элемента
Алгоритм удаления элемента выглядит следующим образом:
- Начинаем удалять элемент с верхнего уровня
- Переходим к следующему элементу, пока значение следующего элемента меньше ключа
- Если элемент существует на данном уровне — удаляем его с этого уровня. Если мы не на первом уровне, то удаляем элемент ещё с нижнего уровня.
Псевдокод
function delete(node res, K key) while res.nextnull and res.next.key < key res = res.next if res.down null delete(res.down, key) if res.next null and res.next.key = key res.next = res.next.next;
Использование нечестной монеты
Вместо честной монеты с распределением
можно взять в качестве случайного источника нечестную монету с распределением (с вероятностью выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне будет . Время поиска будет равно на -ом уровне элементов будет почти в раз больше, чем на -ом, значит на каждом уровне пройдём не более элементов, а уровней всего .Для крайних распределений:
- — — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списков используем по факту один.
- — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным , значит время поиска будет равным .
Применение
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ:
- Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
- Проще реализовать, чем сбалансированные деревья или хеш-таблицы
- Следующий элемент достаётся за (при условии, что у нас есть ссылка не текущий)
- Легко модифицировать под различные задачи
Нахождение всех интервалов, покрывающих данную точку
Задача: |
Пусть у нас есть запросы двух видов:
|
Для решения данной задачи воспользуемся списком с пропусками. Когда нам приходит запрос первого типа, то мы просто добавляем числа и в список с пропусками (если какое-то из чисел уже было добавлено, то второй раз мы его не добавляем). После этого идём с верхнего уровня, и на каждом уровне мы ищем такие и , что значение не больше , а значение следующего за элемента уже больше . Аналогично ищем такое же , только относительно . Если значения и лежат полностью внутри отрезка , то к самому отрезку прибавляем , а сам отрезок разбиваем на два и по отдельности прибавляем уже отрезки и . Допустим, что на каком-то уровне у нас получилось разделить отрезок на . части. Но тогда на следующих уровнях мы будем уменьшать отрезок почти в два раза и только с одной стороны, поскольку другая часть отрезка уже будет иметь чёткую границу, за которую он не переходит. Итого время обработки запроса .
Для запросов второго типа мы снова будем спускать с верхнего уровня до нижнего. На каждом уровне найдём тот элемент, значение которого не меньше точки
. Если такой элемент нашёлся, то прибавляем к ответу значение на отрезку между найденным элементом и следующим. Потом также спускаемся на один уровень вниз, если текущий уровень не был первым. Очевидно, что данный тип запросов мы обрабатываем за .См. также
- Список
- Рандомизированное бинарное дерево поиска
- Поисковые структуры данных
- Skip quadtree
- Skip graph — структура данных, основанная на списке с пропусками