Довідка та теорія
Список з пропусками — це впорядкований зв'язаний список зі складеними експрес-смугами. Вищі смуги містять менше вузлів, тож пошук може стрибнути далеко вперед, потім спуститися для точності.
Побудова рівнів підкиданням монети
Кожен вузол починає з рівня 1. Ми підкидаємо чесну монету: з
імовірністю ½ вузол підвищується на рівень
вище, повторюючи до решки. Тож ~половина вузлів досягає рівня 2,
~чверть — рівня 3, і так далі.
Патерн пошуку
- Почати з голови верхнього рівня.
- Рухатися вперед, доки наступний ключ менший за ціль.
- Коли наступний ключ перескочив би, спуститися на рівень.
- Повторювати до рівня 1, потім перевірити останній вузол.
Чому O(log n)
За приблизно log₂(n) рівнів і сталу очікувану
кількість кроків уперед на рівень очікувана вартість пошуку —
O(log n), що відповідає збалансованому дереву, але
досягається випадковістю замість обертань.
Де воно застосовується
Списки з пропусками живлять впорядковані множини Redis,
memtable LevelDB та конкурентні впорядковані мапи, як-от
ConcurrentSkipListMap у Java.
Як працює ця симуляція
Це справжній список з пропусками. Коли ви вставляєте ключ, він
розміщується в упорядкованому порядку на рівні 1, потім із початковим
зерном багаторазово підкидається монета: кожен орел підвищує
новий вузол на рівень вище, тож його башта вказівників уперед росте з
імовірністю ½ на рівень. Коли ви натискаєте
Шукати, анімований курсор починає з голови верхньої
експрес-смуги й рухається вперед, доки наступний ключ менший за ціль,
спускаючись на рівень щоразу, коли наступний крок перескочив би ціль —
класичний прохід «стрибнути-спуститися», що відвідує очікувано
O(log n) вузлів.
Як читати полотно
Кожен горизонтальний ряд — це один рівень; нижній ряд — повний
упорядкований список, а кожен ряд вище — експрес-смуга з підвищеною
підмножиною, з'єднана вказівниками вперед. Під час пошуку відвідані
вузли підсвічуються, щоб ви могли простежити маршрут. Панель
статистики показує поточну кількість рівнів, кількість
вузлів, теоретичні очікувані стрибки (близько
log₂(n)) та фактичні стрибки, які реально зробив
останній пошук, дозволяючи порівняти теорію з одним прогоном.
Поширені запитання
Що таке список з пропусками?
Список з пропусками — це рандомізована структура даних, побудована з упорядкованого зв'язаного списку з додатковими шарами «експрес-смуг», складеними зверху. Вищі шари містять менше вузлів, тож пошук може швидко стрибати вперед на верхніх смугах і спускатися вниз, щоб знайти ключ за очікуваний час O(log n).
Як обираються рівні?
Коли вузол вставляється, він починає з рівня 1, потім підкидається монета: з імовірністю одна друга його підвищують на наступний рівень угору, і підкидання тривають, доки не випаде решка. Тож приблизно половина вузлів досягає рівня 2, чверть — рівня 3, і так далі.
Як працює пошук?
Пошук починається з голови найвищого рівня й рухається вперед, доки наступний ключ менший за ціль. Коли наступний ключ перескочив би ціль, він спускається на один рівень нижче й продовжує. Цей патерн «стрибнути-спуститися» повторюється до рівня 1, де він або потрапляє на ключ, або проходить повз нього.
Чому пошук у середньому O(log n)?
Оскільки кожен рівень містить приблизно половину вузлів нижчого, рівнів виходить близько log2(n), а очікувана кількість кроків уперед на кожному рівні стала. Разом це дає очікувану вартість пошуку O(log n) стрибків.
Чим список з пропусками відрізняється від збалансованого дерева?
Обидва досягають пошуку O(log n), але список з пропусками доходить до балансу через випадковість, а не через обертання чи перефарбування. Його простіше реалізувати й він дуже зручний для конкурентного доступу, тому він з'являється в системах на кшталт впорядкованих множин Redis і memtable LevelDB.
Що тут означає «очікувані проти фактичних стрибків»?
Очікувана кількість стрибків — це теоретична оцінка, приблизно log2(n), для пошуку в поточному списку. Фактичні стрибки — це реальні рухи вперед і вниз, які анімований курсор зробив під час останнього пошуку, тож ви можете порівняти теорію з одним конкретним прогоном.
Що станеться, якщо я шукатиму відсутній ключ?
Курсор слідує точно тим самим шляхом «стрибнути-спуститися» й зупиняється на рівні 1 саме перед тим місцем, де мав би бути ключ. Симуляція повідомляє про промах, а відвідані вузли все одно підсвічуються, щоб ви бачили пройдений маршрут.
Випадковість фіксована чи різна щоразу?
Кожна вставка використовує генератор псевдовипадкових чисел із початковим зерном для своїх підкидань монети, тож патерн рівнів відтворюваний у межах сесії. Очищення списку перезадає зерно, і ви можете відтворити ту саму форму, вставляючи ті самі ключі в тому самому порядку.
Де списки з пропусками застосовують на практиці?
Вони лежать в основі типу впорядкованих множин у Redis, memtable в пам'яті LevelDB та подібних сховищ ключ-значення, а також кількох конкурентних реалізацій упорядкованих мап, зокрема ConcurrentSkipListMap у Java.
Що таке експрес-смуги на малюнку?
Кожен горизонтальний ряд — це рівень. Нижній ряд — повний упорядкований список; кожен ряд вище — це експрес-смуга, що містить підмножину вузлів, підвищених до цієї висоти, з вказівниками вперед, які дозволяють пошуку перестрибувати багато вузлів нижнього рівня одразу.