Pull to refresh

Еще раз про skiplist…

Reading time6 min
Views34K

… или как я получил «Аленку» за консольное приложение


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

Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»

Предполагается, что в наборе допускаются дубликаты, и количество элементов будет не больше, чем 10^6.

К оценке решения есть несколько комментариев:

Ваш код будут оценивать и тестировать три программиста:
  • Билл будет запускать ваше решение на тестах размером не больше 10Кб.
  • В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
  • В тестах Марка количество запросов будет не больше 10^5.
Решение может быть очень интересным, поэтому я посчитал нужным его описать.

Решение


Пусть у нас есть абстрактное хранилище.

Обозначим Add(e) — добавление элемента в хранилище, а Range(l, r) — взятие среза с l по r элемент.

Тривиальный вариант хранилища может быть таким:
  • Основой хранилища будет упорядоченный по возрастанию динамический массив.
  • При каждой вставке бинарным поиском находится позицию, в которую необходимо вставить элемент.
  • При запросе Range(l, r) будем просто брать срез массива из l по r.
Оценим сложность подхода, основанного на динамическом массиве.

C Range(l, r) — взятие среза можно оценить, как O(r — l).

C Add(e) — вставка в худшем случае будет работать за O(n), где n — количество элементов. При n ~ 10^6, вставка — узкое место. Ниже в статье будет предложен улучшенный вариант хранилища.

Пример исходного кода можно посмотреть здесь.

Более подходящий вариант может быть, например таким:
  • Основой хранилища будет самобалансирующееся дерево поиска, имеющее сложность O(ln n) на операцию вставки, поиска, удаления(AVL tree, RB tree и другие).
  • Расширяется структура данных путем добавления в узел информации о количестве узлов в поддереве. Это необходимо для того, чтобы получать i-ый элемент дерева за O(ln n).
  • Переписывается добавление элемента в дерево, чтобы пересчитывать количество узлов в поддереве. Это можно сделать так, что стоимость операции добавления останется O(ln n).
Я уже практически настроился открыть Кормена и начать вспоминать, как же RB-tree работает, но совершенно случайно наткнулся на статью о SkipList в википедии.

Skiplist


Skiplist — это рандомизированная альтернатива деревьям поиска, в основе которой лежит несколько связных списков. Была изобретена William Pugh в 1989 году. Операции поиска, вставки и удаления выполняются за логарифмически случайное время.

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

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

Пусть у нас есть отсортированный односвязный список:

В худшем случае поиск выполняется за O(n). Как его можно ускорить?

В одной из видео-лекций, которые я пересматривал, когда занимался задачкой, приводился замечательный пример про экспресс-линии в Нью-Йорке:


  • Скоростные линии соединяют некоторые станции
  • Обычные линии соединяют все станции
  • Есть обычные линии между общими станциями скоростных линий
Идея в следующем: мы можем добавить некоторое количество уровней с некоторым количеством узлов в них, при этом узлы в уровнях должны быть равномерно распределены. Рассмотрим пример, когда на каждом из вышележащих уровней располагается половина элементов из нижележащего уровня:


На примере изображен идеальный SkipList, в реальности всё выглядит подобным образом, но немного не так :)

Поиск


Так происходит поиск. Предположим, что мы ищем 72-й элемент:



Вставка


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

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



Предположил, что монетка выпала два раза подряд. Значит нужно протолкнуть элемент на два уровня вверх:



Доступ по индексу


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



После того, как мы получаем доступ к i-му элементу (кстати, получаем мы его за O(ln n)), сделать срез не представляется трудным.

Пусть необходимо найти Range(5, 7). Сначала получим элемент по индексу пять:


А теперь Range(5, 7):


О реализации


Кажется естественной реализация, когда узел SkipList выглядит следующим образом:
SkipListNode {
   int Element;
   SkipListNode[] Next;
   int [] Width;
}
Собственно, так и сделано в реализации на C от William Pug.

