Пропустить список - Skip list

Пропустить список
Тип	Список
Изобрел	1989
Изобретенный	В. Пью
Сложность времени в нотация большой O

В Информатика, а пропустить список это вероятностный структура данных это позволяет ${ Displaystyle { mathcal {O}} ( журнал п)}$ сложность поиска, а также ${ Displaystyle { mathcal {O}} ( журнал п)}$ сложность вставки в упорядоченная последовательность из ${ displaystyle n}$ элементы. Таким образом, он может получить лучшие характеристики отсортированного множество (для поиска) с сохранением связанный список -подобная структура, допускающая вставку, что невозможно в массиве. Быстрый поиск стал возможным благодаря поддержанию связанной иерархии подпоследовательностей, при которой каждая последующая подпоследовательность пропускает меньше элементов, чем предыдущая (см. Рисунок ниже справа). Поиск начинается с самой разреженной подпоследовательности до тех пор, пока не будут найдены два последовательных элемента, один меньше и один больше или равных искомому элементу. Через связанную иерархию эти два элемента связываются с элементами следующей самой разреженной подпоследовательности, где поиск продолжается до тех пор, пока мы, наконец, не начнем поиск во всей последовательности. Пропускаемые элементы можно выбрать вероятностно.^[2] или детерминированно,^[3] причем первое встречается чаще.

Описание

Схематическое изображение структуры данных списка пропуска. Каждое поле со стрелкой представляет собой указатель, а строка - связанный список давая разреженную подпоследовательность; пронумерованные поля (желтого цвета) внизу представляют упорядоченную последовательность данных. Поиск продолжается вниз от самой разреженной подпоследовательности вверху до тех пор, пока не будут найдены последовательные элементы, ограничивающие элемент поиска.

Список пропусков построен по слоям. Нижний слой - обычный заказанный связанный список. Каждый более высокий уровень действует как «экспресс-полоса» для списков ниже, где элемент в слое ${ displaystyle i}$ появляется в слое ${ displaystyle i + 1}$ с некоторой фиксированной вероятностью ${ displaystyle p}$ (два часто используемых значения для ${ displaystyle p}$ находятся ${ displaystyle 1/2}$ или же ${ displaystyle 1/4}$ ). В среднем каждый элемент появляется в ${ Displaystyle 1 / (1-р)}$ списки и самый высокий элемент (обычно специальный элемент заголовка в начале списка пропуска) во всех списках. Список пропуска содержит ${ Displaystyle журнал _ {1 / p} п ,}$ (т.е. основание логарифма ${ displaystyle 1 / p}$ из ${ displaystyle n}$ ) списки.

Поиск целевого элемента начинается с элемента head в верхнем списке и продолжается по горизонтали, пока текущий элемент не станет больше или равен целевому. Если текущий элемент равен целевому, он был найден. Если текущий элемент больше целевого или поиск достигает конца связанного списка, процедура повторяется после возврата к предыдущему элементу и вертикального перехода к следующему нижнему списку. Ожидаемое количество шагов в каждом связанном списке не более ${ displaystyle 1 / p}$ , что можно увидеть, проследив путь поиска назад от цели до достижения элемента, который появляется в следующем более высоком списке или до начала текущего списка. Следовательно, общая ожидал Стоимость поиска составляет ${ displaystyle { tfrac {1} {p}} log _ {1 / p} n}$ который ${ Displaystyle { mathcal {O}} ( журнал п) ,}$ , когда ${ displaystyle p}$ является константой. Выбирая разные значения ${ displaystyle p}$ , можно обменять затраты на поиск на затраты на хранение.

Детали реализации

Вставка элементов в список пропуска

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

Вставки и удаления реализуются так же, как соответствующие операции со связанными списками, за исключением того, что «высокие» элементы должны быть вставлены или удалены из более чем одного связанного списка.

${ Displaystyle { mathcal {O}} (п)}$ операции, которые заставляют нас посещать каждый узел в возрастающем порядке (например, распечатывать весь список), дают возможность выполнить дерандомизацию за кулисами структуры уровней пропускаемого списка оптимальным способом, в результате чего пропуск список для ${ Displaystyle { mathcal {O}} ( журнал п)}$ время поиска. (Выберите уровень i-го конечного узла равным 1 плюс количество раз, которое мы можем многократно разделить i на 2, прежде чем он станет нечетным. Кроме того, i = 0 для заголовка с отрицательной бесконечностью, поскольку у нас есть обычный специальный случай выбора максимально возможный уровень для отрицательных и / или положительных бесконечных узлов.) Однако это также позволяет кому-то узнать, где находятся все узлы выше уровня 1, и удалить их.

