Пропустите список по сравнению с деревом двоичного поиска
5 ответов
Списки пропуска более поддаются параллельному доступу/модификации. Herb Sutter записал статья о структуре данных в параллельных средах. Это имеет больше всесторонней информации.
наиболее часто используемая реализация дерева двоичного поиска красно-черное дерево . Параллельные проблемы входят, когда дерево изменяется, оно часто должно изменять баланс. Операция восстановления равновесия может влиять на значительные части дерева, которое потребовало бы, чтобы взаимное исключение соединило многие древовидные узлы. Вставка узла в список пропуска намного более локализуется, только узлы, непосредственно связанные с затронутым узлом, должны быть заблокированы.
<час>Обновление из комментариев Jon Harrops
я считал Фрейзер и последнюю статью Harris Параллельное программирование без блокировок . Действительно хороший материал, если Вы интересуетесь структурами данных без блокировок. Работа фокусируется на Транзакционная Память и теоретическая операция multiword-compare-and-swap MCAS. Оба из них моделируются в программном обеспечении как никакая поддержка оборудования их все же. Я справедливо впечатлен, что они смогли создать MCAS в программном обеспечении вообще.
я не нашел транзакционный материал памяти особенно востребованным, поскольку он требует сборщика "мусора". Также программное обеспечение транзакционная память заполоняется с проблемами производительности. Однако я был бы очень взволнован, если аппаратные средства транзакционная память когда-нибудь распространены. В конце это - все еще исследование и не будет полезно для производственного кода в течение другого десятилетия или около этого.
раздел In 8.2 они сравнивают выполнение нескольких параллельных древовидных реализаций. Я буду суммировать их результаты. Это стоит того для загрузки PDF, поскольку это имеет некоторые очень информативные графики на страницах 50, 53, и 54.
- списки пропуска Блокировки безумно быстры. Они масштабируются невероятно хорошо с количеством параллельных доступов. Это - то, что входит в особенные списки пропуска, другие основанные на блокировке структуры данных имеют тенденцию каркать под давлением.
- списки пропуска без Блокировок последовательно быстрее, чем блокировка списков пропуска, но только едва.
- транзакционные списки пропуска последовательно в 2-3 раза медленнее, чем блокировка и версии без блокировки.
- блокирующие красно-черные деревья карканье под параллельным доступом. Их производительность ухудшается линейно с каждым новым параллельным пользователем. Из двух известных блокирующих красно-черных древовидных реализаций у каждого по существу есть глобальная блокировка во время древовидного изменения баланса. Другое воображение использования (и сложный) повышение уровня блокировок, но все еще значительно не выполняет глобальную версию блокировки.
- красно-черные деревья без блокировок не существуют (больше верный, посмотрите Обновление).
- транзакционные красно-черные деревья сопоставимы с транзакционными списками пропуска. Это было очень удивительно и очень перспективно. Транзакционная память, хотя медленнее, если намного легче записать. Это может быть столь же легко как быстрый поиск и замена на непараллельной версии.
Обновление
Вот бумага о деревьях без блокировок: Красно-черные Деревья без Блокировок Используя CAS.
я не изучил его глубоко, но на поверхности это кажется твердым.
Кроме того, в дополнение к данным ответам (простота реализации, объединенной с сопоставимой производительностью к сбалансированному дереву). Я нахожу, что реализация, чтобы обход (вперед и назад) намного более прост, потому что список пропуска эффективно имеет связанный список в своей реализации.
На практике я нашел, что производительность B-дерева на моих проектах удалась, чтобы быть лучше, чем списки пропуска. Списки пропуска действительно кажутся легче понять, но реализация B-дерева не это трудно.
одно преимущество, о котором я знаю, состоит в том, что некоторые умные люди разработали, как реализовать параллельный список пропуска без блокировок, который только использует атомарные операции. Например, Java 6 содержит класс ConcurrentSkipListMap, и можно считать исходный код в него, если Вы являетесь сумасшедшими.
, Но не слишком трудно записать параллельному варианту B-дерева любого - я видел сделанный кем-то еще - если Вы преимущественно разделяете и объединяете узлы "на всякий случай", поскольку Вы спускаетесь с дерева тогда, Вы не должны будете волноваться о мертвых блокировках и только когда-либо должны держать блокировку на двух уровнях дерева за один раз. Синхронизация наверху будет немного выше, но B-дерево, вероятно, быстрее.
От статья Wikipedia Вы заключили в кавычки:
О (n) операции, которые вынуждают нас посетить каждый узел в порядке возрастания (такой как печать всего списка) обеспечивают возможность выполнить закулисную дерандомизацию структуры уровня списка пропуска оптимальным способом, принося список пропуска к O (зарегистрируйте n), время поиска. [...] список пропуска, в котором мы недавно не выполнили [никакой подобный] О (n) операции, , не обеспечивает те же абсолютные гарантии исполнения худшего случая как более традиционные структуры данных сбалансированного дерева , потому что это всегда возможно (хотя с очень низкой вероятностью), что подбрасывания монеты, используемые для создания списка пропуска, произведут плохо сбалансированную структуру
РЕДАКТИРОВАНИЕ: таким образом, это - компромисс: Пропустите использование Списков меньше памяти в риске, что они могли бы ухудшиться в несбалансированное дерево.
Списки пропуска реализованы с помощью списков.
Бесплатные решения блокировки существуют для отдельно и двунаправленные связанные списки - но нет никакой блокировки бесплатных решений который непосредственно с помощью только CAS для любого O (logn) структура данных.
Можно однако использовать основанные на CAS списки для создания списков пропуска.
(Обратите внимание, что MCAS, который создается с помощью CAS, разрешает произвольные структуры данных и подтверждение концепции, красно-черное дерево было создано с помощью MCAS).
Так, нечетный, как они, они оказываются очень полезными :-)