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

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

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

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

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

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

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

Список S h содержит только «-оо» и «+оо».

Образец такого 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-списка

В предыдущих статьях (раз , два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N) , где N - число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N .
Или все же представляет?..

Существует довольно любопытная структура данных - skip-list , основанная на обычном односвязном списке. Впервые она была описана в 1990 году W.Pugh, перевод его оригинальной статьи есть на хабре. Эта структура представляет для нас интерес, так как, имея алгоритм lock-free ordered list, довольно легко реализовать lock-free skip-list.
Для начала - немного о принципах построения skip-list. Skip-list представляет собой многоуровневый список: каждый элемент (иногда называемый башней, tower) имеет некоторую высоту h .


Высота h выбирается случайным образом из диапазона , где Hmax - максимально возможная высота, обычно 16 или 32. Вероятность того, что высота башни равна единице, есть P = 1/2 . Вероятность высоты k есть:

Несмотря на кажущуюся сложность вычисления высоты, её можно рассчитать довольно просто, например, так: h = lsb(rand()) , где lsb - номер младшего значащего бита числа.

Magic 1/2

На самом деле, константа 1/2 - это мое упрощение, в оригинальной статье идет речь о 0 < p < 1 и исследуется поведение skip-list при различных значениях p . Но для практической реализации p = 1/2 - наилучшее значение, мне кажется.

Получается, что чем больше уровень, тем более список на этом уровне разрежен по сравнению с нижележащими. Эта разреженность наряду с вероятностной природой дает оценку сложности поиска O(log N) , - такую же, как для бинарных самобалансирующихся деревьев.
Поиск в skip-list"е довольно прост: начиная с head-башни, которая имеет максимальную высоту, проходим по самому верхнему уровню, пока не найдем элемент с ключом больше искомого (или не упремся в хвост tail), спускаемся на уровень ниже, ищем аналогично в нем и т.д., пока не попадем на уровень 0, самый нижний; пример поиска ключа 34:

Lock-free skip list

Для построения lock-free skip-list у нас уже есть lock-free алгоритм для каждого уровня. Осталось разработать приемы работы с уровнями. Казалось бы, невозможно атомарно вставить узел-башню высотой, скажем, 20, - ведь для этого нужно атомарно поменять 20 указателей! Оказывается, этого и не нужно, достаточно уметь атомарно менять один указатель, - то, что мы уже умеем делать в lock-free list.
Рассмотрим, как происходит вставка в lock-free skip-list. Будем вставлять элемент-башню высотой 5 с ключом 23. Первым этапом мы ищем позицию вставки, двигаясь по уровням сверху вниз. В результате у нас получается массив prev позиций вставки на каждом уровне:


Далее, вставляем новый элемент на уровень 0, самый нижний. Вставку в lock-free список мы уже умеем делать:


Всё, - элемент становится частью списка, его можно найти, он становится достижимым , несмотря на то, что вся башня целиком ещё не вставлена в skip-list.
Далее мы не торопясь вставляем нашу башню на уровни выше, снизу вверх:


Эти вставки имеют уже второстепенное значение, призваны повысить эффективность поиска, но никак не влияют на принципиальную достижимость нового ключа.
Удаление элемента происходит в две фазы: сначала мы находим удаляемый элемент и помечаем его как логически удаленный, используя прием marked pointer. Сложность в том, что для башни мы должны пометить все уровни элемента, начиная с самого верхнего:


После того, как все уровни элемента-башни помечены, делается физическое удаление (точнее говоря, исключение элемента из списка, так как удаление памяти под элемент выполняется Hazard Pointer или RCU), также сверху вниз:


На каждом уровне применяется алгоритм вставки/удаления из обычного lock-free ordered list, который мы уже рассматривали.