В качестве альтернативы мы могли бы сделать структуру уровней квазислучайной следующим образом:

сделать все узлы на уровне 1j ← 1пока количество узлов на уровне j> 1 делать    за каждый i-й узел на уровне j делать        если я странный и i не является последним узлом на уровне j, случайным образом выбирайте, повышать ли его до уровня j + 1 иначе если я даже и узел i-1 не был повышен до уровня j + 1 конец, если    повторение    j ← j + 1повторение

Как и дерандомизированная версия, квази-рандомизация выполняется только тогда, когда есть другие причины для запуска ${ Displaystyle { mathcal {O}} (п)}$ операция (которая посещает каждый узел).

Преимущество этой квазислучайности заключается в том, что она не выдает почти столько информации, связанной со структурой уровней, в состязательный пользователь как дерандомизированный. Это желательно, потому что злоумышленник, который может определить, какие узлы не находятся на самом низком уровне, может снизить производительность, просто удалив узлы более высокого уровня. (Бетеа и Райтер, однако, утверждают, что, тем не менее, злоумышленник может использовать вероятностные и временные методы, чтобы вызвать снижение производительности.^[4]) Производительность поиска по-прежнему гарантированно будет логарифмической.

Было бы заманчиво провести следующую «оптимизацию»: в части, которая гласит: «Далее для каждого яth ... ", забудьте о подбрасывании каждой четно-нечетной пары. Просто подбросьте монету один раз, чтобы решить, следует ли продвигать только четные или только нечетные. Вместо ${ Displaystyle { mathcal {O}} (п журнал п)}$ подбрасывает монету, будет только ${ Displaystyle { mathcal {O}} ( журнал п)}$ их. К сожалению, это дает злоумышленнику шанс 50/50 оказаться правым, если он предположит, что все узлы с четными номерами (среди узлов на уровне 1 или выше) выше первого уровня. И это несмотря на то свойство, что у него очень низкая вероятность угадать, что конкретный узел находится на уровне N для некоторого целого числа N.

Список пропуска не обеспечивает таких же абсолютных гарантий производительности в худшем случае, как более традиционный сбалансированное дерево структуры данных, потому что это всегда возможно (хотя и с очень низкой вероятностью^[5]), что подбрасывание монеты, использованное для построения списка пропусков, приведет к плохо сбалансированной структуре. Однако они хорошо работают на практике, и утверждается, что схему рандомизированной балансировки проще реализовать, чем схемы детерминированной балансировки, используемые в сбалансированных двоичных деревьях поиска. Списки пропуска также полезны в параллельные вычисления, где вставки могут выполняться в разные части списка пропусков параллельно без какой-либо глобальной перебалансировки структуры данных. Такой параллелизм может быть особенно полезен для обнаружения ресурсов в специальной беспроводная сеть потому что случайный список пропусков можно сделать устойчивым к потере любого отдельного узла.^[6]

Индексируемый скиплист

Как описано выше, список пропуска позволяет быстро ${ Displaystyle { mathcal {O}} ( журнал п)}$ вставка и удаление значений из отсортированной последовательности, но только медленная ${ Displaystyle { mathcal {O}} (п)}$ поиск значений в заданной позиции в последовательности (т.е. возвращает 500-е значение); однако с небольшими изменениями скорость произвольный доступ индексированные поиски можно улучшить до ${ Displaystyle { mathcal {O}} ( журнал п)}$ .

Для каждой ссылки также сохраните ширину ссылки. Ширина определяется как количество звеньев нижнего уровня, по которым проходит каждое из звеньев «скоростной полосы» более высокого уровня.

Например, вот ширина ссылок в примере вверху страницы:

   1 10 o ---> o ------------------------------------------ ---------------> o Верхний уровень 1 3 2 5 o ---> o ---------------> o ---- -----> o ---------------------------> o Уровень 3 1 2 1 2 3 2 o ---> o ---------> о ---> о ---------> о ---------------> о ------ ---> o Уровень 2 1 1 1 1 1 1 1 1 1 1 1 o ---> o ---> o ---> o ---> o ---> o ---> o- -> o ---> o ---> o ---> o ---> o Нижний уровень Глава 1-й 2-й 3-й 4-й 5-й 6-й 7-й 8-й 9-й 10-й Узел NIL Узел Узел Узел Узел Узел Узел Узел