Но в C# в массиве хранится еще и его длина, а хотелось сделать это за как можно меньшее количество памяти (как оказалось, в условиях задачи все оценивалось не так строго). При этом хотелось сделать так, чтобы реализация SkipList и расширенного RB Tree занимала примерно одинаковое количество памяти.

Ответ, как уменьшить потребление памяти, неожиданно был найден при ближайшем рассмотрении ConcurrentSkipListMap из пакета java.util.concurrent.

Двумерный skiplist


Пусть в одном измерении будет односвязный список из всех элементов. Во втором же будут лежать «экспресс-линии» для переходов со ссылками на нижний уровень.
ListNode {
   int Element;
   ListNode Next;
}

Lane {
   Lane Right;
   Lane Down;
   ListNode Node;
}

Нечестная монетка


Еще для снижения потребления памяти можно воспользоваться «нечестной» монеткой: уменьшить вероятность проталкивания элемента на следующий уровень. В статье William Pugh рассматривался срез из нескольких значений вероятности проталкивания. При рассмотрении значений ½ и ¼ на практике получилось примерно одинаковое время поиска при уменьшении потребления памяти.

Немного о генерации случайных чисел


Копаясь в потрохах ConcurrentSkipListMap, заметил, что случайные числа генерируются следующим образом:
int randomLevel() {
  int x = randomSeed;
  x ^= x << 13;
  x ^= x >>> 17;
  randomSeed = x ^= x << 5;
  if ((x & 0x80000001) != 0)
    return 0;
  int level = 1;
  while (((x >>>= 1) & 1) != 0) ++level;
    return level;
}
Подробнее о генерации псевдослучайных чисел с помощью XOR можно почитать в этой статьe. Особого увеличения скорости я не заметил, поэтому, не использовал его.

Исходник получившегося хранилища можно глянуть здесь.

Все вместе можно забрать с googlecode.com (проект Pagination).

Тесты


Было использовано три типа хранилища:
  1. ArrayBased (динамический массив)
  2. SkipListBased (SkipList c параметром ¼)
  3. RBTreeBased (красно-черное дерево: реализация моего знакомого, который выполнял аналогичное задание).
Было проведено три вида тестов на вставку 10^6 элементов:
  1. Упорядоченные по возрастанию элементы
  2. Упорядоченные по убыванию элементы
  3. Случайные элементы
Тесты проводились на машине с i5, 8gb ram, ssd и Windows 7 x64.
Результаты:
Array RBTree SkipList
Random 127033 ms 1020 ms 1737 ms
Ordered 108 ms 457 ms 536 ms
Ordered by descending 256337 ms 358 ms 407 ms
Вполне ожидаемые результаты. Видно, что вставка в массив, когда элемент вставляется куда-нибудь, кроме как в конец, работает медленнее всего. При этом SkipList медленнее RBTree.

Также были проведены замеры: сколько каждое хранилище занимает в памяти при вставленных в него 10^6 элементах. Использовался студийный профайлер, для простоты запускался такой код:
var storage = ...
for(var i = 0; i < 1000000; ++i)
  storage.Add(i);
Результаты:
Array RBTree SkipList
Total bytes allocated 8,389,066 bytes 24,000,060 bytes 23,985,598 bytes
Ещё вполне ожидаемые результаты: хранилище на динамическом массиве заняло наименьшее количество памяти, а SkipList и RBTree заняли примерно одинаковый объем.

Хеппи-энд с «Алёнкой»


Коллега-нытик, по условию задачи, проспорил мне шоколадку. Моё решение зачли с максимальным баллом. Надеюсь, кому-нибудь данная статья будет полезна. Если есть какие-то вопросы — буду рад ответить.

P.S.: я был на стажировке в компании СКБ Контур. Это чтобы не отвечать на одинаковые вопросы =)
Tags:
Hubs:
Total votes 53: ↑49 and ↓4+45
Comments27

Articles