Пропустить Список против двоичного дерева поиска

Недавно я столкнулся с структурой данных, известной как список пропусков . Похоже, что это похоже на двоичное дерево поиска.

Зачем вам когда-либо понадобиться использовать список пропуска по двоичному дереву поиска?

7 Solutions collect form web for “Пропустить Список против двоичного дерева поиска”

Пропустить списки более поддаются одновременному доступу / модификации. Херб Саттер написал статью о структуре данных в параллельных средах. Он имеет более глубокую информацию.

Наиболее часто используемой реализацией двоичного дерева поиска является красно-черное дерево . Параллельные проблемы возникают при изменении дерева, которое часто требуется для балансировки. Операция перебалансировки может влиять на большие части дерева, что потребует блокировки мьютекса на многих узлах дерева. Вставка узла в список пропуска намного локализована, только узлы, непосредственно связанные с затронутым узлом, должны быть заблокированы.


Обновление от комментариев Jon Harrops

Я читал последнюю статью Фрейзера и Харриса « Параллельное программирование без блокировок» . Действительно хорошие вещи, если вас интересуют блокированные структуры данных. В документе основное внимание уделяется транзакционной памяти и теоретической операции multi-compare-and-swap MCAS. Оба они имитируются в программном обеспечении, пока их не поддерживает. Я довольно впечатлен тем, что они смогли создать MCAS в программном обеспечении вообще.

Я не нашел материал транзакционной памяти особенно привлекательным, поскольку для этого нужен сборщик мусора. Кроме того, транзакционная память программного обеспечения страдает от проблем с производительностью. Тем не менее, я был бы очень рад, если аппаратная транзакционная память станет обычной. В конце концов, это все еще исследование и не будет использоваться для производственного кода еще на десятилетие или около того.

В разделе 8.2 они сравнивают производительность нескольких параллельных реализаций дерева. Я обобщу их выводы. Это стоит того, чтобы загрузить pdf, так как на страницах 50, 53 и 54 у него есть очень информативные графики.

  • Блокировка списков пропусков безумно быстра. Они масштабируются невероятно хорошо с количеством одновременных доступов. Именно это делает списки пропусков специальными, другие структуры данных, основанные на блокировке, имеют тенденцию кричать под давлением.
  • Списки пропусков с блокировкой последовательно быстрее, чем блокировка списков пропусков, но едва ли.
  • транзакционные списки пропусков последовательно в 2-3 раза медленнее, чем блокирующие и неблокирующие версии.
  • блокирующие красно-черные деревья пробираются под одновременным доступом. Их производительность ухудшается линейно с каждым новым одновременным пользователем. Из двух известных блокирующих реализаций красно-черного дерева, по сути, существует глобальная блокировка во время балансировки дерева. Другой использует необычную (и сложную) эскалацию блокировки, но по-прежнему не выполняет значительную версию глобальной блокировки.
  • блокировочные красно-черные деревья не существуют (больше не верны, см. Обновление).
  • транзакционные красно-черные деревья сопоставимы с транзакционными списками пропуска. Это было очень удивительно и очень многообещающе. Транзакционная память, хотя и медленнее, если гораздо проще писать. Это может быть так же просто, как быстрый поиск и замена на неконкурентной версии.

Обновить
Вот статья о деревьях, свободных от замка : Безкрайние красно-черные деревья с использованием CAS .
Я не заглядывал в нее глубоко, но на первый взгляд кажется твердым.

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

Список пропусков эквивалентен случайно сбалансированному двоичному дереву поиска (RBST) таким образом, который более подробно объясняется в Дин и Джонсе «Изучение двойственности между пропущенными списками и деревьями двоичного поиска» .

С другой стороны, вы также можете иметь детерминированные списки пропусков, которые гарантируют наихудшую производительность, ср. Munro et al.

Противоположность тому, что указано выше, вы можете иметь реализации двоичных поисковых деревьев (BST), которые хорошо работают при параллельном программировании. Потенциальная проблема с ориентированными на параллелизм BST заключается в том, что вы не можете легко получить то же самое, что и гарантии относительно балансировки, как и из дерева с красно-черным (RB). (Но «стандартные», то есть случайные, списки пропуска не дают вам этих гарантий.) Существует компромисс между поддержанием баланса во все времена и хорошим (и простым в программировании) одновременным доступом, поэтому обычно используются расслабленные деревья RB когда требуется хороший параллелизм. Релаксация заключается в том, чтобы сразу не переустанавливать дерево. В несколько датированном (1998) обзоре см. «Эффективность параллельных алгоритмов красно-черного дерева» Хэнке [ps.gz] .

