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

14

Для домашнего задания мне нужно понять, как работает список пропусков .

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

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

Как работает список пропусков? Требуется ли знание списка пропусков для понимания более сложных структур данных?

Carcigenicate
источник
1
Советы по образованию явно не по теме . Поскольку речь идет о структурах данных, а не об образовании, я отредактировал ваш вопрос, чтобы удалить эти части. Я также рекомендую прочитать ссылку на Википедию, в которой я отредактировал, и обновить ваш вопрос более подробной информацией о том, что вы до сих пор не поняли.
@ Снеговик Спасибо. Я только добавил, что для предотвращения комментариев, как «спросите своего учителя». Я буду помнить это в следующий раз. И вы добавили правку, которая меняет вопрос. В конце я не прошу людей объяснять, как они работают, поскольку я предполагаю, что это оффтоп (хотя я не был бы против хорошего объяснения). Я просто хочу знать, насколько они важны, чтобы учиться.
Carcigenicate
1
@Carcigenicate, объясняющий, как они работают, на самом деле больше тематический, чем вопрос, увидишь ли ты их в реальном мире. Мы можем только догадываться о том, что вы будете делать, и о различных сферах. Вопрос о том, видим ли мы их в реальном мире, опрашивает нас: «Да, я вижу их и использую их» или «Нет, никогда не слышал об этом» - что не дает хороших или полезных ответов для других людей.

Ответы:

29

В былые времена в классе структур данных мы узнали, как работают деревья AVL . У меня было бы это на одном из моих занятий, но преподаватель сказал: «Вы никогда не будете использовать это на самом деле», и вместо этого попросил нас выучить 2-3 дерева и б * деревья. Это были дни, когда память была тесной и процессы были однопоточными. Вы не использовали deque, когда одинаково связанный список будет работать так же хорошо.

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

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

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

Вы будете нуждаться , чтобы понять , почему вы хотите , чтобы выбрать ConcurrentSkipListMapв Java , а не HashMapили , TreeMapили любой из других реализаций карты.


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

Допустим, у нас есть это дерево:

Бинарное дерево

И мы вставляем в него «8». Теперь у нас есть:

Несбалансированное бинарное дерево

И это не сбалансировано. Итак, мы идем и делаем волшебство балансировки через некоторую реализацию ...

сбалансированное дерево

И у тебя снова сбалансированное дерево. Но это было много магии, я махнул рукой.

Давайте возьмем список пропуска.

идеальный список пропуска

Это один идеализированный. Немного, но это показывает сбалансированную двоичную древовидную природу, которую аппроксимирует идеал пропуска.

Теперь мы хотим вставить туда 6. Это вставляет его так же, как связанный список. Однако мы начинаем сверху и спускаемся. Верхняя точка указывает на 5. Является ли 6> 5? Да. Хорошо, теперь вершина заканчивается до конца, поэтому мы идем вниз по стеку (мы находимся на 5). Следующим является 7. Является ли 6> 7? Нет. Итак, мы идем вниз по уровню и находимся на базовом уровне, поэтому мы вставляем 6 справа от 5.

Мы подбрасываем монету - головы строим, хвосты остаемся. Хвосты. Больше ничего не нужно делать.

пропустить список после вставки

Давайте вставим это 8 сейчас. 8> 5? Ага. 8> 7? Ага. И теперь мы снова на нижнем уровне после следующих стрелок и стека и тестируем 8> 11? Нет. Таким образом, мы вставляем 8 справа от 7.

Мы подбрасываем монету - головы строим, хвосты остаемся. Хвосты. Больше ничего не нужно делать.

пропустить список после другой вставки

В сбалансированном дереве мы бы все расстроились из-за того, что дерево сейчас не сбалансировано. Но это не дерево - это список пропусков. Мы приближаем сбалансированное дерево.

Теперь давайте вставим 10. Я буду избегать всех сравнений.

Мы подбрасываем монету - головы строим, хвосты остаемся. Heads! И снова переверни, Головы снова! Переверните это снова, хорошо, есть хвосты. Два уровня выше базового связного списка.

пропустить список после еще одной вставки

Преимущество здесь в том, что теперь, если мы собираемся вставить 12, мы можем пропустить от 5 до 10, не делая все эти другие сравнения. Мы можем пропустить их с помощью списка пропусков. И нам не нужно беспокоиться о сбалансированном дереве - вероятностный характер суммирования делает это для нас.

Почему это так полезно? Потому что, вставляя 10, я могу сделать это, блокируя запись на 5 и 7 и 8 указателях, а не на всю структуру. И пока я делаю это, читатели могут просматривать список пропусков, не имея противоречивого состояния. Для одновременного использования быстрее не нужно блокировать. Для итерации по нижнему слою, это быстрее, чем дерево (радости алгоритмов BFS и DFS для навигации по дереву - вам не нужно беспокоиться о них).

Вы столкнетесь с этим? Вы, вероятно, увидите его в использовании в некоторых местах. И тогда вы поймете, почему автор выбрал эту реализацию, а не TreeMapили HashMapдля структуры.

Многое из этого было позаимствовано из моего поста в блоге: The Skip List


источник
Спасибо. Это даже не общая реализация, которую я не понимаю; Я получаю их сходство с BST. Я пытался придумать, как бы это реализовать, и мысль об управлении всеми указателями / ссылками постоянно смущала меня. Может быть, я позволил себе слишком расстроиться. Благодарю. Я постараюсь забрать его завтра, используя ваш ответ в качестве отправной точки.
Carcigenicate
2
@Carcigenicate Вы также можете найти оригинальную статью, представляющую их полезной - Пропуск списков: вероятностная альтернатива сбалансированным деревьям . Это довольно понятная статья по сравнению с большинством академических работ, которые могут выходить далеко за головы людей. Таблица 2, почему вы увидите их в использовании. Этот фактор времени для вставки или удаления добавляет сложность других решений.
2
Связанный список - это «просто вырожденное очень несбалансированное дерево». Пропуск списка - это своего рода частичное добавление некоторой древовидной структуры поверх списка. Лично я большой поклонник постоянных структур данных, и деревья, кажется, легче рассуждать в этом конкретном контексте. Я не думаю, что это совпадение, что Clojure, Scala и др. похоже, сходятся на неких хэш-попытках в стиле Багвелла в качестве базовой структуры данных. (Фил Багвелл даже участвовал в редизайне структуры коллекций Scala для Scala 2.8.) Однако списки пропусков все еще хороши.
Йорг Миттаг,
Это лучшее объяснение того, как работает список пропусков, который я когда-либо читал.
Габорист