Пропустить список

Пропустить список
Пропустить список
Тип	Список
Изобретенный	1989
Изобретён	В. Пью
Операция
Временная сложность в обозначении большого О
Операция	Средний
Поиск
Вставлять
Удалить
Пространственная сложность
Космос

В информатике список пропуска (или Skiplist ) — это вероятностная структура данных , позволяющая $O(\log n)$ средняя сложность для поиска, а также $O(\log n)$ средняя сложность вставки в упорядоченную последовательность $n$ элементы. Таким образом, он может получить лучшие возможности отсортированного массива (для поиска), сохраняя при этом структуру, подобную связанному списку , которая позволяет вставку, что невозможно для статического массива. Быстрый поиск становится возможным благодаря поддержанию связанной иерархии подпоследовательностей, при которой каждая последующая подпоследовательность пропускает меньше элементов, чем предыдущая (см. рисунок ниже справа). Поиск начинается с самой разреженной подпоследовательности, пока не будут найдены два последовательных элемента: один меньшего размера, а другой больше или равен искомому элементу. Через связанную иерархию эти два элемента связаны с элементами следующей самой разреженной подпоследовательности, где поиск продолжается до тех пор, пока, наконец, не будет выполнен поиск в полной последовательности. Пропущенные элементы могут быть выбраны вероятностным путем. ^[2] или детерминированно, ^[3] причем первое встречается чаще.

Описание

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

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

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

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

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

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

Альтернативно, структуру уровней можно сделать квазислучайной следующим образом:

make all nodes level 1j ← 1while the number of nodes at level j > 1 do    for each i'th node at level j do        if i is odd and i is not the last node at level j            randomly choose whether to promote it to level j+1        else if i is even and node i-1 was not promoted            promote it to level j+1        end if    repeat    j ← j + 1repeat

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

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

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

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

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

Как описано выше, список пропуска способен быстро $O(\log n)$ вставка и удаление значений из отсортированной последовательности, но только медленная $O(n)$ поиск значений в заданной позиции в последовательности (т.е. возврат 500-го значения); однако с незначительной модификацией скорость индексированного поиска с произвольным доступом может быть улучшена до $O(\log n)$ .

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

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

   1                               10 o---> o---------------------------------------------------------> o    Top level   1           3              2                    5 o---> o---------------> o---------> o---------------------------> o    Level 3   1        2        1        2              3              2 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2   1     1     1     1     1     1     1     1     1     1     1  o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom levelHead  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

Обратите внимание, что ширина ссылки более высокого уровня представляет собой сумму компонентных ссылок ниже нее (т. е. ссылка шириной 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).

function lookupByPositionIndex(i)    node ← head    i ← i + 1                           # don't count the head as a step    for level from top to bottom do        while i ≥ node.width[level] do # if next step is not too far            i ← i - node.width[level]  # subtract the current width            node ← node.next[level]    # traverse forward at the current level        repeat    repeat    return node.valueend function

Этот метод реализации индексирования подробно описан в «Поваренной книге списка пропуска» Уильяма Пью. ^[7]

История

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

Цитирую автора:

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

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

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

Apache Portable Runtime реализует списки пропуска. ^[9]
MemSQL использует списки пропуска без блокировок в качестве основной структуры индексации для своей технологии баз данных.
MuQSS для ядра Linux — это планировщик процессора, построенный на списках пропуска. ^[10]^[11]
Сервер Cyrus IMAP предлагает реализацию внутренней базы данных «пропускного списка». ^[12]
Lucene использует списки пропуска для поиска в списках сообщений с дельта-кодировкой в логарифмическом времени. ^{[ нужна ссылка ]}
Класс шаблонов словаря ключей/значений QMap (до Qt 4) Qt реализован с помощью списков пропуска. ^[13]
Redis , постоянное хранилище ключей/значений с открытым исходным кодом ANSI-C для систем Posix, использует списки пропуска в своей реализации упорядоченных наборов. ^[14]
Discord использует списки пропуска для хранения и обновления списка участников на сервере . ^[15]
RocksDB использует списки пропуска для реализации Memtable по умолчанию. ^[16]

Списки пропуска также используются в распределенных приложениях (где узлы представляют собой физические компьютеры, а указатели представляют собой сетевые соединения) и для реализации высокомасштабируемых параллельных очередей приоритетов с меньшим количеством конфликтов за блокировки. ^[17] или даже без блокировки , ^[18]^[19]^[20] а также параллельные словари без блокировки . ^[21] Существует также несколько патентов США на использование списков пропуска для реализации (безблокировочных) приоритетных очередей и параллельных словарей. ^[22]

См. также

Ссылки