Одним из последних улучшений в этом случае является так называемое хроматическое дерево (в основном у вас есть такой вес, что черный будет 1, а красный – нулевым, но вы также позволяете значения между ними). И как цветовое дерево связано с пропуском? Давайте посмотрим, что Браун и др. «Общая техника для неблокирующих деревьев» (2014) должна сказать:

с 128 streamами, наш алгоритм превосходит неблокирующий skiplist Java на 13% до 156%, основанное на блокировке AVL-дерево Bronson и др. на 63% до 224%, а RBT, который использует программную транзакционную память (STM) в 13 – 134 раза

EDIT, чтобы добавить: пропущенный список блокировки Pugh, который был проверен в Fraser and Harris (2007) «Concurrent Programming Without Lock», как приближающийся к своей собственной версии без блокировки (в данном случае настойчиво настаивал на верхнем ответе) также настраивается для хорошей параллельной работы, ср. «Совместное техническое обслуживание списков пропусков » Пью, хотя и довольно мягким образом. Тем не менее одна новая статья 2009 года «Простой оптимистичный алгоритм пропуска» Херлихи и др., В которой предлагается предположительно более простая (чем у Пью) реализация на основе блокировки совпадающих списков пропуска, критикует Пью за то, что он не предоставил доказательства правильности, достаточно убедительного для них. Оставив в стороне этот (возможно, слишком педантичный) характер, Herlihy et al. показывают, что их простая реализация на основе блокировки списка пропусков фактически не масштабируется, а также ее блокировка без блокировки, но только для высокой конкуренции (50% вставок, 50% удалений и 0% запросов) … которые Fraser и Харрис не испытывал вообще; Фрейзер и Харрис тестировали только 75% запросов, 12,5% вставок и 12,5% удалений (в списке пропуска с элементами ~ 500 тыс.). Более простая реализация Herlihy et al. также приближается к решению без блокировки от JDK в случае низкой конкуренции, которую они тестировали (70% запросов, 20% вставок, 10% удалений); они фактически обыграли без блокировки решение для этого сценария, когда они сделали свой список пропуска достаточно большим, то есть перейдя от 200 К до 2М элементов, так что вероятность конкуренции на любом замке стала незначительной. Было бы неплохо, если бы Herlihy et al. покончили с собой за доказательство Пью и испытали его реализацию, но, к сожалению, они этого не сделали.

EDIT2: Я обнаружил (2015) опубликованный материнский список всех тестов: «Больше, чем вы когда-либо хотели знать о синхронизации». «Синхронизация, измерение влияния синхронизации на параллельные алгоритмы» : вот fragment изображения, относящийся к этому вопросу.

введите описание изображения здесь

«Algo.4» является предшественником (старше, версия 2011 года) Brown et al., Упомянутым выше. (Я не знаю, насколько лучше или хуже версия 2014 года). «Алго.26» – это упоминаемое выше Херлихи; так как вы можете видеть, что он обрушивается на обновления и намного хуже на процессорах Intel, используемых здесь, чем на процессорах Sun от оригинальной бумаги. «Algo.28» – это ConcurrentSkipListMap из JDK; это не так, как можно было бы надеяться по сравнению с другими реализациями списков пропуска на основе CAS. Победителями, получившими высокую оценку, являются алгоритм Algo.2, основанный на блокировке (!!), описанный Crain et al. в «Дружественном к конкуренции двоичном дереве поиска» и «Algo.30» является «вращающимся скипистом» из «Логарифмических структур данных для мультикодов» . «Algo.29» – это «Нет запрещающего перехвата списка горячих точек» . Имейте в виду, что Грамоли является соавтором всех трех этих документов с алгоритмами поиска. «Algo.27» – это реализация списка пропусков Fraser для C ++.

Вывод Gramoli заключается в том, что намного проще испортить параллельную реализацию дерева на основе CAS, чем прикрутить аналогичный список пропусков. И, основываясь на цифрах, трудно не согласиться. Его объяснение этому факту:

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

Переопределение этой трудности было ключевой проблемой в недавней работе Брауна и др. У них есть целая отдельная (2013 г.) статья «Прагматические примитивы для неблокирующих структур данных» по созданию многоstreamовых примитивов LL / SC, которые они называют LLX / SCX, сами реализованы с использованием (машинного уровня) CAS. Brown et al. использовал этот строительный блок LLX / SCX в своей параллельной реализации в 2014 году (но не в 2011 году).