Как видим, процедуры вставки/удаления из lock-free skip-list многошаговые, на каждом шаге возможна интерференция с конкурирующими операциями, поэтому при программировании skip-list нужна особая аккуратность. Например, при вставке мы сначала ищем позиции в списках на всех уровнях и формируем массивы prev . Вполне возможно, что в процессе вставки список на каком-то уровне изменится и эти позиции станут невалидными. В этом случае следует обновить prev , то есть найти вставляемый элемент, и продолжить вставку, начиная с уровня, на котором произошел облом.
Более интересна ситуация, когда происходит одновременная вставка ключа K и его удаление. Такое вполне возможно: вставка считается успешно выполненной, когда мы связали элемент на уровне 0 списка. После этого элемент уже достижим и его вполне можно удалить, несмотря на то, что он ещё не до конца вставлен в верхние уровни. Для разрешения коллизии вставки и удаления очень важен порядок: вставка производится снизу вверх, а удаление (точнее, его первая фаза - логическое удаление, marked pointer) - противоходом, сверху вниз. В таком случае процедура вставки обязательно увидит на каком-либо уровне метку удаления и немедленно прекратит свою работу.
Процедура удаления также может быть конкурентной на обоих своих фазах. На фазе логического удаления, когда проставляются метки на башне сверху вниз, нам конкуренция не страшна. А вот на фазе исключения удаляемого элемента из списков любое изменение skip-list"а, то есть нарушение массивов prev и found , определяющих позицию удаляемого элемента, приводит к тому, что нам надо эти массивы сформировать заново. Но метки уже проставлены и функция поиска просто не найдет удаляемый элемент! Для разрешения этой ситуации мы наделяем функцию поиска несвойственной ей работой: при обнаружении помеченного на каком-либо уровне элемента функция поиска исключает (unlink) этот элемент из списка этого уровня, то есть помогает удалять элементы. После исключения функция возобновляет поиск с самого начала, то есть с самого верхнего уровня (здесь возможны вариации, но самое простое - начать с начала). Это типичный пример взаимопомощи, часто встречающийся в lock-free программировании: один поток помогает другому делать его работу. Именно поэтому функция find() во многих lock-free контейнерах не является константной - поиск может изменить контейнер.
Чем ещё характеризуется skip-list? Во-первых, это упорядоченный map, в отличие от hash map, то есть поддерживает операции извлечения минимального extract_min() и максимального extract_max() ключей.
Во-вторых, skip-list прожорлив для схемы Hazard Pointrer (HP): при максимальной высоте башни 32 элементы массивов prev и found , определяющих искомую позицию, должны быть защищены hazard pointer"ами, то есть нам требуется минимум 64 hazard pointer"а (на самом деле, в реализации libcds – 66). Это довольно много для схемы HP, см. подробнее её устройство . Для схемы RCU некоторую сложность представляет реализация метода find() , так как этот метод может удалять элементы, а схема RCU требует, чтобы удаление исключение (unlink) элемента из списка было под критической секцией RCU, а удаление деаллокация памяти - вне критической секции, иначе возможен deadlock.
Интересную практическую задачу представляет собой реализация башен для высоты более 1. Сейчас в реализации skip-list в библиотеке libcds память под башни высотой более 1 распределяется отдельно от памяти под элемент даже для интрузивного варианта. Учитывая вероятностную природу высоты, получается, что для 50% элементов делается распределение памяти, - это может сказаться на производительности, а также негативно влияет на фрагментацию памяти. Есть задумка башни высотой не более h_min распределять одним блоком и только для высоких «дораспределять» память под башню:
template struct tower { tower * next; tower * high_next; // массив для указателей уровней >= Hmin };
Если Hmin = 4 , то при таком построении 93% элементов не потребуют распределения дополнительной памяти под указатели next - high_next для них будет nullptr .

skip-list: библиография

W.Pugh спустя год-два после опубликования своей работы о skip-list представил другую работу, посвященную конкурентной реализации, основанной на аккуратной расстановке блокировок (fine-grained locks).
Наиболее цитируемая работа по lock-free skip-list – это диссертация K.Fraser Practical lock-freedom 2003 года, в которой представлено несколько алгоритмов skip-list как на основе транзакционной памяти, так и на программной реализации MCAS (CAS над несколькими ячейками памяти). Эта работа представляет сейчас, на мой взгляд, чисто теоретический интерес, так как программная эмуляция транзакционной памяти довольно тяжела, равно как и MCAS. Хотя с выходом Haswell реализация транзакционной памяти в железе пошла в массы…
Реализация skip-list в libcds сделана по мотивам неоднократно цитируемой мною монографии The Art of Multiprocessor Programming . «По мотивам» потому, что оригинальный алгоритм приведен для Java и имеет, как мне кажется, несколько ошибок, которые, быть может, были исправлены во втором издании. Или это вовсе не ошибки для Java.
Есть ещё диссертация Фомичева , посвященная вопросу возобновления поиска в случае обнаруженных конфликтов в skip-list. Как я упоминал выше, find() при обнаружении помеченного (marked) элемента пытается удалить его из списка и возобновляет поиcк с самого начала . Фомичев предлагает механизм расстановки back-reference – обратных ссылок, чтобы работу возобновлять с некоторого предыдущего элемента, а не с начала, что, в принципе, должно повлиять на производительность в лучшую сторону. Алгоритм поддержки back-reference в актуальном состоянии довольно сложный и непонятно, будет ли выигрыш или же его съест код поддержки актуальности.

В следующей статье попытаемся рассмотреть другой обширный класс структур данных, являющихся основой для ассоциативных контейнеров, - деревья, точнее, их конкурентную реализацию.

Списки с пропусками - это структура данных, которая может применяться вместо сбалансированных деревьев. Благодаря тому, что алгоритм балансировки вероятностный, а не строгий, вставка и удаление элемента в списках с пропусками реализуется намного проще и значительно быстрее, чем в сбалансированных деревьях.

Списки с пропусками - это вероятностная альтернатива сбалансированным деревьям. Они балансируются с использованием генератора случайных чисел. Несмотря на то, что у списков с пропусками плохая производительность в худшем случае, не существует такой последовательности операций, при которой бы это происходило постоянно (примерно как в алгоритме быстрой сортировки со случайным выбором опорного элемента). Очень маловероятно, что эта структура данных значительно разбалансируется (например, для словаря размером более 250 элементов вероятность того, что поиск займёт в три раза больше ожидаемого времени, меньше одной миллионной).

Балансировать структуру данных вероятностно проще, чем явно обеспечивать баланс. Для многих задач списки пропуска это более естественное представление данных по сравнению с деревьями. Алгоритмы получаются более простыми для реализации и, на практике, более быстрыми по сравнению со сбалансированными деревьями. Кроме того, списки с пропусками очень эффективно используют память. Они могут быть реализованы так, чтобы на один элемент приходился в среднем примерно 1.33 указатель (или даже меньше) и не требуют хранения для каждого элемента дополнительной информации о балансе или приоритете.

Для поиска элемента в связном списке мы должны просмотреть каждый его узел:

Если список хранится отсортированным и каждый второй его узел дополнительно содержит указатель на два узла вперед, нам нужно просмотреть не более, чем ⌈n /2⌉ + 1 узлов(где n - длина списка):

Аналогично, если теперь каждый четвёртый узел содержит указатель на четыре узла вперёд, то потребуется просмотреть не более чем ⌈n /4⌉ + 2 узла:

Если каждый 2 i i узлов вперёд, то количество узлов, которые необходимо просмотреть, сократится до ⌈log 2 n ⌉, а общее количество указателей в структуре лишь удвоится:

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

Назовём узел, содержащий k указателей на впередистоящие элементы, узлом уровня k . Если каждый 2 i -ый узел содержит указатель на 2 i узлов вперёд, то уровни распределены так: 50% узлов - уровня 1, 25% - уровня 2, 12.5% - уровня 3 и т.д. Но что произойдёт, если уровни узлов будут выбираться случайно, в тех же самых пропорциях? Например, так:

Указатель номер i каждого узла будет ссылаться на следующий узел уровня i или больше, а не на ровно 2 i -1 узлов вперёд, как было до этого. Вставки и удаления потребуют только локальных изменений; уровень узла, выбранный случайно при его вставке, никогда не будет меняться. При неудачном назначении уровней производительность может оказаться низкой, но мы покажем, что такие ситуации редки. Из-за того, что эти структуры данных представляют из себя связные списки с дополнительными указателями для пропуска промежуточных узлов, я называю их списками с пропусками .

Операции

Опишем алгоритмы для поиска, вставки и удаления элементов в словаре, реализованном на списках с пропусками. Операция поиска возвращает значение для заданного ключа или сигнализирует о том, что ключ не найден. Операция вставки связывает ключ с новым значением (и создаёт ключ, если его не было до этого). Операция удаления удаляет ключ. Также в эту структуру данных можно легко добавить дополнительные операции, такие как «поиск минимального ключа» или «нахождение следующего ключа».

Каждый элемент списка представляет из себя узел, уровень которого был выбран случайно при его создании, причём независимо от числа элементов, которые уже находились там. Узел уровня i содержит i указателей на различные элементы впереди, проиндексированные от 1 до i . Мы можем не хранить уровень узла в самом узле. Количество уровней ограничено заранее выбранной константой MaxLevel . Назовём уровнем списка максимальный уровень узла в этом списке (если список пуст, то уровень равен 1). Заголовок списка (на картинках он слева) содержит указатели на уровни с 1 по MaxLevel . Если элементов такого уровня ещё нет, то значение указателя - специальный элемент NIL.

Инициализация

Создадим элемент NIL, ключ которого больше любого ключа, который может когда-либо появиться в списке. Элемент NIL будет завершать все списки с пропусками. Уровень списка равен 1, а все указатели из заголовка ссылаются на NIL.

Поиск элемента

Начиная с указателя наивысшего уровня, двигаемся вперед по указателям до тех пор, пока они ссылаются на элемент, не превосходящий искомый. Затем спускаемся на один уровень ниже и снова двигаемся по тому же правилу. Если мы достигли уровня 1 и не можем идти дальше, то мы находимся как раз перед элементом, который ищем (если он там есть).

Search (list, searchKey)
x:= list→header
# инвариант цикла: x→key < searchKey
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward→key
x:= x→forward
if x→key = searchKey then return x→value
else return failure

Вставка и удаление элемента

Для вставки или удаления узла применяем алгоритм поиска для нахождения всех элементов перед вставляемым (или удаляемым), затем обновляем соответствующие указатели:


В данном примере мы вставили элемент уровня 2.

Insert (list, searchKey, newValue)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
# x→key < searchKey ≤ x→forward[i]→key
update[i] := x
x:= x→forward
if x→key = searchKey then x→value:= newValue
else
lvl:= randomLevel()
if lvl > list→level then
for i:= list→level + 1 to lvl do
update[i] := list→header
list→level:= lvl
x:= makeNode(lvl, searchKey, value)
for i:= 1 to level do
x→forward[i] := update[i]→forward[i]
update[i]→forward[i] := x

Delete (list, searchKey)
local update
x:= list→header
for i:= list→level downto 1 do
while x→forward[i]→key < searchKey do
x:= x→forward[i]
update[i] := x
x:= x→forward
if x→key = searchKey then
for i:= 1 to list→level do
if update[i]→forward[i] ≠ x then break
update[i]→forward[i] := x→forward[i]
free(x)
while list→level > 1 and list→header→forward = NIL do
list→level:= list→level – 1

Для запоминания элементов перед вставляемым(или удаляемым) используется массив update . Элемент update[i] - это указатель на самый правый узел, уровня i или выше, из числа находящихся слева от места обновления.

Если случайно выбранный уровень вставляемого узла оказался больше, чем уровень всего списка (т.е. если узлов с таким уровнем ещё не было), увеличиваем уровень списка и инициализируем соответствующие элементы массива update указателями на заголовок. После каждого удаления проверяем, удалили ли мы узел с максимальным уровнем и, если это так, уменьшаем уровень списка.

Генерация номера уровня

Ранее мы приводили распределение уровней узлов в случае, когда половина узлов, содержащих указатель уровня i , также содержали указатель на узел уровня i +1. Чтобы избавиться от магической константы 1/2, обозначим за p долю узлов уровня i , содержащих указатель на узлы уровня i +i. Номер уровня для новой вершины генерируется случайно по следующему алгоритму:

randomLevel ()
lvl:= 1
# random() возвращает случайное число в полуинтервале }