Списки с пропусками: Сделано Правильно

Что такое список пропусков?

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

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

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

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

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

Это мои мысли о том, как выглядит плохая и хорошая реализация списка пропусков.

Преимущества

• Списки пропусков очень хорошо работают при быстрой вставке, потому что нет никаких вращений или перераспределений.
• Они проще в реализации, чем самобалансирующиеся бинарные деревья поиска и хэш-таблицы.
• Вы можете получить следующий элемент в постоянное время (сравните с логарифмическим временем для обхода inorder для BST и линейным временем в хэш-таблицах).
• Алгоритмы могут быть легко модифицированы в более специализированную структуру (например, сегментные или диапазонные “деревья”, индексируемые списки пропусков или очереди приоритетов с ключами).
• Сделать его без замка очень просто.
• Он хорошо работает в постоянном (медленном) хранении (часто даже лучше, чем AVL и EH).

Наивная (но распространенная) реализация

Наш список пропусков состоит из (в данном случае трех) списков, сложенных таким образом, что n- й список посещает подмножество узла, который делает N-1-й список. Это подмножество определяется распределением вероятностей, к которому мы вернемся позже.

Если вы повернете список пропусков и удалите повторяющиеся ребра, то увидите, как он напоминает двоичное дерево поиска:

Скажем, я хотел бы найти узел “30”, а затем выполнить обычный двоичный поиск от корня и вниз. Из-за повторяющихся узлов мы используем правило идти направо, если оба потомка равны:

Самобалансирующиеся бинарные деревья поиска часто имеют сложные алгоритмы для поддержания сбалансированности дерева, но списки пропусков проще: они не деревья, они похожи на деревья в некоторых отношениях, но они не деревья.

Каждому узлу в списке пропусков присваивается "высота", определяемая самым высоким уровнем, содержащим узел (аналогично, число потомков листа, содержащего то же значение). Например, на приведенной выше диаграмме “42” имеет высоту 2, “25” - высоту 3, а “11” - высоту 1.

При вставке мы присваиваем узлу высоту, следуя распределению вероятностей:

p (n) = 21-n

Чтобы получить такое распределение, мы подбрасываем монету до тех пор, пока она не попадет в решку, и считаем сальто:

uint generate_level() {     uint n = 0;     while coin_flip() {         n++;     }      return n; } 

При таком распределении статистически Родительский слой будет содержать вдвое меньше узлов, поэтому поиск амортизируется O(log n) .

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

-- Recursive skip list insertion function. define insert(elem, root, height, level):     if right of root < elem:         -- If right isn't "overshot" (i.e. we are going to long), we go right.         return insert(elem, right of root, height, level)     else:         if level = 0:             -- We're at bottom level and the right node is overshot, hence             -- we've reached our goal, so we insert the node inbetween root             -- and the node next to root.             old <- right of root             right of root <- elem             right of elem <- old         else:             if level <= height:                 -- Our level is below the height, hence we need to insert a                 -- link before we go on.                 old <- right of root                 right of root <- elem                 right of elem <- old              -- Go a level down.             return insert(elem, below root, height, level - 1) 

Приведенный выше алгоритм рекурсивен, но мы можем с относительной легкостью превратить его в итеративную форму (или позволить оптимизации хвостового вызова сделать эту работу за нас).

В качестве примера приведем диаграмму, криволинейные линии которой обозначают выходы / ребра там, где вставляется новый узел:

Отходы, отходы повсюду

Это кажется прекрасным, не так ли? Нет, вовсе нет. Это абсолютный мусор.

Происходит полная и абсолютная трата пространства. Предположим, что существует n элементов , тогда самый высокий узел равен приблизительно h = log2 n, что дает нам приблизительно 1 + ?k <-0..h 2-k n ? 2n.

2n-это, конечно, немалая сумма, особенно если учесть, что каждый узел содержит указатель на внутренние данные, узел справа и вниз, дающий в общей сложности 5 указателей, так что единая структура из n узлов состоит примерно из 6N указателей.

Но память-это даже не главная забота! Когда вам нужно следить за указателем на каждом уменьшении (ок. 50% всех ссылок), что, возможно, приводит к промахам кэша. Оказывается, существует действительно простое решение этой проблемы:

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

Если вы представляете ссылки ("ярлыки") через динамические массивы, вы все равно часто получаете промах кэша. В частности, вы можете получить промах кэша как на самом узле (который не является локальным для данных), так и на динамическом массиве. Таким образом, я рекомендую использовать массив фиксированного размера (остерегайтесь двух отрицательных недостатков: 1. больше пространства, 2. жесткий предел на самом высоком уровне и подразумеваемый линейный верхний предел, когда h > c>. Кроме того, вы должны держать достаточно маленький размер, чтобы соответствовать строке кэша.).

