Почему не существует не одновременной версии SkipList

Question

Я начал исследование ConcurrentSkipListSet.

С самого начала я пытался понять, что такое SkipList?

Я представляю это так (возможный вариант):

У меня есть 2 вопроса:

1. Как SkipList связан с параллелизмом?
2. Почему не существует одновременного варианта этой структуры данных?

Answer 1

Ваш список пропусков немного не похож, он выглядит примерно так:

^{_{От http://en.wikipedia.org/wiki/File:Skip_list.svg}}

Дно начинается как список ссылок, и у вас это есть... но больше думайте о них как о башнях, связанных с каждым уровнем. Дело в том, что если вы хотите найти 7, вы можете перейти от 1 -> 4 -> 6 -> 9 (упс, нет) к 7. Это позволяет вам аппроксимировать сбалансированное двоичное дерево со связанными списками.

При использовании красно-черного дерева или дерева AVL, когда необходимо изменить структуру, необходимо полностью заблокировать ее, чтобы можно было перестроить структуру. С другой стороны, список пропусков можно "переставить" без глобальной блокировки. Удаление 7 требует только изменения ссылок, указывающих на него, чтобы они указывали на следующий элемент, что требует только блокировки записи для элемента 6, а не всей структуры.

В списках пропуска, где они были представлены, хорошо читается " Пропустить списки: вероятностная альтернатива сбалансированным деревьям", в которой показано, как это работает, и различные алгоритмы. Внутри этого находится "Таблица 2 - Временные рамки и реализации различных алгоритмов", в которых показано, что списки пропусков работают немного быстрее, хотя отчасти это объясняется конкретными данными, которые они использовали.

В разделе "Дополнительные работы по пропускам списков"

Я описал набор алгоритмов, которые позволяют нескольким процессорам одновременно обновлять список пропусков в общей памяти [Pug89a]. Эти алгоритмы намного проще, чем параллельные алгоритмы сбалансированного дерева. Они позволяют неограниченному количеству читателей и n занятых писателей пропустить список из n элементов с очень небольшим количеством конфликтов блокировки.

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

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

Что касается того, почему в Библиотеке Java нет списка одновременных пропусков? Это будет означать дублирование кода в другой пакет (что плохо) и ничего не получится. Ничто не говорит о том, что вы не можете использовать параллельный пакет где-то, что не связано с одновременными проблемами. Дело в том, что им потребовалось два типа Map для одновременной работы, O(1) HashMap и O(log n) дерево. Поскольку TreeMap не может обеспечить хорошую параллельную реализацию, они решили изменить это на SkipList.

Связанное чтение:

• Как реализовать список пропусков без блокировки
• безблокировочный скиплист с операцией ранга

Answer 2

1. Любая структура данных не зависит от параллелизма. См. Реализации Java List в пакете коллекций. LinkedList не является потокобезопасным, но вы можете сделать это, используя класс Collections.
2. Тот, кто написал реализацию для SkipList, решил встроить безопасность потока в класс. Это было решение о реализации.