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

Ответ 1

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

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

Там также апплет с бегущей демонстрацией. Cute 90 Java shininess здесь:

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

Смотрите оригинальную бумагу [pdf] от William Pugh

Ответ 5

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

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

Это было написано на С# и потребовалось несколько итераций, чтобы успешно работать.

Ответ 6

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

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

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