Главная » Java, Структуры данных и алгоритмы » Skip-список

0

Интересной разновидностью структуры данных эффективной реализации АТД «упорядоченный словарь» является skip^cnucoK (skip list). Эта структура данных организует объекты в произвольном порядке таким

образом, что поиск и обновление в среднем выполняются за 0(log п) времени, где п — количество объектов словаря. Интересно, что понятие усредненной временной сложности, используемое здесь, не зависит от возможного распределения ключей при вводе. Наоборот, оно продиктовано использованием генераторов случайных чисел в реализации процесса ввода, чтрбы облегчить процесс принятия решения о месте вставки нового объекта. Время выполнения в этом случае будет равно среднему значению времени выполнения ввода любых случайных чисел, используемых в качестве входных объектов.

Методы генерации случайных чисел встраиваются в большинство современных компьютеров, поскольку они широко применяются в компьютерных играх, криптографии и компьютерных симуляторах. Некоторые методы, называемые генераторами псевдослучайных чисел (pseudorandom number generators), генерируют псевдослучайно числа по некоторому закону, начиная с так называемого начального числа (seed). Другие методы используют аппаратные средства для извлечения «действительно» случайных чисел. В любом случае компьютер имеет числа, отвечающие требованиям, предъявляемым к случайным числам в приводимом анализе.

Основным преимуществом использования случайных чисел в струк- > туре данных и при создании алгоритма является простота и надежность результативных структур и методов. Таким образом можно-создать простую рандомизированную структуру данных, называемую skip-список, обеспечивающую логарифмические затраты времени для поиска, аналогичные затратам при использовании бинарного поискового алгоритма. Тем не менее предполагаемые временные затраты при skip-списке будут большими, чем у бинарного поиска в поисковой таблице. С другой стороны, при словарном обновлении skip-список намного быстрее поисковых таблиц.

Пусть skip-список S для словаря D состоит из серии списков {iSo, S\, Si, З/j}. Каждый список S\ хранит набор объектов словаря D по ключам в неубывающей последовательности плюс объекты с двумя специальными ключами, записываемыми в виде «-оо» и «+оо», где «-оо» обозначает меньше, а «+оо» — больше любого возможного ключа, который может быть в D. Кроме того, списки в Sотвечают следующим требованиям:

•          список S0 содержит каждый объект словаря D (плюс специальные объекты с ключами «-оо» и «+оо»);

•          для / = 1, …, h – 1 список Si содержит (в дополнение к «-оо» и «+оо») случайно сгенерированный набор объектов из списка St_ ь

•          список Sh содержит только «-оо» и «+оо».

Образец такого skip-списка приведен на рис. 8.9, наглядно представляющем списодс S со списком в основании и списками S\, …, S^ над ним. Высоту (height) списка S обозначим как h.

Рис. 8.9. Пример skip-списка

Интуитивно списки организованы таким образом; чтобы ?/+/ содержал хотя бы каждый второй объект 5/. Как будет показано при рассмотрении метода ввода, объекты в St+\ выбираются произвольно из объектов в Si с таким расчетом, чтобы каждый выбираемый объект 5/ входил в 5/ + \ с вероятностью 1/2. Образно говоря, помещать или нет объект из в Si + 1, определяем в зависимости от того, какой стороной упадет подкидываемая монетка — орлом или решкой. Таким образом, можно считать, что S\ содержит около я/2 объектов, S2 — я/4, и, соответственно, Sj — около п/2′ объектов. Другими словами, высота h списка S может составлять около logn. Хотя при этом деление пополам числа объектов от одного списка к другому не является обязательным требованием в виде явно выраженного свойства skip-списка. Наоборот, случайный выбор важнее.

Используя позиционную абстракцию применительно к спискам и деревьям, можно рассматривать skip-список как двухмерную коллекцию позиций, организованных горизонтально в уровни (levels) и вертикально в башни (towers). Каждый уровень — это список S^ а каждая башня — набор позиций, хранящих один и тот же объект и расположенных друг над другом в списках. Позиции skip-списка можно проходить с помощью следующих операций:

after(/?): возвращает позицию, следующую за р ца том же уровне; before(/?): возвращает позицию, предшествующую р на том же уровне; below(/?): возвращает позицию, расположенную под р в той же башне; above(/?): возвращает позицию, расположенную над р в той же башне.

Установим, что перечисленные выше операции должны возвращать null, если запрашиваемой позиции не существует. Не вдаваясь в подробности, заметим, что skip-список легко реализуется с помощью связной структуры таким образом, что методы прохода требуют 0(1) времени (при наличии в списке позиции р). Такая связная структура представляет собой коллекцию из h двусвязных списков, объедийёйй^ й^айШ, в свою очередь являющиеся двусвязными списками.

Поиск

Структура skip-списка позволяет применять простые поисковые алгоритмы для словарей. В действительности все поисковые алгоритмы skip-списка основываются на достаточно элегантном методе SkipSearch, принимающем ключ к и находящим объект в skip-списке S с наибольшим ключом (который может оказаться «-оо»), меньшим или равным к. Допустим, имеется искомый ключ к. Метод SkipSearch устанавливает позицию р в самой верхней левой позиции в skip-списке S. То есть р устанавливается на позиции специального объекта с ключом «-оо» в S^. Затем выполняется следующее:

1)      если S.below(/?) равен null, то поиск заканчивается — на уровень ниже обнаружен наибольший объект в Sс ключом, меньшим или равным искомому ключу к. В противном случае опускаемся на один уровень в данной башне, устанавливая р S.be\ow(p);

2)      из позиции р продвигаемся вправо (вперед) до тех пор, пока не окажемся в крайней правой позиции текущего уровня, где кеу(/?) < к. Такой шаг называется сканированием вперед (scan forward). Указанная позиция существует всегда, поскольку каждый уровень имеет специальные ключи «+оо» и «-оо». И на самом деле, после шага вправо по текущему уровню р может остаться на исходном месте. В любом случае после этого снова повторяется предыдущее действие.

Рис. 8.10. Пример поиска в skip-списке. Обследованные во время поиска ключа 50 позиции выделены штриховым обозначением

Фрагмент кода 8.4 содержит описание поискового алгоритма skip-списка. Имея такой метод, несложно реализовать операцию findElement(/:). Выполняется операция р^- SkipSearch(A;) и проверяется равенство key{p)~ k. При ^равенстве возвращается /?.element. В противном случае возвращается сигнальное сообщение NO_SUCH_KEY.

Алгоритм SkipSearch(/:):

Input: поисковый кл?оч к.

Output: позиция р в S, объект которой имеет наибольший ключ, меньший или равный к.

Допустим, что р — самая верхняя левая позиция в S (состоящей как минимум из двух уровней), while below (р) * null do

р below(p) {просканировать вниз} while key(after(p)) < к do

Let p after(p) {просканировать вперед} return p

Фрагмент кода 8.4. Алгоритм поиска в skip-списке S

Оказывается, предполагаемое время выполнения алгоритма SkipSearch составляет 0(log п). Прежде чем обосновать это, приведем реализацию методов обновления skip-списка

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии