Список с пропусками — различия между версиями
Gaporf (обсуждение | вклад) |
Gaporf (обсуждение | вклад) (→Поиск элемента) |
||
(не показано 11 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
'''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов. | '''Список с пропусками''' (англ. ''skip list'') — вероятностная структура данных, позволяющая в среднем за <tex>O(\log(n))</tex> времени выполнять операции добавления, удаления и поиска элементов. | ||
− | Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов | + | Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на уровне <tex>i</tex>, то он также расположен на всех уровнях с номерами меньших <tex>i</tex>. |
==Построение== | ==Построение== | ||
Строка 11: | Строка 11: | ||
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов. | Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за <tex>O(\log{n})</tex> времени выполнять операции добавления, удаления и поиска элементов. | ||
− | На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те | + | На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне <tex>-</tex> всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни. |
====Псевдокод==== | ====Псевдокод==== | ||
− | Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>head</tex> и конец <tex>tail</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне. | + | Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало <tex>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне. |
− | Элементы односвязного списка | + | Элементы односвязного списка <tex>-</tex> вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля: |
− | * <tex>next</tex> <tex>-</tex> ссылка на следующий элемент списка | + | * <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент списка |
− | * <tex>key</tex> <tex>-</tex> ключ, который хранится в данной вершине | + | * <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине |
− | * <tex>down</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже | + | * <tex>\mathtt{down}</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже |
+ | Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>. | ||
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня. | Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня. | ||
Строка 27: | Строка 28: | ||
'''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> | '''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> | ||
'''list''' next_lvl | '''list''' next_lvl | ||
− | '''node''' i = lvl.head | + | '''node''' i = lvl.head |
− | '''while''' (i != ''null'') '''and''' (i != lvl.tail | + | '''while''' (i != ''null'') '''and''' (i != lvl.tail) |
next_lvl.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> | ||
Строка 37: | Строка 38: | ||
'''list''' skip_list ('''list''' l): | '''list''' skip_list ('''list''' l): | ||
'''list''' lvl = build_lvl(l) <font color=darkgreen>// Построение первого уровня</font> | '''list''' lvl = build_lvl(l) <font color=darkgreen>// Построение первого уровня</font> | ||
− | '''while''' lvl.size | + | '''while''' lvl.size > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font> |
− | lvl = build_lvl (lvl) | + | lvl = build_lvl(lvl) |
'''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font> | '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font> | ||
Строка 46: | Строка 47: | ||
[[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] | [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] | ||
− | + | Алгоритм поиска элементе в списке с пропусками состоит из следующих операций: | |
− | + | # Начинаем поиск элемента в самом верхнем уровне | |
− | |||
− | |||
− | # Начинаем поиск элемента в самом верхнем | ||
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | # Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | ||
− | # Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже | + | # Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> прекратить поиск и вернуть ссылку на текущую вершину |
− | В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>key</tex> или ссылку на | + | В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на конец списка на первом уровне. |
Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>. | Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>. | ||
Строка 64: | Строка 62: | ||
'''T''' find ('''node''' res, '''K''' key) | '''T''' find ('''node''' res, '''K''' key) | ||
'''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font> | '''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font> | ||
− | res = res.next | + | res = res.next <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font> |
'''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> | '''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> | ||
'''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> | '''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> | ||
'''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font> | '''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font> | ||
− | Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{ | + | Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{skip}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом |
− | find( | + | find(skip.head, key) |
===Вставка элемента=== | ===Вставка элемента=== | ||
− | + | Добавить элемент в список можно следующим образом: | |
+ | # Начинаем вставку в самом верхнем уровне | ||
+ | # На каждом уровне находим место, куда надо вставить элемент | ||
+ | # Если мы на первом уровне <tex>-</tex> вставляем элемент и кидаем монету. Если выпал «Орёл», то возвращаем ссылку на только что вставленный элемент, иначе возвращаем ''null'' | ||
+ | # Если мы не на первом уровне, то вызываем рекурсивно функцию от нижнего уровня, и если нам вернулась ссылка на элемент <tex>-</tex> вставляем его на текущем уровне и снова кидаем монету, иначе просто возвращаем ''null'' | ||
+ | |||
+ | ====Псевдокод==== | ||
===Удаление элемента=== | ===Удаление элемента=== | ||
− | + | Алгоритм удаления элемента выглядит следующим образом: | |
+ | # Начинаем удалять элемент с верхнего уровня | ||
+ | # Если мы на первом уровне и нашли элемент <tex>-</tex> то просто удаляем элемент | ||
+ | # Иначе спускаемся ниже и также удаляем элемент с текущего уровня, если он есть | ||
+ | ====Псевдокод==== | ||
==Использование нечестной монеты== | ==Использование нечестной монеты== | ||
Строка 83: | Строка 91: | ||
Для крайних распределений: | Для крайних распределений: | ||
− | * <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex> | + | * <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex> <tex>-</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списком используем по факту всего один список. |
− | * <tex>\{1, 0\}</tex> {{---}} <tex> | + | * <tex>\{1, 0\}</tex> {{---}} зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>. |
==Применение== | ==Применение== | ||
Строка 95: | Строка 103: | ||
===Нахождение всех интервалов, покрывающих данную точку=== | ===Нахождение всех интервалов, покрывающих данную точку=== | ||
− | + | {{Задача | |
− | + | |definition = Есть <tex>q</tex> запросов двух видов: | |
# Добавить интервал <tex>[L, R]</tex> | # Добавить интервал <tex>[L, R]</tex> | ||
− | # Задана точка <tex>x</tex>. | + | # Задана точка <tex>x</tex>. |
− | + | На каждый запрос второго типа необходимо вывести количество интервалов, которые покрывают данную точку. | |
+ | }} | ||
− | Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. | + | Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. На каждый запрос мы отвечаем онлайн за <tex>O(\log{n})</tex> времени. |
==См. также== | ==См. также== |
Версия 22:47, 23 марта 2019
Список с пропусками (англ. skip list) — вероятностная структура данных, позволяющая в среднем за
времени выполнять операции добавления, удаления и поиска элементов.Список с пропусками состоит из нескольких уровней, на каждом из которых находится отсортированный связный список. На самом нижнем (первом) уровне располагаются все элементы. Дальше около половины элементов в таком же порядке располагаются на втором, почти четверть
на третьем и так далее, но при этом известно, что если элемент расположен на уровне , то он также расположен на всех уровнях с номерами меньших .Содержание
Построение
Допустим, что нам задан односвязный отсортированный список и мы хотим построить на его основе список с пропусками, позволяющий в среднем за
времени выполнять операции добавления, удаления и поиска элементов.На самом нижнем уровне списка с пропусками мы расположим исходный список. На втором уровне
всё элементы с чётными номерами, причём каждый элемент будет ссылаться на соответствующий ему элемент на нижнем уровне. Таким же образом построим и третий уровень, куда будем добавлять только те элементы, номера которых кратны четырём. Аналогичным образом построим и последующие уровни.Псевдокод
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которое есть начало
и конец . Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.Элементы односвязного списка
вершины , у которых есть поля:- ссылка на следующий элемент списка
- ключ, который хранится в данной вершине
- ссылка на соответственный элемент, лежащий уровнем ниже
Также известно, что
и .Функция
возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.list build_lvl (list lvl) // Отсеивание нечётных элементов list next_lvl node i = lvl.head 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
Функция
принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе.list skip_list (list l): list lvl = build_lvl(l) // Построение первого уровня 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
Псевдокод
Удаление элемента
Алгоритм удаления элемента выглядит следующим образом:
- Начинаем удалять элемент с верхнего уровня
- Если мы на первом уровне и нашли элемент то просто удаляем элемент
- Иначе спускаемся ниже и также удаляем элемент с текущего уровня, если он есть
Псевдокод
Использование нечестной монеты
Вместо честной монеты с распределением
можно взять в качестве случайного источника нечестную монету с распределением (с вероятностью выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне будет . Время поиска будет равно (на -ом уровне элементов будет почти в раз больше, чем на -ом, значит на каждом уровне пройдём не более элементов, а уровней всего ).Для крайних распределений:
- — поиск, добавление и удаления элемента, поскольку мы вместо нескольких списком используем по факту всего один список.
- — зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным , значит время поиска будет равным .
Применение
Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ.
- Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент)
- Проще реализовать, чем сбалансированные деревья или хеш-таблицы
- Следующий элемент достаётся за
- Легко модифицировать под различные задачи
Нахождение всех интервалов, покрывающих данную точку
Задача: |
Есть
| запросов двух видов:
Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем . Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. На каждый запрос мы отвечаем онлайн за времени.
См. также
- Список
- Рандомизированное бинарное дерево поиска
- Поисковые структуры данных
- Skip quadtree
- Skip graph — структура данных, основанная на списке с пропусками