Список с пропусками — различия между версиями
Kamensky (обсуждение | вклад) м (Увеличены дроби) |
Kamensky (обсуждение | вклад) (Исправлено определение, добавлено описание и картиночки.) |
||
Строка 1: | Строка 1: | ||
− | '''Список с пропусками''' (''skip-list'') — | + | '''Список с пропусками''' (''skip-list'') — вероятностная структура данных, основанная на нескольких отсортированных односвязных списках. |
− | Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. | + | Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до <tex>\Theta(\log(n))</tex>. |
+ | |||
+ | ==Описание== | ||
+ | Список с пропусками строится на основе существующего односвязного отсортированного списка. | ||
+ | |||
+ | [[Файл:SimpleList.png]] | ||
+ | |||
+ | Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять <tex>\Theta(\log(n))</tex>. | ||
+ | |||
+ | [[Файл:SkipList.png]] | ||
==Операции над структурой== | ==Операции над структурой== | ||
Строка 11: | Строка 20: | ||
# Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу | # Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу | ||
# Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex> | # Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex> | ||
+ | |||
+ | Пример поиска числа 8 в списке из описания: | ||
+ | |||
+ | [[Файл:SkipListSearch.png]] | ||
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы: | Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы: | ||
Строка 114: | Строка 127: | ||
*[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)] | *[http://en.wikipedia.org/wiki/Skip_list Википедия — списки с пропусками(En)] | ||
*[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками] | *[http://bit.ly/LiNe8M Курс kiev-clrs — Списки с пропусками] | ||
+ | *[http://igoro.com/archive/skip-lists-are-fascinating/ igoro.com — Skip lists are fascinating] |
Версия 04:08, 16 июня 2014
Список с пропусками (skip-list) — вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.
Отсортированный связный список является простейшей структурой с временем поиска
. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, поможет улучшить асимптотику до .Содержание
Описание
Список с пропусками строится на основе существующего односвязного отсортированного списка.
Добавив дополнительные уровни, каждый из которых представляет предыдущий уровень без нечетных элементов, мы получим возможность осуществлять поиск, вставку и удаление элементов подобно операциям с двоичным деревом поиска. Одинаковые элементы связаны между уровнями. Соответственно, асимптотика этих операций будет составлять
.Операции над структурой
Поиск элемента
Допустим, что в нашем списке с пропусками существуют два уровня:
, в котором содержатся все элементы и , в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
- Начинаем поиск элемента в верхнем левом углу
- Передвигаться будем по списку , пока значение в следующей ячейке меньше или равно ключу
- Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку
Пример поиска числа 8 в списке из описания:
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне
. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
Минимизируя, мы получаем, что
В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:
Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:
- Для трех уровней:
- Для четырех уровней:
- Для пяти уровней:
- Для уровней:
В списках с пропусками, в которых содержится
уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в списке с пропусками будет осуществляться за асимптотическое время .Вставка элемента
Для вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:
- Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент
- Вставить наш элемент в нижний уровень списка с пропусками
- «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше
- Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется
, на третьем уровне и т.д. На уровне у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это , на третий и т.д. Вероятность попасть на уровень равнаУдаление элемента
Алгоритм удаления достаточно тривиален.
- Найти удаляемый элемент
- Удалить его со всех уровней
Псевдокод
const float P = 0.5 int random_level() int lvl = (int)(log(frand())/log(1.-P)) if lvl < MAX_LEVEL return lvl return MAX_LEVEL boolean Find (int key) SkipNode x = header for i = level to 0 while x.forward[i] != NULL and x.forward[i].value < key x = x.forward[i] x = x.forward[0] return x != NULL && x.value == key void Insert(int value) SkipNode x = header SkipNode update update.assign(MAX_LEVEL + 1, 0) for i = level to 0 while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0] if x == NULL or x.value != value int lvl = random_level() if lvl > level for i = level + 1 to lvl update[i] = header level = lvl x = new SkipNode(lvl, value) for i = 0 to lvl x.forward[i] = update[i].forward[i] update[i].forward[i] = x void Erase(int value) SkipNode x = header SkipNode update update.assign(MAX_LEVEL + 1, 0) for i = level to 0 while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0] if x.value == value for i = 0 to level if update[i].forward[i] != x break update[i].forward[i] = x.forward[i]; delete x while level > 0 or header.forward[level] == NULL level--