^ Jump up to: ^а ^б Пападакис, Томас (1993). Списки пропуска и вероятностный анализ алгоритмов (PDF) (доктор философии). Университет Ватерлоо.
^ Пью, В. (1990). «Списки пропуска: вероятностная альтернатива сбалансированным деревьям» (PDF) . Коммуникации АКМ . 33 (6): 668–676. дои : 10.1145/78973.78977 . S2CID 207691558 .
^ Манро, Дж. Ян ; Пападакис, Томас; Седжвик, Роберт (1992). «Детерминированные списки пропуска» (PDF) . Материалы третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '92) . Орландо, Флорида, США: Общество промышленной и прикладной математики, Филадельфия, Пенсильвания, США. стр. 367–375. S2CID 7477119 .
^ Бетея, Даррелл; Райтер, Майкл К. (21–23 сентября 2009 г.). Структуры данных с непредсказуемым временем (PDF) . ESORICS 2009, 14-й Европейский симпозиум по исследованиям в области компьютерной безопасности. Сен-Мало, Франция. стр. 456–471, §4 «Списки пропуска». дои : 10.1007/978-3-642-04444-1_28 . ISBN 978-3-642-04443-4 .
^ Сен, Сандип (1991). «Некоторые наблюдения по поводу списков пропуска». Письма об обработке информации . 39 (4): 173–176. дои : 10.1016/0020-0190(91)90175-H .
^ Шах, Гаури (2003). Распределенные структуры данных для одноранговых систем (PDF) (кандидатская диссертация). Йельский университет.
^ Уильям Пью. «Кулинарная книга со списком пропуска» .1990. Раздел 3.4 Операции с линейным списком .
^ Пью, Уильям (апрель 1989 г.). Параллельное ведение списков пропуска (PS, PDF) (Технический отчет). Кафедра компьютерных наук, Университет Мэриленда. CS-TR-2222.
^ Документация Apache Portable Runtime, апрель 1.6.
^ LWN статья
^ «LKML: Con Kolivas: [ОБЪЯВЛЕНИЕ] Планировщик списков пропуска нескольких очередей, версия 0.120» . lkml.org . Проверено 11 мая 2017 г.
^ IMAP-сервер Сайруса. исходный файл списка пропуска
^ QMap
^ «Реализация упорядоченного набора Redis» . Гитхаб .
^ Новак, Мэтт. «Использование Rust для масштабирования Elixir для 11 миллионов одновременных пользователей» . Дискорд-блог . Проверено 23 июля 2023 г.
^ «МемТаблица» . Гитхаб . Проверено 12 декабря 2023 г.
^ Шавит, Н.; Лотан, И. (2000). «Очереди с одновременным приоритетом на основе скипслистов» (PDF) . Материалы 14-го Международного симпозиума по параллельной и распределенной обработке. ИППДС 2000 . п. 263. CiteSeerX 10.1.1.116.3489 . дои : 10.1109/IPDPS.2000.845994 . ISBN 978-0-7695-0574-9 . S2CID 8664407 .
^ Санделл, Х.; Цигас, П. (2003). «Быстрые и одновременные очереди приоритетов без блокировки для многопоточных систем». Труды Международного симпозиума по параллельной и распределенной обработке . п. 11. CiteSeerX 10.1.1.113.4552 . дои : 10.1109/IPDPS.2003.1213189 . ISBN 978-0-7695-1926-5 . S2CID 20995116 .
^ Фомичев Михаил; Руперт, Эрик (2004). Связанные списки и списки пропуска без блокировки (PDF) . Учеб. Ежегодный симпозиум ACM. по принципам распределенных вычислений (PODC). стр. 50–59. дои : 10.1145/1011767.1011776 . ISBN 1581138024 .
^ Баджпай, Р.; Дхара, КК; Кришнасвами, В. (2008). «QPID: очередь с распределенным приоритетом и местоположением элементов». 2008 Международный симпозиум IEEE по параллельной и распределенной обработке приложений . п. 215. дои : 10.1109/ISPA.2008.90 . ISBN 978-0-7695-3471-8 . S2CID 15677922 .
^ Санделл, Гонконг; Цигас, П. (2004). «Масштабируемые одновременные словари без блокировки» (PDF) . Материалы симпозиума ACM по прикладным вычислениям 2004 г. - SAC '04 . п. 1438. дои : 10.1145/967900.968188 . ISBN 978-1581138122 . S2CID 10393486 .
^ Патент США 7937378.

Внешние ссылки

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

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

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

[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-H .

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

[7] Уильям Пью. «Кулинарная книга со списком пропуска» .1990. Раздел 3.4 Операции с линейным списком .

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

[9] Документация Apache Portable Runtime, апрель 1.6.

[10] LWN статья

[11] «LKML: Con Kolivas: [ОБЪЯВЛЕНИЕ] Планировщик списков пропуска нескольких очередей, версия 0.120» . lkml.org . Проверено 11 мая 2017 г.

[12] IMAP-сервер Сайруса. исходный файл списка пропуска

[13] QMap

[14] «Реализация упорядоченного набора Redis» . Гитхаб .

[15] Новак, Мэтт. «Использование Rust для масштабирования Elixir для 11 миллионов одновременных пользователей» . Дискорд-блог . Проверено 23 июля 2023 г.

[16] «МемТаблица» . Гитхаб . Проверено 12 декабря 2023 г.

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

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

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

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

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

[22] Патент США 7937378.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

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