Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пропустить список
ТипСписок
Изобрел1989 г.
ИзобретенныйВ. Пью
Сложность времени в большой нотации O
АлгоритмСреднийХудший случай
Космос[1]
Поиск[1]
Вставлять
Удалить
Часть серии по
Вероятностные структуры данных
Случайные деревья
Связанный

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

Описание [ править ]

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

Список пропусков построен по слоям. Нижний слой - это обычный упорядоченный связанный список . Каждый более высокий уровень действует как «экспресс-дорожка» для списков ниже, где элемент в слое появляется в слое с некоторой фиксированной вероятностью (два обычно используемых значения для are или ). В среднем каждый элемент появляется в списках, а самый высокий элемент (обычно это специальный элемент заголовка в начале списка пропуска) - во всех списках. Список содержит пропуска (т.е. логарифма базы в ) списки.

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

Детали реализации [ править ]

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

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

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

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

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

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

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

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

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

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

Индексируемый скиплист [ править ]

Как описано выше, список пропуска позволяет быстро вставлять и удалять значения из отсортированной последовательности, но он имеет только медленный поиск значений в заданной позиции в последовательности (т. Е. Возвращает 500-е значение); однако с небольшими изменениями скорость индексированного поиска с произвольным доступом может быть улучшена до .

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

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

 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-я 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) узел ← голова я ← +- # не считать голову в качестве шага  на уровень от верхних к нижним делам в  то время как я ≥ node.width [Уровень] делать  # , если следующий шаг не слишком далеко я ← я - node.width [Уровень] # вычесть текущую ширину node ← node.next [level] # перейти вперед на текущем уровне повторить  повторить  return node.value end function

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

История [ править ]

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

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

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

-  Уильям Пью, Параллельное ведение списков пропусков (1989).

Использование [ править ]

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

  • Apache Portable Runtime реализует списки пропуска. [9]
  • MemSQL использует списки пропуска без блокировки в качестве основной структуры индексации для своей технологии баз данных.
  • Сервер Cyrus IMAP предлагает внутреннюю реализацию БД "skiplist" [10]
  • Lucene использует списки пропуска для поиска списков сообщений с дельта-кодированием в логарифмическом времени. [ необходима цитата ]
  • Класс шаблона словаря ключей / значений "QMap" (до Qt 4) Qt реализован с помощью списков пропуска. [11]
  • Redis , постоянное хранилище ключей / значений с открытым исходным кодом ANSI-C для систем Posix, использует списки пропуска в своей реализации упорядоченных наборов. [12]
  • «nessDB», очень быстрое встроенное ядро ​​хранилища базы данных «ключ-значение» (использующее деревья лог-структурированного слияния (LSM)), использует списки пропусков для своей таблицы памяти. [13]
  • "skipdb" - это реализация с открытым исходным кодом упорядоченной базы данных "ключ-значение" ACID, реализованная со списком пропуска вместо b-дерева. [14]
  • ConcurrentSkipListSet и ConcurrentSkipListMap в API Java 1.6. [15] Используется Apache HBase .
  • Таблицы скорости - это быстрое хранилище данных типа "ключ-значение" для Tcl, в котором используются списки пропусков для индексов и разделяемой памяти без блокировки.
  • "leveldb" - это библиотека быстрого хранения ключей и значений, написанная в Google, которая обеспечивает упорядоченное сопоставление строковых ключей со строковыми значениями [16]
  • Планировщик MuQSS [17] Кон Коливаса для ядра Linux использует списки пропуска
  • SkiMap использует списки пропусков в качестве базовой структуры данных для построения более сложной трехмерной разреженной сетки для систем картирования роботов. [18]
  • «IOWOW» - это постоянная библиотека для хранения ключей / значений C11, которая использует списки пропусков в качестве основной структуры данных. [19]

Списки пропусков используются для эффективных статистических вычислений] бегущих медиан (также известных как скользящие медианы). [20]

