Список с пропусками

Список с пропусками (англ. Skip List) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций).

Вставка элемента в список с пропусками

В основе списка с пропусками лежит расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением[1], таким образом, чтобы поиск по списку мог быстро пропускать части этого списка. Вставка, поиск и удаление выполняются за логарифмическое случайное время.

Описание

Список с пропусками — это несколько слоев. Нижний слой — это обычный упорядоченный связный список. Каждый более высокий слой представляет собой «выделенную полосу движения» для списков ниже, где элемент в i-м слое появляется в i+1-м слое с некоторой фиксированной вероятностью p (два наиболее часто используемых значений для p — 1/2 и 1/4). В среднем каждый элемент встречается в 1/(1-p) списках, и верхний элемент (обычно специальный головной элемент в начале списка с пропусками) в списках.

Поиск нужного элемента начинается с головного элемента верхнего списка, и выполняется горизонтально до тех пор, пока текущий элемент не станет больше либо равен целевому. Если текущий элемент равен целевому, он найден. Если текущий элемент больше, чем целевой, процедура повторяется после возвращения к предыдущему элементу и спуска вниз вертикально на следующий нижележащий список. Ожидаемое число шагов в каждом связном списке 1/p, что можно увидеть, просматривая путь поиска назад с целевого элемента, пока не будет достигнут элемент, который появляется в следующем более высоком списке. Таким образом, общие ожидаемые затраты на поиск — , равные в случае константного p. Выбирая разные значения p, возможно выбирать необходимый компромисс между затратами на время поиска и затратами памяти на хранение списка.

Детали реализации

Элементы, используемые в списке с пропусками, могут содержать более одного указателя, таким образом они могут состоять в более чем одном списке.

Операции удаления и вставки реализованы весьма похоже на аналогичные операции связного списка, с тем исключением, что «высокие» должны быть вставлены или удалены более чем из одного связного списка.

Однако без рандомизации эти операции приводили бы к очень низкой производительности, так как необходимо было бы полностью перетасовывать список при добавлении нового элемента, чтобы сохранить число пропусков на верхнем уровне константным. William Pugh предложил следующий алгоритм для решения, на какую высоту должен быть продвинут новый элемент. Этот алгоритм требует лишь локальных изменений списка при добавлении новых элементов и позволяет сохранять эффективность «экспресс-линий» (l — результирующее значение уровня, на который нужно помещать элемент):

l = 1
пока случайное значение в диапазоне [0,1] < p и l < максимального уровня
  l = l + 1

В итоге элемент вставляет на l-й уровень и, соответственно, на все уровни меньше l.

Θ(n) операций, которые необходимы нам для посещения каждого узла в возрастающем порядке (например, печать всего списка), предоставляют возможность выполнить незаметную дерандомизацию структуры уровней списка с пропусками оптимальным путём, достигая времени поиска для связного списка. (выбирая уровень i-го конечного узла 1 плюс количество раз, которое мы можем поделить i на 2, пока оно не станет нечетным. Также i=0 для отрицательно бесконечного заголовка, как мы имеем, обычный специальный случай, выбирая максимально возможный уровень для отрицательных и/или положительных бесконечных узлов.) Тем не менее, это позволяет узнать кому-нибудь, где все узлы с уровнем более 1, и затем удалить их.

В качестве альтернативы мы можем сделать структуру уровней квази-случайной следующим путём:

создать все узлы уровня 1
j = 1
пока количество узлов на уровне j > 1
  для каждого i-го узла на уровне j
    если i нечетное 
      если i не последний узел на уровне j
        случайно выбираем, продвигать ли его на уровень j+1
      иначе
        не продвигать
      конец условия
    иначе, если i четный узел i-1 не продвинут
      продвинуть его на уровень j+1
    конец условия
  конец цикла для
  j = j + 1
конец цикла пока

Так же, как дерандомизированная версия, квази-рандомизация выполняется только, когда есть какая-то другая причина выполнять Θ(n) операций (которые посетят каждый узел).

Пример реализации

Примечания

  1. Pugh, William. Skip lists: a probabilistic alternative to balanced trees (англ.) // Communications of the ACM : journal. — 1990. — June (vol. 33, no. 6). P. 668—676. doi:10.1145/78973.78977.

Литература

  • William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees / Workshop on Algorithms and Data Structures. Springer Berlin Heidelberg, 1989; Communications of the ACM CACM Homepage archive Volume 33 Issue 6, June 1990 Pages 668-676 doi:10.1145/78973.78977 — оригинальная работа
  • Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. Вильямс, 2011. — 512 с. — ISBN 978-5-8459-1623-5.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.