Редактирование: Список с пропусками
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 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>\mathtt{head}</tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне. |
− | Элементы односвязного списка | + | Элементы односвязного списка <tex>-</tex> вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля: |
− | * <tex>\mathtt{next}</tex> | + | * <tex>\mathtt{next}</tex> <tex>-</tex> ссылка на следующий элемент списка |
− | * <tex>\mathtt{key}</tex> | + | * <tex>\mathtt{key}</tex> <tex>-</tex> ключ, который хранится в данной вершине |
− | * <tex>\mathtt{down}</tex> | + | * <tex>\mathtt{down}</tex> <tex>-</tex> ссылка на соответственный элемент, лежащий уровнем ниже |
− | + | Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>. | |
− | |||
− | |||
− | |||
− | Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex> | ||
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня. | Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня. | ||
− | '''list''' build_lvl('''list''' lvl) | + | '''list''' build_lvl ('''list''' lvl) <font color=darkgreen>// Отсеивание нечётных элементов</font> |
− | '''list''' next_lvl | + | '''list''' next_lvl |
− | + | '''node''' i = lvl.head <font color=darkgreen>// Перебор всех элементов lvl</font> | |
− | + | '''while''' (i != ''null'') '''and''' (i != lvl.tail) | |
− | '''node''' i = lvl.head | + | 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> | |
− | '''while''' i | ||
− | |||
− | |||
− | i = i.next.next | ||
'''return''' next_lvl | '''return''' next_lvl | ||
Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе. | Функция <tex>\ \mathtt{skip\_list} \ </tex> принимает в качестве аргумента односвязный отсортированный список и возвращает новый список с пропусками, построенный на его основе. | ||
− | '''list''' skip_list('''list''' l): | + | '''list''' skip_list ('''list''' l): |
− | '''list''' lvl | + | '''list''' lvl = build_lvl(l) <font color=darkgreen>// Построение первого уровня</font> |
− | ''' | + | '''while''' lvl.size > 2 <font color=darkgreen>// Добавление следующих уровней; последний содержит не более двух элементов</font> |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
lvl = build_lvl(lvl) | lvl = build_lvl(lvl) | ||
− | '''return''' lvl | + | '''return''' lvl <font color=darkgreen>// Возвращает ссылку на начало верхнего уровня</font> |
==Операции над структурой== | ==Операции над структурой== | ||
===Поиск элемента=== | ===Поиск элемента=== | ||
− | Алгоритм поиска | + | |
+ | [[Файл:SkipListSearch.png|thumb|600px|Пример поиска числа <tex>8</tex>]] | ||
+ | |||
+ | Алгоритм поиска элементе в списке с пропусками состоит из следующих операций: | ||
# Начинаем поиск элемента в самом верхнем уровне | # Начинаем поиск элемента в самом верхнем уровне | ||
# Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | # Переходим к следующему элементу списка, пока значение в следующей ячейке меньше | ||
− | # | + | # Переместиться на один уровень вниз и перейти к шагу <tex>2</tex>. Если мы уже на первом уровне <tex>-</tex> прекратить поиск и вернуть ссылку на текущую вершину |
− | В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на | + | В конце алгоритма функция вернёт элемент, значение которого не меньше ключа <tex>\mathtt{key}</tex> или ссылку на хвост списка на первом уровне. |
− | Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). | + | Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего <tex>\log{n}</tex>, откуда вытекает оценка времени поиска элемента в <tex>O(\log{n})</tex>. |
====Псевдокод==== | ====Псевдокод==== | ||
Строка 71: | Строка 60: | ||
Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками. | Функция <tex>\mathtt{find}</tex> возвращает ссылку на элемент, значение которого не меньше <tex>\mathtt{key}</tex>. В случае, если все элементы в списке с пропусками меньше <tex>\mathtt{key}</tex>, то возвращается ссылка на конец списка с пропусками. | ||
− | '''T''' find('''node''' res, '''K''' key) | + | '''T''' find ('''node''' res, '''K''' key) |
− | '''while''' res.key < key | + | '''while''' res.key < key <font color=darkgreen>// Пока значение вершины меньше ключа</font> |
− | res = res.next | + | res = res.next() <font color=darkgreen>// Перейдём к следующей вершине в текущем уровне</font> |
− | '''if''' res.down = ''null'' | + | '''if''' res.down = ''null'' <font color=darkgreen>// Если мы находимся на первом уровне</font> |
− | '''return''' res | + | '''return''' res <font color=darkgreen>// Мы нашли искомый элемент</font> |
− | '''return''' find(res.down, key) | + | '''return''' find(res.down, key) <font color=darkgreen>// Иначе спустимся на один уровень ниже</font> |
− | Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{ | + | Для того, чтобы найти элемент с ключом <tex>\mathtt{key}</tex> в списке с пропусками <tex>\mathtt{list}</tex> необходимо запустить <tex>\mathtt{find}</tex> следующим образом |
− | find( | + | find(list.head(), key) |
===Вставка элемента=== | ===Вставка элемента=== | ||
− | + | Добавить элемент в список можно следующим образом: | |
− | # Начинаем вставку | + | # Начинаем вставку в самом верхнем уровне |
− | # | + | # На каждом уровне находим место, куда надо вставить элемент |
− | # Если мы на первом уровне | + | # Если мы на первом уровне <tex>-</tex> вставляем элемент и кидаем монету. Если выпал «Орёл», то возвращаем ссылку на только что вставленный элемент, иначе возвращаем ''null'' |
− | + | # Если мы не на первом уровне, то вызываем рекурсивно функцию от нижнего уровня, и если нам вернулась ссылка на элемент <tex>-</tex> вставляем его на текущем уровне и снова кидаем монету, иначе просто возвращаем ''null'' | |
− | |||
− | |||
− | |||
− | |||
====Псевдокод==== | ====Псевдокод==== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===Удаление элемента=== | ===Удаление элемента=== | ||
− | + | Для того, чтобы удалить элемент из списка с пропусками необходимо вызвать рекурсивную функцию, которая в каждом уровне, подобно поиску, найдёт позицию, где должен был стоять элемент. Во время рекурсии если это самый нижний уровень, то удаляем элемент из списка (не забывая при этом сохранить связность списка). Если это не это первый уровень, то рекурсивно вызовем функцию от уровня ниже, а также удалим элемент в текущем уровне. После удаления элемента могло так получить, что несколько верхних уровней перестали содержать какие-либо элементы, тогда необходимо удалить эти уровни (кроме первого), и не забыть вернуть ссылку на начало самого верхнего уровня. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Использование нечестной монеты== | ==Использование нечестной монеты== | ||
− | Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{1 | + | Вместо честной монеты с распределением <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex> можно взять в качестве случайного источника нечестную монету с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл»). Тогда математическим ожиданием количества элементов на уровне <tex>k</tex> будет <tex>n \cdot p^k</tex>. Время поиска будет равно <tex>O\left( \dfrac{1}{p} \log_{\frac{1}{p}} {n} \right)</tex> (на <tex>i</tex>-ом уровне элементов будет почти в <tex>\dfrac{1}{p}</tex> раз больше, чем на <tex>(i+1)</tex>-ом, значит на каждом уровне пройдём не более <tex>\dfrac{1}{p}</tex> элементов, а уровней всего <tex>\log_{\frac{1}{p}} {n}</tex>). |
− | |||
− | |||
Для крайних распределений: | Для крайних распределений: | ||
− | * <tex>\{0, 1\}</tex> | + | * <tex>\{0, 1\}</tex> {{---}} <tex>O(n)</tex> <tex>-</tex> поиск, добавление и удаления элемента, поскольку мы вместо нескольких списком используем по факту всего один список. |
− | * <tex>\{1, 0\}</tex> | + | * <tex>\{1, 0\}</tex> {{---}} зависит от реализации алгоритма. Если при каждой вставке у нас образуется не более одного уровня, то количество уровней будет равным <tex>n</tex>, значит время поиска будет равным <tex>O(n)</tex>. |
==Применение== | ==Применение== | ||
− | Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ | + | Список с пропусками применяется во многих приложениях, поскольку имеет ряд преимуществ. |
* Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент) | * Быстрая вставка элемента, поскольку не требуется каким-либо образом изменять другие элементы (только предыдущий элемент) | ||
* Проще реализовать, чем сбалансированные деревья или хеш-таблицы | * Проще реализовать, чем сбалансированные деревья или хеш-таблицы | ||
− | * Следующий элемент достаётся за <tex>O(1)</tex> | + | * Следующий элемент достаётся за <tex>O(1)</tex> |
* Легко модифицировать под различные задачи | * Легко модифицировать под различные задачи | ||
− | ===Нахождение всех | + | ===Нахождение всех интервалов, покрывающих данную точку=== |
− | |||
{{Задача | {{Задача | ||
− | |definition = | + | |definition = Есть <tex>q</tex> запросов двух видов: |
− | # Добавить | + | # Добавить интервал <tex>[L, R]</tex> |
− | # | + | # Задана точка <tex>x</tex>. |
− | + | На каждый запрос второго типа необходимо вывести количество интервалов, которые покрывают данную точку. | |
}} | }} | ||
− | + | Решение данной задачи заключается в том, что когда приходит запрос добавления интервала, то мы добавляем левую и правую границу (если до этого они не были добавлены). Потом идём от левой точки до правой и на пути прибавляем <tex>1</tex>. Когда нам приходит запрос второго типа, то рекурсивно спускаемся сверху вниз и суммируем все числа, лежащие на пути между двумя ближайшими вершинами, между которыми находится заданная точка. На каждый запрос мы отвечаем онлайн за <tex>O(\log{n})</tex> времени. | |
− | |||
− | |||
==См. также== | ==См. также== | ||
Строка 177: | Строка 113: | ||
*[[Поисковые структуры данных]] | *[[Поисковые структуры данных]] | ||
*[[Skip quadtree: определение, время работы|Skip quadtree]] | *[[Skip quadtree: определение, время работы|Skip quadtree]] | ||
+ | *[http://en.wikipedia.org/wiki/Skip_graph Skip graph] — структура данных, основанная на списке с пропусками | ||
==Источники информации== | ==Источники информации== |