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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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