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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Вставка элемента в список с пропусками

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

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

Описание[править | править вики-текст]

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

Skip list.svg

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

Детали реализации[править | править вики-текст]

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

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

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

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

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

Θ(n) операций, которые необходимы нам для посещения каждого узла в возрастающем порядке (например печать всего списка), предоставляют возможность выполнить незаметную дерандомизацию структуры уровней списка с пропусками оптимальным путем, достигая \mathcal{O}(\log 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 (June 1990). «Skip lists: a probabilistic alternative to balanced trees». Communications of the ACM 33 (6): 668–676. DOI:10.1145/78973.78977.

Ссылки[править | править вики-текст]