Недавно я столкнулся с структурой данных, известной как Skip list. Кажется, что они очень похожи на двоичное дерево поиска ... мой вопрос: зачем вам когда-либо хотеть использовать список пропуска через двоичное дерево поиска?Пропустить Список против двоичного дерева
Пропустить списки более поддаются одновременному доступу/модификации. Херб Саттер написал article о структуре данных в параллельных средах. Он имеет более глубокую информацию.
Наиболее часто используемой реализацией двоичного дерева поиска является red-black tree. Параллельные проблемы возникают при изменении дерева, которое часто требуется для балансировки. Операция перебалансировки может влиять на большие части дерева, что потребует блокировки мьютекса на многих узлах дерева. Вставка узла в список пропуска намного локализована, только узлы, непосредственно связанные с затронутым узлом, должны быть заблокированы.
Обновление от Jon Harrops комментарии
Я прочитал последнюю статью Фрейзер и Харриса Concurrent programming without locks. Действительно хорошие вещи, если вас интересуют блокированные структуры данных. В документе основное внимание уделяется Transactional Memory и теоретической операции multi-compare-and-swap MCAS. Оба они имитируются в программном обеспечении, пока их не поддерживает. Я довольно впечатлен тем, что они смогли создать MCAS в программном обеспечении вообще.
Я не нашел материал транзакционной памяти, особенно убедительный, поскольку для этого требуется сборщик мусора. Также software transactional memory страдает от проблем с производительностью. Тем не менее, я был бы очень рад, если аппаратная транзакционная память станет обычной. В конце концов, это все еще исследование и не будет использоваться для производственного кода еще на десятилетие или около того.
В разделе 8.2 они сравнивают производительность нескольких параллельных реализаций дерева. Я обобщу их выводы. Это стоит того, чтобы загрузить pdf, так как на страницах 50, 53 и 54 у него есть очень информативные графики.
Update
Вот статья о безблокировочного деревьев: Lock-Free Red-Black Trees Using CAS.
Я не заглянул в него глубоко, но на поверхности он кажется твердым.
Из Wikipedia статьи вы цитируемая:
Q (п) операции, которые заставляют нас посетить каждый узел в порядке возрастания (например, печать всего списка) дает возможность выполнить заколонный -цены для рандомизации структуры уровня скип-листа оптимальным способом, приведя список пропусков к O (log n) времени поиска. [...] Перечня пропуска, на которых мы не имеем недавно выполненные [любые такие] Q (п) операций, не обеспечивают ту же абсолютное наихудший гарантии исполнения, как более традиционных данных сбалансировано деревом структуры, потому что это всегда возможно (хотя и с очень низкой вероятности), что монета-щелчки используются для создания списка пропуска, производящим плохо сбалансированной структуру
EDIT: так что это компромисс : Пропустить списки используют меньше памяти, рискуя тем, что y может выродиться в несбалансированное дерево.
Это было бы поводом для использования списка пропусков. – Claudiu 2008-11-02 04:50:45
@askgelal: Я предполагал, что вы действительно прочитали статью, которую вы на самом деле цитировали. Я думаю, вы хотели сказать «Пожалуйста, остановитесь прямо ...» – 2008-11-02 05:43:18
, цитируя MSDN, «Шансы [для 100 элементов уровня 1] составляют точно 1 в 1 267 650 600 228 229 401 496 703 205 376». – peterchen 2008-11-02 10:03:39
Кроме того, в дополнение к ответам (простота реализации в сочетании с сопоставимой производительностью с сбалансированным деревом). Я нахожу, что реализация обхода в порядке (вперед и назад) намного проще, потому что в пропуске список имеет связанный список внутри своей реализации.
На практике я обнаружил, что производительность B-дерева в моих проектах улучшилась лучше, чем пропуски. Списки пропусков кажутся более понятными, но внедрение B-дерева не , что сложно.
Единственное преимущество, о котором я знаю, состоит в том, что некоторые умные люди разработали, как реализовать запретный параллельный список пропуска, который использует только атомарные операции. Например, Java 6 содержит класс ConcurrentSkipListMap, и вы можете прочитать исходный код, если вы сумасшедший.
Но не так сложно написать параллельный вариант B-дерева либо - я видел, как это сделал кто-то другой - если вы предварительно разделите и объедините узлы «на всякий случай», когда идете по дереву, тогда вы выиграли не нужно беспокоиться о тупиках, и только когда-либо нужно держать замок на двух уровнях дерева за раз. Накладные расходы синхронизации будут немного выше, но B-дерево, вероятно, быстрее.
Списки пропусков реализованы с использованием списков.
Решения, защищенные от блокировки, существуют для одно- и двусвязных списков, но нет решений без блокировки, которые непосредственно используют только CAS для любой структуры данных O (logn).
Однако вы можете использовать списки на основе CAS для создания списков пропуска.
(Обратите внимание, что MCAS, созданный с использованием CAS, допускает создание произвольных структур данных и доказательство концепции красно-черного дерева, созданного с использованием MCAS).
Так, странно, как они есть, они оказываются очень полезной :-)
Пропустить Списки есть преимущество блокировки вскрыши. Но время выполнения зависит от того, как определяется уровень нового узла. Обычно это делается с помощью Random(). В словаре из 56000 слов список пропусков занял больше времени, чем дерево splay, и дерево занимало больше времени, чем хеш-таблица. Первые два не могли соответствовать времени выполнения таблицы хеш-таблицы. Кроме того, массив хеш-таблицы также может быть заблокирован одновременно.
Пропустить Список и аналогичные упорядоченные списки используются, когда требуется местность ссылки. Например: поиск рейсов следующий и до даты в заявке.
Исключительное бинарное дерево поиска широко используется и используется чаще.
Skip List Vs Splay Tree Vs Hash Table Runtime on dictionary find op
Во-первых, вы не можете достаточно сравнить рандомизированное структуру данных, с той, что дает вам наихудшие гарантии.
Список пропусков эквивалентен случайно сбалансированному двоичному дереву поиска (RBST) таким образом, который более подробно объясняется в Dean and Jones '"Exploring the Duality Between Skip Lists and Binary Search Trees".
С другой стороны, вы также можете иметь детерминированные списки пропусков, которые гарантируют наихудшую производительность, ср. Munro et al.
В соответствии с некоторыми утверждениями выше вы можете иметь реализации двоичных поисковых деревьев (BST), которые хорошо работают при параллельном программировании. Потенциальная проблема с ориентированными на параллелизм BST заключается в том, что вы не можете легко получить то же самое, что и гарантии относительно балансировки, как и из дерева с красно-черным (RB). (Но «стандартные», то есть случайные, списки пропуска не дают вам этих гарантий.) Существует компромисс между поддержанием баланса в любое время и хорошим (и простым в программировании) одновременным доступом, поэтому relaxed Деревья RB обычно используется, когда желателен хороший параллелизм. Релаксация заключается в том, чтобы сразу не переустанавливать дерево. Для несколько датированного (1998 г.) обзора см. «Эффективность параллельных алгоритмов красно-черного дерева» Ханке «[ps.gz].
Одним из последних усовершенствований является так называемое хроматическое дерево (в основном у вас есть такой вес, чтобы черный был 1, а красный был бы нулевым, но вы также допускали бы значения между ними). И как цветовое дерево связано с пропуском? Давайте посмотрим, что Браун и др. "A General Technique for Non-blocking Trees" (2014) должен сказать:
с 128 потоков, наш алгоритм обгоняет в Java неблокирующая skiplist на 13% до 156%, блокировки на основе AVL дерева Bronson и др. на 63% до 224%, и RBT, которая использует программное обеспечение транзакционной памяти (STM) на 13 до 134 раз
EDIT добавить: блокировки на основе списка пропуску Pugh, которая была пересматриваться по сравнению с Фрейзером и Harris (2007) "Concurrent Programming Without Lock" как приближающийся к своей собственной версии без блокировки (точка, на которую настойчиво настаивает в верхнем ответе), также настраивается для хорошей параллельной работы, ср. Pugh's "Concurrent Maintenance of Skip Lists", хотя и довольно мягким способом. Тем не менее одна новая/2009 статья "A Simple Optimistic skip-list Algorithm" от Herlihy и др., В которой предлагается предположительно более простая (чем у Пью) реализация на основе блокировки совпадающих списков пропуска, критикует Пью за то, что он не предоставил доказательств правильности, достаточно убедительных для них. Оставив в стороне этот (возможно, слишком педантичный) характер, 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 опубликован) материнство всех тестов: "More Than You Ever Wanted to Know about Synchronization. Synchrobench, Measuring the Impact of the Synchronization on Concurrent Algorithms" Gramoli: Вот выдержка из этого вопроса.
"Algo.4" является предшественником (старше, 2011 версии) Брауна и др. Упоминается выше. (Я не знаю, насколько лучше или хуже версия 2014 года). «Алго.26» - это упоминаемое выше Херлихи; так как вы можете видеть, что он обрушивается на обновления и намного хуже на процессорах Intel, используемых здесь, чем на процессорах Sun от оригинальной бумаги. «Algo.28» - это ConcurrentSkipListMap из JDK; это не так, как можно было бы надеяться по сравнению с другими реализациями списков пропуска на основе CAS. Победителями, получившими высокую оценку, являются алгоритм Algo.2, основанный на блокировке (!!), описанный Crain et al. в "A Contention-Friendly Binary Search Tree" и «Algo.30» является «вращающимся скипистом» от "Logarithmic data structures for multicores". «Algo.29» - это "No hot spot non-blocking skip list". Имейте в виду, что Грамоли является соавтором всех трех этих документов с алгоритмами поиска. «Algo.27» - это реализация списка пропусков Fraser для C++.
Вывод Gramoli заключается в том, что намного проще испортить параллельную реализацию дерева на основе CAS, чем прикрутить аналогичный список пропусков. И, основываясь на цифрах, трудно не согласиться. Его объяснение этого факта:
Сложность в разработке дерева, которое безблокировочный проистекает из трудности изменения нескольких ссылок атомарны. Списки пропуска состоят из башен, соединенных друг с другом с помощью указателей-последователей и , в которых каждый узел указывает на узел сразу под ним. Они равны , которые часто считаются похожими на деревья, потому что каждый узел имеет преемник в башне-предшественнике и ниже его, однако основное отличие - , что указатель вниз является, как правило, неизменным, что упрощает атомарную модификацию узла. Это различие, вероятно, является причиной того, почему списки пропуска превышают деревья при сильных конфликтах , как показано на рисунке [выше].
Преодоление этой трудности было ключевой проблемой в недавней работе Брауна и др. У них есть отдельная (2013 г.) бумага "Pragmatic Primitives for Non-blocking Data Structures" о создании «примитивов» с множеством записей LL/SC, которые они называют LLX/SCX, сами реализованы с использованием (машинного уровня) CAS. Brown et al. использовал этот строительный блок LLX/SCX в своей параллельной реализации в 2014 году (но не в 2011 году).
Я думаю, что, возможно, стоит также обобщить основные идеи "no hot spot"/contention-friendly (CF) skip list. Это добавляет существенную идею из расслабленных деревьев РБ (и аналогичных конгрессивно жарких структур данных): башни больше не создаются сразу после вставки, но откладываются до тех пор, пока не будет меньше конфликтов.И наоборот, удаление высокой башни может вызвать множество утверждений; это было замечено в 1990 году одновременно с совпадающим списком пропусков Пью в 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 Я хочу сказать, что вы можете управлять ими сами.
Возможно, вы захотите также посмотреть на деревья. Они также довольно легко внедряются и стремятся к равновесию. Я попытался бы избежать рандомизированных алгоритмов аппроксимации (например, списков пропуска), если вы собираетесь писать модульные тесты для структуры данных. – Cybis 2008-11-02 05:30:30
Кроме того, рандомизация в алгоритме служит цели, которая является внутренней для списка пропусков. Его интерфейс остается тем же, что и является интерфейсом сортированного словарного типа структуры. Рандомизация не влияет на ожидаемое поведение. Модульные тесты должны тестировать публичное поведение структуры данных, как описано в ее интерфейсе с клиентским кодом, а не с внутренними элементами реализации. – Ernesto 2012-04-05 18:12:39
Если вы отказываетесь от совершенно хорошего решения, потому что это может быть сложно записать для него единичные тесты, вы делаете это неправильно. Модульные тесты должны служить вашему приложению, а не наоборот. – 2010-05-26 05:57:28