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

Вероятностная структура данных

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 1 10 о---> о-------------------------------------------- -------------> o Верхний уровень 1 3 2 5 о---> о---------------> о---------> о---------------- -----------> o Уровень 3 1 2 1 2 3 2 о---> о---------> о---> о---------> о---------------> о ---------> o Уровень 2 1 1 1 1 1 1 1 1 1 1 1 о---> о---> о---> о---> о---> о---> о---> о---> о---> о---> o---> o Нижний уровеньРуководитель 1-й 2-й 3-й 4-й 5-й 6-й 7-й 8-й 9-й 10-й НОЛЬ Узел Узел Узел Узел Узел Узел Узел Узел Узел

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

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

Этот метод реализации индексирования подробно описан в «Кулинарной книге списка пропуска» Уильяма Пью ^[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]

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

• Фильтр Блума
• Пропустить график

Рекомендации

1. Пападакис, Томас (1993). Списки пропуска и вероятностный анализ алгоритмов (PDF) (доктор философии). Университет Ватерлоо.
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. 

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

• Запись «Пропустить список» в Словаре алгоритмов и структур данных.
• Лекция по пропускам списков (MIT OpenCourseWare: Введение в алгоритмы)
• Структуры открытых данных. Глава 4. Пропускные списки, Пэт Морин
• Графы пропускаемых деревьев, распределенная версия пропускаемых деревьев.
• Подробнее о графах деревьев пропуска — распределенной версии деревьев пропуска.