Список пропуска и дерево двоичного поиска
Ответы 6
Из цитированной вами статьи Википедия:
Θ(n) operations, which force us to visit every node in ascending order (such as printing the entire list) provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to O(log n) search time. [...] A skip list, upon which we have not recently performed [any such] Θ(n) operations, does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure
Обновлено: так что это компромисс: списки пропуска используют меньше памяти из-за риска того, что они могут превратиться в несбалансированное дерево.
это было бы причиной против использования списка пропуска.
@askgelal: Я предполагал, что вы действительно прочитали статью, которую процитировали. Я думаю, вы хотели сказать: "Пожалуйста, прекратите прямо ..."
цитируя MSDN: «Шансы [для 100 элементов уровня 1] равны 1 из 1 267 650 600 228 229 401 496 703 205 376».
Почему вы сказали, что они используют меньше памяти?
@peterchen: Конечно, но какой случай патологический?
@Jon: Высота списка пропуска выбирается случайным образом, поэтому с конечной вероятностью все в конечном итоге будут равны 1.
@peterchen: Понятно, спасибо. Значит, этого не происходит с детерминированными списками пропусков? @Mitch: «Списки пропуска используют меньше памяти». Как списки пропуска используют меньше памяти, чем сбалансированные двоичные деревья? Похоже, у них есть 4 указателя в каждом узле и повторяющиеся узлы, тогда как у деревьев есть только 2 указателя и нет дубликатов.
@Jon Harrop: Узлам первого уровня нужен только один указатель на узел. Любым узлам на более высоких уровнях требуется только два указателя на узел (один на следующий узел и один на уровень ниже), хотя, конечно, узел уровня 3 означает, что вы используете всего 5 указателей для этого одного значения. Конечно, это по-прежнему будет занимать много памяти (больше, чем двоичный поиск, если вам нужен бесполезный список пропусков и большой набор данных) ... но я думаю, что я чего-то упускаю ...
Кроме того, в дополнение к приведенным ответам (простота реализации в сочетании с сопоставимой производительностью для сбалансированного дерева). Я считаю, что реализация обхода по порядку (вперед и назад) намного проще, потому что пропускаемый список фактически имеет связанный список внутри своей реализации.
Разве обход по порядку для дерева бинов не такой простой, как: «def func (node): func (left (node)); op (node); func (right (node))»?
Конечно, это правда, если вы хотите обойти все за один вызов функции. но это становится намного более раздражающим, если вы хотите иметь обход в стиле итератора, как в std :: map.
@Evan: Не на функциональном языке, где можно просто писать на CPS.
@ Эван: def iterate(node): for child in iterate(left(node)): yield child; yield node; for child in iterate(right(node)): yield child;? знак равно нелокальное управление iz awesom .. @Jon: писать в CPS - это боль, но, может быть, вы имеете в виду с продолжениями? генераторы в основном являются частным случаем продолжений для python.
@Claudiu: это примерно эквивалент it++? Если так, то это ужасно неэффективно.
@Evan: нет, это код для настройки итерации. эквивалент it++ будет вызывать .next() в результирующем генераторе. чтобы выполнить итерацию, вы бы сделали: for child in iterate(head): op(child).
@Claudui: а что, если у вас просто есть экземпляр итератора, и вы просто хотите следующий? Даже если карта изменилась с тех пор, как вы получили этот итератор (что нормально для многих случаев использования std::map), это все еще работает?
@Evan: да, это работает, пока параметр узла вырезан из дерева во время модификации. Обход C++ имеет такое же ограничение.
Списки пропуска более удобны для одновременного доступа / модификации. Херб Саттер написал статья о структуре данных в параллельных средах. Здесь более подробная информация.
Наиболее часто используемая реализация двоичного дерева поиска - это красно-черное дерево. Одновременные проблемы возникают, когда дерево модифицируется, часто его нужно перебалансировать. Операция перебалансировки может повлиять на большие части дерева, что потребует блокировки мьютекса на многих узлах дерева. Вставка узла в список пропуска гораздо более локализована, необходимо заблокировать только узлы, напрямую связанные с затронутым узлом.
Обновление от комментариев Джона Харропса
Я прочитал последнюю статью Фрейзера и Харриса Параллельное программирование без блокировок. Действительно хороший материал, если вас интересуют структуры данных без блокировок. В статье основное внимание уделяется Транзакционная память и теоретической операции многословного сравнения и обмена MCAS. Оба они моделируются в программном обеспечении, поскольку оборудование еще не поддерживает их. Я очень впечатлен тем, что они вообще смогли встроить MCAS в программное обеспечение.
Я не нашел особенно привлекательным работу с транзакционной памятью, поскольку она требует сборщика мусора. Также программная транзакционная память страдает от проблем с производительностью. Однако я был бы очень рад, если аппаратная транзакционная память когда-нибудь станет обычным явлением. В конце концов, это все еще исследования, и они не будут использоваться в производственном коде еще около десяти лет.
В разделе 8.2 они сравнивают производительность нескольких параллельных реализаций дерева. Обобщу их выводы. Скачать PDF-файл стоит, так как он содержит очень информативные графики на страницах 50, 53 и 54.
- Блокировка списков пропусков безумно быстр. Они невероятно хорошо масштабируются с количеством одновременных доступов. Это то, что делает списки пропусков особенными, другие структуры данных, основанные на блокировках, имеют тенденцию к сбою под давлением.
- Списки пропусков без блокировки постоянно быстрее, чем блокировка списков пропусков, но лишь ненамного.
- списки пропусков транзакций стабильно в 2-3 раза медленнее, чем блокирующая и неблокирующая версии.
- запирание красно-черных деревьев квакает при одновременном доступе. Их производительность линейно снижается с каждым новым одновременным пользователем. Из двух известных реализаций красно-черного дерева с блокировкой одна, по сути, имеет глобальную блокировку во время ребалансировки дерева. Другой использует причудливую (и сложную) эскалацию блокировки, но все же не значительно превосходит версию с глобальной блокировкой.
- свободные от замков красно-черные деревья не существует (больше не верно, см. Обновление).
- транзакционные красно-черные деревья сравнимы с транзакционными пропускаемыми списками. Это было очень удивительно и многообещающе. Транзакционная память, хотя и медленнее, но ее гораздо легче писать. Это может быть так же просто, как быстрый поиск и замена на непараллельную версию.
Обновить
Вот статья о деревьях без блокировок: Свободные от блокировки красно-черные деревья с использованием CAS.
Я не вникал в это глубоко, но на первый взгляд кажется твердым.
Не говоря уже о том, что в невырожденном скиплисте около 50% узлов должны иметь только одну ссылку, что делает вставку и удаление чрезвычайно эффективными.
Для ребалансировки не требуется блокировка мьютекса. См. cl.cam.ac.uk/research/srg/netos/lock-free
@ Джон, да и нет. Не существует известных реализаций красно-черного дерева без блокировок. Фрейзер и Харрис показывают, как реализовано красно-черное дерево на основе транзакционной памяти, и его производительность. Транзакционная память все еще очень активно используется в исследованиях, поэтому в производственном коде красно-черное дерево все еще должно блокировать большие части дерева.
Я хотел обновить этот ответ. В настоящее время существует два эффективных дерева двоичного поиска на основе блокировок. Один основан на деревьях AVL (dl.acm.org/citation.cfm?id=1693488), а другой (Внимание! Бесстыдный плагин) основан на красно-черных деревьях. См. actapress.com/Abstract.aspx?paperId=453069
@JuanBesa, «На 14% лучше, чем самые известные решения для параллельных словарей». Вы сравниваете с пропускаемыми списками? Другая статья непреднамеренно указывает, что деревья на основе блокировок - это O(n) для n <90, тогда как skiplists (также словарь) - это O(1)! 14% кажется недостаточным, когда O настолько разрознен.
Думаю, я попытаюсь применить этот базовый механизм к AVL. Как я понял из беглого чтения, основное решение вращения (которое является фундаментальной проблемой) - это иметь блок повтора, который представляет собой подъем флагов в элементах, которые вам нужно контролировать - если вы можете поднять их все, тогда вы можете продолжить, так как другие потоки потерпят неудачу и будут пытаться получить эти флаги. Простой гений!
@BlankXavier, Хммм, это подозрительно похоже на использование спин-блокировки вместо мьютекса для обычного дерева на основе блокировок. Он может быть более производительным, но я хочу увидеть некоторые тесты. В частности, против скиплистов без замков и скиплистов с запиранием.
Все вспомогательные механизмы по сути являются вращающимися механизмами - это просто вместо тупого вращения, которое не выполняет никакой работы, вращая вспомогательный механизм который, если он завершится, позволит вам продолжить свою работу, тогда вы делаете что-то полезное - вы фактически свободны от блокировки ...
@deft_code: Intel недавно объявила о реализации транзакционной памяти через TSX на Haswell. Это может оказаться интересным по сравнению с теми структурами данных без блокировки, которые вы упомянули.
Есть комментарии к Недавний ответ Respawned Fluff?
Я думаю, что Ответ Физза более актуален (с 2015 года), чем этот ответ (2012 год), и поэтому, вероятно, к настоящему времени должен быть предпочтительным ответом.
На практике я обнаружил, что производительность B-дерева в моих проектах лучше, чем у пропускаемых списков. Списки пропуска кажутся более легкими для понимания, но реализовать B-дерево не сложно.
Единственное преимущество, о котором я знаю, заключается в том, что некоторые умные люди разработали, как реализовать безблокирующий список одновременных пропусков, который использует только атомарные операции. Например, Java 6 содержит класс ConcurrentSkipListMap, и вы можете прочитать его исходный код, если вы сошли с ума.
Но также нетрудно написать параллельный вариант B-дерева - я видел, как это делал кто-то другой - если вы превентивно разделите и объедините узлы «на всякий случай», когда вы идете вниз по дереву, вам не придется беспокоиться о взаимоблокировках и когда-либо нужно удерживать блокировку только на двух уровнях дерева одновременно. Накладные расходы на синхронизацию будут немного выше, но B-дерево, вероятно, работает быстрее.
Думаю, не стоит называть Binary Tree B-Tree, есть совершенно другой DS с таким именем.
Списки пропуска реализованы с помощью списков.
Решения без блокировки существуют для односвязных и двусвязных списков, но не существует решений без блокировки, которые напрямую используют только CAS для любой структуры данных O (logn).
Однако вы можете использовать списки на основе CAS для создания списков пропуска.
(Обратите внимание, что MCAS, который создается с использованием CAS, допускает произвольные структуры данных, и доказательство концепции красно-черное дерево было создано с использованием MCAS).
Так что, как ни странно, они оказались очень полезными :-)
«не существует безблокировочных решений, которые напрямую используют только CAS для любой структуры данных O (logn)». Не правда. Примеры счетчиков см. В cl.cam.ac.uk/research/srg/netos/lock-free.
У списков пропуска есть преимущество снятия блокировки. Но время короткого замыкания зависит от того, как определяется уровень нового узла. Обычно это делается с помощью Random (). В словаре из 56000 слов список пропуска занял больше времени, чем развернутое дерево, а дерево заняло больше времени, чем хеш-таблица. Первые два не могут соответствовать времени выполнения хеш-таблицы. Кроме того, массив хеш-таблицы может быть заблокирован одновременно.
Список пропуска и аналогичные упорядоченные списки используются, когда требуется указание местонахождения. Например: поиск рейсов до и до даты в приложении.
Расширяемое дерево двоичного поиска в памяти является отличным и более часто используемым.
Я бегло посмотрел, и ваши результаты показывают, что SkipList работает быстрее, чем SplayTree.
Ошибочно предполагать рандомизацию как часть пропускаемого списка. То, как пропускаются элементы, имеет решающее значение. Для вероятностных структур добавлена рандомизация.
Масштабируемость. См. Доказанно правильный масштабируемый список одновременных пропусков и поиск "пропустить список" одновременно, который показывает 1,024 запись Intel Threading Challenge 2010. Более плоская форма списка пропуска упрощает и упрощает одновременные изменения.