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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

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