Обратите внимание, что ширина ссылки более высокого уровня является суммой компонентных ссылок под ней (т.е. ссылка шириной 10 охватывает ссылки шириной 3, 2 и 5 непосредственно под ней). Следовательно, сумма всех ширин одинакова на всех уровнях (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

Чтобы проиндексировать список пропусков и найти i-е значение, просмотрите список пропусков, отсчитывая ширину каждой пройденной ссылки. Спускайтесь на уровень, если предстоящая ширина окажется слишком большой.

Например, чтобы найти узел в пятой позиции (Узел 5), перейдите по ссылке шириной 1 на верхнем уровне. Теперь необходимо еще четыре шага, но следующая ширина на этом уровне - десять, что слишком велико, поэтому опустите один уровень. Пройдите по одному звену шириной 3. Так как другой шаг шириной 2 будет слишком далеко, спуститесь до нижнего уровня. Теперь пройдитесь по последнему звену шириной 1, чтобы достичь целевой промежуточной суммы 5 (1 + 3 + 1).

функция lookupByPositionIndex (i) узел ← голова i ← i + 1 # не считайте голову за шаг    за уровень из верх к Нижний делать        пока i ≥ node.width [уровень] делать # если следующий шаг не слишком далеко            i ← i - ширина узла [уровень] # вычесть текущую ширину            узел ← node.next [уровень] # переход вперед на текущий уровень        повторение    повторение    возвращаться node.valueконечная функция

Этот метод реализации индексации подробно описан в Раздел 3.4 Операции с линейным списком в «Поваренной книге с пропускаемым списком» Уильяма Пью.

История

Пропускные списки были впервые описаны в 1989 г. Уильям Пью.^[7]

Процитирую автора:

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

Использование

Список приложений и фреймворков, использующих списки пропуска:

Портативная среда выполнения Apache реализует списки пропусков. Видеть Документация по APR 1.6
MemSQL использует списки пропусков без блокировки в качестве основной структуры индексации для своей технологии баз данных.
Cyrus IMAP сервер предлагает реализацию серверной базы данных "skiplist" (исходный файл )
Lucene использует списки пропуска для поиска списков сообщений с дельта-кодированием в логарифмическом времени.^{[нужна цитата ]}
QMap (до Qt 4) шаблонный класс Qt который предоставляет словарь.
Redis, постоянное хранилище ключей / значений с открытым исходным кодом ANSI-C для систем Posix, использует списки пропуска в своей реализации упорядоченных наборов.^[8]
nessDB, очень быстрое встроенное ядро СУБД типа "ключ-значение" (с использованием деревьев лог-структурированного слияния (LSM)), использует списки пропуска для своей таблицы памяти.
skipdb - это формат базы данных с открытым исходным кодом, использующий упорядоченные пары ключ / значение.
ConcurrentSkipListSet и ConcurrentSkipListMap в API Java 1.6. Использован Apache HBase.
Таблицы скорости представляют собой быстрое хранилище данных типа "ключ-значение" для Tcl, которое использует списки пропуска для индексов и разделяемую память без блокировки.
leveldb, библиотека быстрого хранения ключей и значений, написанная в Google, которая обеспечивает упорядоченное сопоставление строковых ключей со строковыми значениями
MuQSS Кон Коливаса^[9] Планировщик для ядра Linux использует списки пропуска
SkiMap использует списки пропуска в качестве базовой структуры данных для построения более сложной трехмерной разреженной сетки для систем картирования роботов.^[10]
IOWOW, стойкий C11 Библиотека хранения ключей / значений использует списки пропуска в качестве основной структуры данных.

Списки пропуска используются для эффективных статистических вычислений. из бегущие медианы (также известные как скользящие медианы). Списки пропуска также используются в распределенных приложениях (где узлы представляют физические компьютеры, а указатели представляют сетевые соединения) и для реализации высокомасштабируемых параллельных операций. приоритетные очереди с меньшим количеством конфликтов блокировки,^[11] или даже без блокировки,^[12]^[13]^[14] а также синхронные словари без блокировки.^[15] Есть также несколько патентов США на использование списков пропуска для реализации (без блокировки) очередей с приоритетом и параллельных словарей.^[16]

Смотрите также

внешняя ссылка

[cs.uwaterloo-1] а ^б Пападакис, Томас (1993). Списки пропусков и вероятностный анализ алгоритмов (PDF) (Кандидат наук.). Университет Ватерлоо.

[pugh-2] Пью, В. (1990). «Пропускаемые списки: вероятная альтернатива сбалансированным деревьям» (PDF). Коммуникации ACM. 33 (6): 668–676. Дои:10.1145/78973.78977.

[3] Манро, Дж. Ян; Пападакис, Томас; Седжвик, Роберт (1992). "Детерминированные списки пропусков" (PDF). Труды третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '92). Орландо, Флорида, США: Общество промышленной и прикладной математики, Филадельфия, Пенсильвания, США. С. 367–375. Дои:10.1145/139404.139478.

[4] Бетея, Даррелл; Рейтер, Майкл К. (21–23 сентября 2009 г.). Структуры данных с непредсказуемым временем (PDF). ESORICS 2009, 14-й Европейский симпозиум по исследованиям в области компьютерной безопасности. Сен-Мало, Франция. С. 456–471, §4 «Пропускные списки». Дои:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.

[5] Сен, Сандип (1991). «Некоторые замечания по пропускным спискам». Письма об обработке информации. 39 (4): 173–176. Дои:10.1016 / 0020-0190 (91) 90175-Н.

[6] Шах, Гаури (2003). Распределенные структуры данных для одноранговых систем (PDF) (Кандидатская диссертация). Йельский университет.

[7] Пью, Уильям (Апрель 1989 г.). Параллельное ведение списков пропусков (PS, PDF) (Технический отчет). Департамент компьютерных наук, Мэриленд. CS-TR-2222.

[8] "Реализация упорядоченного набора Redis".

[9] "LKML: Con Kolivas: [ОБЪЯВЛЕНИЕ] Multiple Queue Skiplist Scheduler версия 0.120". lkml.org. Получено 2017-05-11.

[10] Грегорио, Даниэле Де; Стефано, Луиджи Ди (2017). «SkiMap: эффективная картографическая структура для навигации роботов». arXiv:1704.05832 [cs.CV ].

[11] Shavit, N .; Лотан, И. (2000). «Очереди одновременных приоритетов на основе Skiplist» (PDF). Труды 14-го Международного симпозиума по параллельной и распределенной обработке. IPDPS 2000. п. 263. CiteSeerX 10.1.1.116.3489. Дои:10.1109 / IPDPS.2000.845994. ISBN 978-0-7695-0574-9.

[12] Sundell, H .; Цигас П. (2003). «Быстрые очереди одновременных приоритетов без блокировок для многопоточных систем». Труды Международного симпозиума по параллельной и распределенной обработке. п. 11. CiteSeerX 10.1.1.113.4552. Дои:10.1109 / IPDPS.2003.1213189. ISBN 978-0-7695-1926-5.

[13] Фомичев Михаил; Рупперт, Эрик (2004). Связанные списки без блокировки и списки пропуска (PDF). Proc. Ежегодный симпозиум ACM. по принципам распределенных вычислений (PODC). С. 50–59. Дои:10.1145/1011767.1011776. ISBN 1581138024.

[14] Bajpai, R .; Дхара, К. К .; Кришнасвами, В. (2008). «QPID: Распределенная очередь приоритета с местоположением элемента». Международный симпозиум IEEE 2008 г. по параллельной и распределенной обработке с приложениями. п. 215. Дои:10.1109 / ISPA.2008.90. ISBN 978-0-7695-3471-8.

[15] Sundell, H.K .; Цигас П. (2004). «Масштабируемые параллельные словари без блокировки» (PDF). Материалы симпозиума ACM 2004 г. по прикладным вычислениям - SAC '04. п. 1438. Дои:10.1145/967900.968188. ISBN 978-1581138122.

[16] Патент США 7937378

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Примечательный структуры данных
Типы	Коллекция Контейнер
Абстрактный	Ассоциативный массив Multimap Список Куча Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Multiset Непересекающееся множество
Массивы	Битовый массив Круглый буфер Динамический массив Хеш-таблица Дерево хешированных массивов Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Дерево двоичного поиска Дерево AA AVL дерево Красно-черное дерево Самобалансирующееся дерево Splay tree Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево R * дерево R + дерево R-дерево Гильберта Трие Хеш-дерево
Графики	Диаграмма двоичного решения Направленный ациклический граф Направленный ациклический граф слов
Список структур данных