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

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

Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с 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, вставка — узкое место. Ниже в статье будет предложен улучшенный вариант хранилища.

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

Более подходящий вариант может быть, например таким:

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

Я уже практически настроился открыть Кормена и начать вспоминать, как же RB-tree работает, но совершенно случайно наткнулся на статью о SkipList в википедии ^[3].

Skiplist

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

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

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

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

В худшем случае поиск выполняется за 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 ^[5].

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

Ответ, как уменьшить потребление памяти, неожиданно был найден при ближайшем рассмотрении ConcurrentSkipListMap ^[6] из пакета 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 ^[7]. Особого увеличения скорости я не заметил, поэтому, не использовал его.

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

Все вместе можно забрать с googlecode.com ^[9] (проект 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 заняли примерно одинаковый объем.

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

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

Автор: Pliner