Пропускать списки - когда-нибудь их использовали?

Question

Мне интересно, использовал ли кто-нибудь здесь список пропуска . Он имеет примерно те же преимущества, что и сбалансированное бинарное дерево, но проще в реализации. Если у вас есть, вы написали свою собственную или использовали предварительно написанную библиотеку (и если да, то как она называлась)?

Answer 1

Насколько я понимаю, они не столько полезная альтернатива двоичным деревьям (например, красно-черные деревья), сколько B-деревьям для использования в базе данных, что вы можете уменьшить количество уровней до приемлемого минимума и иметь дело с журналами w / base-K, а не журналами base-2 для получения характеристик производительности. Алгоритмы для вероятностных списков пропусков (IMHO) проще понять, чем соответствующие алгоритмы B-дерева. Плюс есть некоторая литература по спискам пропусков без блокировки. Я смотрел на их использование несколько месяцев назад, но затем отказался от попыток найти библиотеку HDF5 .

литература по теме:

Документы Билла Пью:

• Список пропущенных поваренных книг
• Пропуск списков: вероятностная альтернатива сбалансированным деревьям
• Одновременное ведение списков пропусков

неакадемических работ / учебных пособий:

• Eternally Confuzzled (обсуждается несколько структур данных)
• "Пропустить списки" Томас А. Анастасио

Answer 2

На самом деле, для одного из моих проектов я реализую свой собственный полный STL. И я использовал skiplist для реализации моего std::map. Причина, по которой я пошел с этим, состоит в том, что это простой алгоритм, который очень близок к производительности сбалансированного дерева, но имеет намного более простых возможностей итерации.

Кроме того, QMap Qt4 также был скиплистом, который послужил источником вдохновения для его использования в моем std::map.

Answer 3

Java 1.6 (Java SE 6) представила ConcurrentSkipListSet и ConcurrentSkipListMap в структуре коллекций. Итак, я бы предположил, что кто-то там действительно использует их.

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

См. оригинал статьи [pdf] Уильяма Пью.

Answer 4

Несколько лет назад я реализовал свой собственный класс для вероятностных алгоритмов. Я не знаю ни о каких реализациях библиотеки, но это было давно. Это довольно просто реализовать. Насколько я помню, у них были действительно хорошие свойства для больших наборов данных, и они избежали некоторых проблем с перебалансировкой. Я думаю, что реализация также проще, чем бинарные попытки в целом. Здесь есть хорошее обсуждение и пример кода на C ++:

http://www.ddj.us/cpp/184403579?pgno=1

Есть также апплет с запущенной демонстрацией. Симпатичные девяностые блестки здесь:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

Answer 5

Я реализовал вариант, который я назвал Reverse Skip List для механизма правил несколько лет назад. Почти то же самое, но ссылочные ссылки идут назад от последнего элемента.

Это потому, что это было быстрее для вставки отсортированных элементов, которые были наиболее вероятны к концу коллекции.

Он был написан на C # и занял несколько итераций для успешной работы.

Answer 6

Пропуск списков прост в реализации. Но, корректируя указатели в списке пропуска в случае вставки и удаления, вы должны быть осторожны. Не использовал это в реальной программе, но имел некоторое время профилирования. Списки пропуска отличаются от деревьев поиска. Сходство в том, что оно дает среднее log (n) за период словарных операций, как и у дерева сплайнов. Это лучше, чем несбалансированное дерево поиска, но не лучше, чем сбалансированное дерево.

Каждый узел списка пропуска имеет прямые указатели, которые представляют соединения current-> next () с различными уровнями списка пропуска. Обычно этот уровень ограничен максимумом ln (N). Поэтому, если N = 1 миллион, уровень равен 13. Будет много указателей, а в Java это означает количество указателей для реализации эталонных типов данных. где сбалансированное дерево поиска имеет меньше и дает то же время выполнения !!.

SkipList Vs Splay Tree Vs Hash Как показано для поиска по словарю, хэш-таблица с удаленной блокировкой даст результат менее 0,010 мс, в то время как Splay Tree дает ~ 1 мс и список пропуска ~ 720 мс.