Еще раз про skiplist…

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


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

    Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с 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.: я был на стажировке в компании СКБ Контур. Это чтобы не отвечать на одинаковые вопросы =)
    Share post

    Comments 27

      +1
      Что-то куда-то к концу статьи пропала такая часть изначальной постановки как извлечение среза. Для него можно какие-то числовые замеры сделать?
        +1
        Промахнулся и ответил ниже.
        +1
        Для каких тесткейзов вам интересны числовые замеры? :) Взятие среза размером 10^3, 10^4, 10^5, 10^6 подойдет?
          0
          Да, вполне.
          +1
          Вы сравнивали скорость вставки и потребление памяти со «стоковым» RBTree, или модифицированным (с хранением размера поддерева в узлах)?
            +2
            С модифицированным. Так же в реализации RBTree использовался небольшой хак: число элементов и цвет хранились в одном int. Это корректно, так как по условию задачи максимальное количество элементов 10^6.
            0
            прошу прощения, если не внимательно читал, но скажите, когда есть смысл использовать подобную структуру данных в реальных задачах?
              0
              Например скип листы можно использовать для представления деревьев, при этом находясь на верхней ноде можно простым способом найти всех детей, какой бы глубины дерево дальше не лежало.
                +1
                Не очень понял о чем вы :)
                  0
                  Представьте себе отсортированный массив из 10 элементов.
                  Залейте его в сбалансированный B-Tree.
                  первая нода будет 5, левее будет 2, правее 7. Представьте как это дерево ветвится.
                  А теперь посмотрите на картинки в статье.
                  Если уровень скиплиста приравнять к уровню вложенности дерева — то все станет ясно.
                +4
                Например, когда требуется concurrent доступ к коллекции. Из-за локальных изменениях при вставке в SkipList(в отличии от вставки в дерево, само дерево может сильно перестроиться), реализация такой коллекции на SkipList может оказаться эффективнее.

                Если интересно, могу об этом рассказать подробнее в следующей статье.
                  0
                  Интересно.

                  Вы имеете в виду, что выгода — в том что модифицируется меньше указателей? Не могли бы вы в двух словах сказать, почему это хорошо?
                    +1
                    Именно в этом. Балансировка может сильно перестроить дерево, при этом потребуется заблокировать много его узлов. В Skiplist, как я уже говорил, операция вставки локальна: блокировок потребуют только те узлы, которые непосредственно связаны с вставляемым узлом.

                    По этому поводу есть хорошая статья.
                      0
                      Вы предлагаете завести по мьютексу в каждом узле, и лочить их все по-отдельности?
                      Вряд-ли это будет быстрее чем один мьютекс на всю структуру. Вставки то быстро происходят.
                        +1
                        Мьютекс на всю структуру — не очень хорошая идея. Один поток что-то делает, все остальные ждут.

                        Акцент стоило сделать на том, что приходится блокировать БОЛЬШОЙ кусок дерева. Из-за этого, при concurrent доступе при увеличении количества потоков скорость работы с деревом сильно деградирует.
                          0
                          Все зависит от пропорций оверхед на локинг/время, в залоченном состоянии. ИМХО если мы конструируем новый узел заранее, а в залоченном состоянии просто добавляем его в дерево, то оверхед примерно сопоставим со временем перебалансировки.

                          Улучшая гранулярность блокировок, мы при этом увеличиваем оверхед на локинг.
                +1
                А если взять не RB, а что-нибудь с лучшей балансировкой, например AVL? Ну и если уж работаем с вероятностными алгоритмами (кстати, «логарифмически случайное», наверное, лучше заменить на «логарифмическое в среднем»), то как себя поведет декартово дерево?
                И что будет, если взять датасеты не такого игрушечного размера, а хотя бы в 10 (а лучше в 100) раз больше?
                  +1
                  Сегодня добавлю сравнение с AVL Tree и увеличу датасеты. С декартовым придется немного подождать :)
                  0
                  А почему блог не СКБ Контур?

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

                  И вообще, вот же оно intern_develop_solutions.pdf

                  PS: делал ради интереса, заявок никуда не подавал, в порочащих связях замечен не был.
                    +1
                    1) Я писал от себя, а не от компании, поэтому не в блоге СКБ Контура. Решил начать вести профессиональный блог, начав с описания первого шага в профессию разработчика. Но раз уж вы упомянули, то в этом году тоже проходит Летняя стажировка. Вот ссылка на тестовое: порешайте на досуге =)

                    2) С сортированным массивом другие трудности(простейший тест, который все рушит, есть в статье). На самом деле, решали эту задачу примерно так: половина — с помощью сортированного массива, четверть — деревом отрезков(с предварительным препроцессингом запросов), четверть — с помощью BST.
                      0
                      > четверть — деревом отрезков(с предварительным препроцессингом запросов)
                      АСМщики детектед. Удивительно, что никто не козырнул битовой магией и не сделал дерево Фенвика. :-)
                        0
                        Нормальный человек детектед. А тесты эти не для нас делают :)
                    0
                    Стажировка в гугл? Мне на собеседовании в Google задавали задачку написать реализацию skiplist на С. Видимо у них используется где-то…
                      0
                      Стажировка в СКБ Контур. Когда работаешь над новым проектом и в «голове» компании, то больше возможностей повлиять на то, каким будет продукт.
                      0
                      Xorshift делает равномерное распределения, или характер зависит от the seed set Z?
                        0
                        Упомянается, что вы открывали книгу Кормена. Я её открыл (издание 2013г.), но там не нашёл сведения про эту структуру данных. А вы, ношли?
                          0
                          Вы упомнали лекцию, которую пересмаривали вы пересматривали, это Лекция№12?
                          https://www.youtube.com/watch?v=IXRzBVUgGl8
                          https://itunes.apple.com/us/itunes-u/introduction-to-algorithms/id341597754

                          Курса Mit. Algorithms and datastructures из 2005-го года.
                          Если это она — то круто думаю было бы её добавить в статью в раздел библиографии.

                          Only users with full accounts can post comments. Log in, please.