Я думаю, что, возможно, стоит также подвести итог фундаментальным идеям списка пропусков «без горячих точек» или «конкуренции» (CF) . Это добавляет существенную идею из расслабленных деревьев РБ (и аналогичных конгрессивно жарких структур данных): башни больше не создаются сразу после вставки, но откладываются до тех пор, пока не будет меньше конфликтов. И наоборот, удаление высокой башни может вызвать множество утверждений; это было замечено еще в 1990 году, когда Пью представлял собой параллельный лист с пропуском, поэтому Пью ввел разворот указателя на удаление (лакомый кусочек, который на странице Википедии в списках пропуска до сих пор не упоминается и по сей день, увы). Список пропусков CF делает это еще дальше и задерживает удаление верхних уровней высокой башни. Оба вида замедленных операций в списках пропуска CF списываются отдельным (например, на основе CAS) сборщиком мусорного коллектора, который его авторы называют «адаптирующей нитью».

Код Synchrobench (включая все проверенные алгоритмы) доступен по адресу: https://github.com/gramoli/synchrobench . Последний Brown et al. реализация (не включена в вышесказанное) доступна по адресу http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Кто-нибудь имеет 32-ядерную машину? J / K Я хочу сказать, что вы можете управлять ими сами.

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

На практике я обнаружил, что производительность B-дерева в моих проектах была лучше, чем списки пропуска. Списки пропусков кажутся более понятными, но внедрение B-дерева не так уж сложно.

Единственное преимущество, о котором я знаю, заключается в том, что некоторые умные люди разработали, как реализовать запретный параллельный список пропуска, который использует только атомарные операции. Например, Java 6 содержит class ConcurrentSkipListMap, и вы можете прочитать исходный код, если вы сумасшедший.

Но также не сложно написать параллельный вариант B-дерева – я видел, как это сделал кто-то другой – если вы предварительно разделите и объедините узлы «на всякий случай», когда идете по дереву, тогда вам не придется беспокоиться о взаимоблокировках и только когда-либо нужно держать замок на двух уровнях дерева за раз. Накладные расходы синхронизации будут немного выше, но B-дерево, вероятно, быстрее.

Из статьи Википедии, которую вы цитировали:

Операции Θ (n), которые заставляют нас посещать каждый узел в порядке возрастания (например, распечатывать весь список), обеспечивают возможность выполнить заглавную дерандомизацию структуры уровня перечня оптимальным образом, приведя список пропусков к O (log n) времени поиска. […] Список пропусков, на котором мы недавно не выполняли [любые такие] операции Θ (n), не обеспечивает те же самые наихудшие гарантии производительности в случае более традиционных сбалансированных структур древовидных данных , поскольку это всегда возможно (хотя и с очень низкой вероятностью), что монеты, используемые для создания списка пропусков, создадут плохо сбалансированную структуру

EDIT: так что это компромисс: Skip Lists использует меньше памяти с риском того, что они могут выродиться в несбалансированное дерево.

Списки пропуска реализуются с использованием списков.

Свободные решения для свободного доступа существуют для одно- и двусвязных списков, но нет решений без блокировки, которые непосредственно используют только CAS для любой структуры данных O (logn).

Однако вы можете использовать списки на основе CAS для создания списков пропуска.

(Обратите внимание, что MCAS, созданный с использованием CAS, разрешает создание произвольных структур данных и доказательство концепции красно-черного дерева было создано с использованием MCAS).

Так что, как ни странно, они оказываются очень полезными 🙂

Пропущенные списки имеют преимущество блокировки блокировки. Но время выполнения зависит от того, как определяется уровень нового узла. Обычно это делается с помощью Random (). В словаре из 56000 слов список пропусков занял больше времени, чем дерево splay, и дерево занимало больше времени, чем хеш-таблица. Первые два не могли соответствовать времени выполнения таблицы хеш-таблицы. Кроме того, массив хеш-таблицы также может быть заблокирован одновременно.

Список пропусков и аналогичные упорядоченные списки используются, когда требуется местность ссылки. Например: поиск рейсов следующий и до даты в заявке.

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

Пропустить Список Vs Splay Tree Vs Hash Table Runtime в словаре find op

Interesting Posts
Давайте будем гением компьютера.