Поиск осуществляется путем следования верхним ярлыкам до тех пор, пока вы не превысите свою цель, затем вы уменьшаете уровень и повторяете, пока не достигнете самого низкого уровня и не превысите его. Вот пример поиска “22”:

В псевдокоде:

define search(skip_list, needle):     -- Initialize to the first node at the highest level.     level <- max_level     current_node <- root of skip_list      loop:         -- Go right until we overshoot.         while level'th shortcut of current_node < needle:             current_node <- level'th shortcut of current_node          if level = 0:             -- We hit our target.             return current_node         else:             -- Decrement the level.             level <- level - 1 

O (1) генерация уровня

Даже Уильям пью допустил эту ошибку в своей первоначальной работе. Проблема заключается в том, как генерируется уровень: повторяющиеся подбрасывания монет (вызов генератора случайных чисел и проверка четности) могут означать пару обновлений состояния ГСЧ (примерно по 2 на каждую вставку). Если ваш ГСЧ работает медленно (например, вам нужна высокая безопасность от DOS-атак), это заметно.

Выход ГСЧ равномерно распределен, поэтому вам нужно применить некоторую функцию, которая может преобразовать это в желаемое распределение. Мой любимый-вот этот:

define generate_level():     -- First we apply some mask which makes sure that we don't get a level     -- above our desired level. Then we find the first set bit.     ffz(random() & ((1 << max_level) - 1)) 

Это, конечно, подразумевает, что вы max_levelне выше разрядности random()выходного сигнала. На практике большинство ГСЧ возвращают 32-разрядные или 64-разрядные целые числа, что означает, что это не должно быть проблемой, если только у вас нет большего количества элементов, чем может быть в вашем адресном пространстве.

Повышение эффективности кэша

Для повышения эффективности работы кэша можно использовать несколько методов:

Пулы памяти

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

Приказ не имеет значения. Действительно, если мы поменяем местами “9 "и” 7", то внезапно увидим, что это просто список пропусков:

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

Поскольку это указатели в память, а не индексы в массиве, нам не нужно перераспределять их при росте. Мы можем просто расширить свободный список.

Плоские массивы

Если мы заинтересованы в компактности и имеем отношение вставки/удаления около 1, то можно использовать вариант связанных пулов памяти: мы можем хранить список пропусков в плоском массиве, так что у нас есть индексы в этом массиве вместо указателей.

Развернутые списки

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

Развертывание имеет важное значение для хорошей производительности кэша. В зависимости от размера объектов, которые вы храните, развертка может уменьшить пропуски кэша при переходе по ссылкам во время поиска на 50-80%.

Вот пример развернутого списка пропусков:

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

Обратите внимание, что эти алгоритмы требуют информации о том, как мы нашли кусок. Поэтому мы храним” взгляд назад", массив последнего посещенного узла, для каждого уровня. Затем мы можем вернуться назад, если мы не смогли поместить элемент в кусок.

Мы эффективно уменьшаем пропуски кэша в несколько раз в зависимости от размера объекта, который вы храните. Это происходит из-за меньшего количества ссылок, которые необходимо проследить, прежде чем цель будет достигнута.

Самобалансирующиеся списки пропусков

Различные методы могут быть использованы для улучшения генерации высоты, чтобы дать лучшее распределение. Другими словами, мы делаем генератор уровней осведомленным о наших узлах, а не о чисто случайных независимых ГСЧ.

Самокорректирующийся список пропусков

Самый простой способ создать генератор уровней с учетом содержимого - отслеживать количество узлов каждого уровня в списке пропусков. Если мы предположим, что существует n узлов, то ожидаемое число узлов с уровнем l равно 2-ln. Вычитание этого из действительного числа дает нам меру того, насколько хорошо сбалансирована каждая высота:

Когда мы генерируем новый уровень узла, вы выбираете одну из высот с наибольшим недопредставлением (см. черную линию на диаграмме), либо случайным образом, либо по какому-то фиксированному правилу (например, самая высокая или самая низкая).

Идеально сбалансированные списки пропусков

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

Лишнее замечание

Списки пропусков являются прекрасной альтернативой распределенным хэш-таблицам. Производительность в основном примерно такая же, но списки пропусков более устойчивы к DoS, если вы убедитесь, что все ссылки являются F2F.

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

Если вы хотите безопасную открытую систему, хитрость заключается в том, что любой узел может пригласить узел, дав ему уровень, равный или ниже самого уровня. Если узел управляет ключевым пространством в интервале от А до В, то мы разбиваем его на две части и переносим все пары КВ во второй части на новый узел. Очевидно, что этот подход не имеет эскалации привилегий, поэтому вы не можете легко инициализировать атаку Сибиллы.

Заключение и заключительные слова

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

Источник: ticki.github.io

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