Списки пропуска также используются в распределенных приложениях (где узлы представляют физические компьютеры, а указатели представляют сетевые соединения) и для реализации высокомасштабируемых параллельных очередей приоритетов с меньшим количеством конфликтов блокировок [21] или даже без блокировок , [22] [23] [ 24], а также параллельные словари без блокировки . [25] Есть также несколько патентов США на использование списков пропуска для реализации (без блокировки) очередей приоритетов и параллельных словарей. [26]

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ a b Пападакис, Томас (1993). Пропускные списки и вероятностный анализ алгоритмов (PDF) (доктор философии). Университет Ватерлоо.
  2. ^ Пью, W. (1990). «Списки пропуска: вероятная альтернатива сбалансированным деревьям» (PDF) . Коммуникации ACM . 33 (6): 668–676. DOI : 10.1145 / 78973.78977 .
  3. ^ Манро, Дж. Ян ; Пападакис, Томас; Седжвик, Роберт (1992). «Детерминированные списки пропусков» (PDF) . Труды третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '92) . Орландо, Флорида, США: Общество промышленной и прикладной математики, Филадельфия, Пенсильвания, США. С. 367–375. DOI : 10.1145 / 139404.139478 .
  4. ^ Бетеа, Даррелл; Рейтер, Майкл К. (21–23 сентября 2009 г.). Структуры данных с непредсказуемым временем (PDF) . ESORICS 2009, 14-й Европейский симпозиум по исследованиям в области компьютерной безопасности. Сен-Мало, Франция. С. 456–471, §4 «Пропускные списки». DOI : 10.1007 / 978-3-642-04444-1_28 . ISBN  978-3-642-04443-4.
  5. ^ Сен, Сандип (1991). «Некоторые замечания по пропускным спискам». Письма об обработке информации . 39 (4): 173–176. DOI : 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 APR 1.6
  10. ^ Сервер Cyrus IMAP. исходный файл skiplist
  11. ^ QMap
  12. ^ "Реализация упорядоченного набора Redis" .
  13. ^ nessDB
  14. ^ skipdb
  15. ^ ConcurrentSkipListSet и ConcurrentSkipListMap
  16. ^ leveldb
  17. ^ "LKML: Con Kolivas: [ОБЪЯВЛЕНИЕ] Multiple Queue Skiplist Scheduler версия 0.120" . lkml.org . Проверено 11 мая 2017 .
  18. ^ Грегорио, Даниэле Де; Стефано, Луиджи Ди (2017). «SkiMap: эффективная картографическая структура для навигации роботов». arXiv : 1704.05832 [ cs.CV ].
  19. ^ IOWOW
  20. ^ Раймонд Хеттингер. «Эффективная беговая медиана с использованием индексируемого скиплиста (Python)» . 2009 г.
  21. ^ Шавит, N .; Лотан, И. (2000). «Очереди одновременных приоритетов на основе Skiplist» (PDF) . Труды 14-го Международного симпозиума по параллельной и распределенной обработке. IPDPS 2000 . п. 263. CiteSeerX 10.1.1.116.3489 . DOI : 10.1109 / IPDPS.2000.845994 . ISBN   978-0-7695-0574-9.
  22. ^ Sundell, H .; Цигас П. (2003). «Быстрые очереди одновременных приоритетов без блокировок для многопоточных систем». Материалы Международного симпозиума по параллельной и распределенной обработке . п. 11. CiteSeerX 10.1.1.113.4552 . DOI : 10.1109 / IPDPS.2003.1213189 . ISBN  978-0-7695-1926-5.
  23. ^ Фомичев, Михаил; Рупперт, Эрик (2004). Связанные списки без блокировки и списки пропуска (PDF) . Proc. Ежегодный симпозиум ACM. по принципам распределенных вычислений (PODC). С. 50–59. DOI : 10.1145 / 1011767.1011776 . ISBN  1581138024.
  24. ^ Bajpai, R .; Дхара, KK; Кришнасвами, В. (2008). «QPID: Распределенная очередь приоритета с местоположением элемента». Международный симпозиум IEEE 2008 г. по параллельной и распределенной обработке приложений . п. 215. DOI : 10,1109 / ISPA.2008.90 . ISBN 978-0-7695-3471-8.
  25. ^ Sundell, HK; Цигас П. (2004). «Масштабируемые параллельные словари без блокировки» (PDF) . Материалы симпозиума ACM 2004 г. по прикладным вычислениям - SAC '04 . п. 1438. DOI : 10,1145 / 967900,968188 . ISBN  978-1581138122.
  26. ^ Патент США 7937378 

Внешние ссылки [ править ]

  • Запись «Пропускаемый список» в Словаре алгоритмов и структур данных
  • Списки пропуска: связанный список с самобалансирующимися свойствами, подобными BST, в MSDN в C # 2.0
  • Зачем пропускать списки?
  • Лекция по пропускным спискам (MIT OpenCourseWare: Introduction to Algorithms)
  • Структуры открытых данных - Глава 4 - Специалисты , Пэт Морин
  • Пропустить деревья, альтернативная структура данных для пропуска списков в параллельном подходе
  • Графы деревьев пропуска, распределенная версия деревьев пропуска
  • Подробнее о графах деревьев пропуска, распределенной версии деревьев пропуска