Ключевые преимущества скип. С какого уровня начинать искать? Определение L(n)

Исправлена ​​ошибка в реализации, предоставляемой @PoweredByRice. Он выбросил NPE для случаев, когда удаленный node был первым node. Другие обновления включают переименованные имена переменных и обратную печать порядка списка пропусков.

Import java.util.Random; interface SkippableList> { int LEVELS = 5; boolean delete(T target); void print(); void insert(T data); SkipNode search(T data); } class SkipNode> { N data; @SuppressWarnings("unchecked") SkipNode next = (SkipNode) new SkipNode; SkipNode(N data) { this.data = data; } void refreshAfterDelete(int level) { SkipNode current = this; while (current != null && current.getNext(level) != null) { if (current.getNext(level).data == null) { SkipNode successor = current.getNext(level).getNext(level); current.setNext(successor, level); return; } current = current.getNext(level); } } void setNext(SkipNode next, int level) { this.next = next; } SkipNode getNext(int level) { return this.next; } SkipNode search(N data, int level, boolean print) { if (print) { System.out.print("Searching for: " + data + " at "); print(level); } SkipNode result = null; SkipNode current = this.getNext(level); while (current != null && current.data.compareTo(data) < 1) { if (current.data.equals(data)) { result = current; break; } current = current.getNext(level); } return result; } void insert(SkipNode skipNode, int level) { SkipNode current = this.getNext(level); if (current == null) { this.setNext(skipNode, level); return; } if (skipNode.data.compareTo(current.data) < 1) { this.setNext(skipNode, level); skipNode.setNext(current, level); return; } while (current.getNext(level) != null && current.data.compareTo(skipNode.data) < 1 && current.getNext(level).data.compareTo(skipNode.data) < 1) { current = current.getNext(level); } SkipNode successor = current.getNext(level); current.setNext(skipNode, level); skipNode.setNext(successor, level); } void print(int level) { System.out.print("level " + level + ": [ "); int length = 0; SkipNode current = this.getNext(level); while (current != null) { length++; System.out.print(current.data + " "); current = current.getNext(level); } System.out.println("], length: " + length); } } public class SkipList> implements SkippableList { private final SkipNode head = new SkipNode<>(null); private final Random rand = new Random(); @Override public void insert(T data) { SkipNode skipNode = new SkipNode<>(data); for (int i = 0; i < LEVELS; i++) { if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i) insert(skipNode, i); } } } @Override public boolean delete(T target) { System.out.println("Deleting " + target); SkipNode victim = search(target, true); if (victim == null) return false; victim.data = null; for (int i = 0; i < LEVELS; i++) { head.refreshAfterDelete(i); } System.out.println("deleted..."); return true; } @Override public SkipNode search(T data) { return search(data, true); } @Override public void print() { for (int i = LEVELS-1; i >= 0 ; i--) { head.print(i); } System.out.println(); } private void insert(SkipNode SkipNode, int level) { head.insert(SkipNode, level); } private SkipNode search(T data, boolean print) { SkipNode result = null; for (int i = LEVELS-1; i >= 0; i--) { if ((result = head.search(data, i, print)) != null) { if (print) { System.out.println("Found " + data.toString() + " at level " + i + ", so stopped"); System.out.println(); } break; } } return result; } public static void main(String args) { SkipList sl = new SkipList<>(); int data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8}; for (int i: data) { sl.insert(i); } sl.print(); sl.search(4); sl.delete(4); System.out.println("Inserting 10"); sl.insert(10); sl.print(); sl.search(10); } }

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

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

Ваш код будут оценивать и тестировать три программиста:

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

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

Skiplist

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

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

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

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

• Скоростные линии соединяют некоторые станции
• Обычные линии соединяют все станции
• Есть обычные линии между общими станциями скоростных линий

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

Поиск

Вставка

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

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

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

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

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

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

О реализации

SkipListNode {
int Element;
SkipListNode Next;
int Width;
}

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

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

Двумерный skiplist

ListNode {
int Element;
ListNode Next;
}

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

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

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

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;
}

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

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

Тесты

1. ArrayBased (динамический массив)
2. SkipListBased (SkipList c параметром ¼)
3. RBTreeBased (красно-черное дерево: реализация моего знакомого, который выполнял аналогичное задание).

1. Упорядоченные по возрастанию элементы
2. Упорядоченные по убыванию элементы
3. Случайные элементы

Также были проведены замеры: сколько каждое хранилище занимает в памяти при вставленных в него 10^6 элементах. Использовался студийный профайлер, для простоты запускался такой код:

var storage = ...
for (var i = 0; i < 1000000; ++i)
storage.Add(i);

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

P.S.: я был на стажировке в компании СКБ Контур. Это чтобы не отвечать на одинаковые вопросы =)

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

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

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

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

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

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

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 указателями на заголовок. После каждого удаления проверяем, удалили ли мы узел с максимальным уровнем и, если это так, уменьшаем уровень списка.

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

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