Списки пропуска — когда-нибудь ими пользовались?

StackOverflow https://stackoverflow.com/questions/234560

Вопрос

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

Статьи Билла Пью:

неакадемические статьи/руководства:

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top