algorithms · advanced · 6d
Список с пропусками
Реализуй вероятностную упорядоченную структуру данных, которая обеспечивает O(log n) поиск, вставку и удаление без балансировочной бухгалтерии деревьев — только слоистые «экспресс-полосы» через отсортированный связный список.
Результат
Список с пропусками с инжектируемым детерминированным подбрасыванием монеты для генерации уровней, корректной восходящей итерацией и тест-сьютом, который доказывает многоуровневое продвижение, точный порядок и выигрыш O(log n) поиска над линейным сканом на высоком списке.
Этапы
0/6 · 0%- 01Узлы, часовые и структура уровней
До любой логики поиска или вставки выстрой правильную физическую форму. Список с пропусками — это башня отсортированных связных списков: уровень 0 — полный список, в котором участвует каждый узел; уровень 1 содержит примерно половину узлов; уровень k — примерно 1/2^k. Каждый узел несёт массив прямых указателей, по одному на каждый уровень, которого узел достигает. Два узла-часовых — head и tail — обрамляют каждый уровень, так что проверки границ сводятся к сравнению указателей, а не к защите от null. Ключ head равен −∞, tail — +∞; каждый не-часовой узел помещается между ними. Ограничение максимального уровня (обычно 16 или 32) ограничивает и память, и цикл генерации уровня в худшем случае — без него патологическая последовательность монет могла бы выделять память бесконечно. Набросай расположение узла, часовых head/tail на всех уровнях и инвариант: уровень 0 всегда является полной отсортированной цепочкой, а более высокие уровни — разреженные экспресс-полосы той же сортировки. Эта структурная ясность предотвращает ошибки позже — смещённый прямой указатель на уровне 2 молча искажает поиски, но практически невозможно отладить, глядя только на вывод.
Критерии готовности- Ты можешь описать расположение узла (key + forward[] длиной = уровень узла) и нарисовать список с пропусками из пяти ключей, показывая все четыре структурных уровня, часовые head и tail и полноту уровня 0.
- Конструктор класса SkipList принимает инжектируемый параметр coinFlip (не Math.random) и ограничение maxLevel; инвариант часовых обеспечивается при построении и никогда не перепроверяется во время выполнения.
Самопроверка
Пройди массив прямых указателей на каждом уровне для списка из трёх узлов; senior-ревьюер проверяет, что head[k] → первый узел на уровне k → часовой tail[k] — полная цепочка и что цепочка уровня 0 содержит каждый узел без пропусков.
- 02Вероятностная генерация уровня и контракт подбрасывания монеты
Ожидаемая стоимость O(log n) списка с пропусками целиком покоится на случайности: если сместить монету или сделать уровни детерминированными, структура деградирует до отсортированного связного списка. Стандартный рецепт — продолжай подбрасывать несмещённую монету; остановись при первом решке или достижении maxLevel; количество орлов — уровень узла — производит геометрическое распределение высот, гарантируя, что ожидаемое число узлов на уровне k равно n/2^k. Ключевое инженерное понимание состоит в том, что подбрасывание монеты должно инжектироваться, а не читаться из Math.random(), по двум причинам: (1) тесты должны быть детерминированными и воспроизводимыми; (2) любой код, встраивающий глобальный ГСЧ, нетестируем на уровне юнит-теста. Твой параметр coinFlip() → boolean возвращает true (продвижение) или false (остановка). Контролируемая последовательность флипов вида [true, true, false, …] детерминированно производит трёхуровневый узел, делая утверждения о нескольких уровнях возможными без хрупкости. Ограничение maxLevel важно для безопасности: вызывающий, который может смещать монету так, чтобы всегда возвращать true, вызвал бы бесконечный цикл; ограничение 32 ограничивает худший случай O(32) = O(1) генерации уровня независимо от ввода.
Критерии готовности- randomLevel() использует только инжектируемый coinFlip, никогда глобальный ГСЧ, и соблюдает maxLevel — доказано передачей coinFlip, который всегда возвращает true, и утверждением, что результирующий уровень равен ровно maxLevel.
- Тест с контролируемой последовательностью флипов [true, true, false] производит узел на уровне 3, а флип [false] — узел на уровне 1, подтверждая геометрическое распределение в малом масштабе.
Самопроверка
Покажи реализацию randomLevel() без ссылок на Math.random, Date или что-либо глобальное; senior-ревьюер проверяет условие остановки (false от coinFlip ИЛИ level === maxLevel) и что уровень считается от 1, а не от 0.
- 03Вставка и поиск: паттерн вектора обновления
Поиск и вставка разделяют один и тот же скелет обхода — это ключевой алгоритмический ход в списке с пропусками. Начиная с наивысшего уровня head, ты продвигаешься вперёд, пока ключ следующего узла строго меньше цели; когда продвинуться больше нельзя, ты спускаешься на один уровень и повторяешь. Это двумерное движение — вправо, потом вниз — в ожидании посещает O(log n) узлов, потому что каждый уровень действует как экспресс-полоса, пропускающая примерно половину узлов ниже. Вектор обновления (массив последнего посещённого узла на каждом уровне во время поиска) — это то, что превращает чистый поиск во вставку: после обхода каждый update[k] указывает на предшественника на уровне k, а встраивание нового узла на его сгенерированной высоте — это O(высота) перестановок указателей, каждая за константное время. Без вектора обновления каждая вставка требовала бы второго прохода; с ним вставка — это поиск плюс локальное встраивание. Тот же паттерн обхода используется при удалении: найти предшественников, проверить существование цели на уровне 0, затем отсоединить её от каждого уровня, где она появляется.
Критерии готовности- insert(k) корректно встраивает новый узел на каждом уровне до его сгенерированной высоты с помощью паттерна вектора обновления, а has(k) возвращает true для вставленного ключа и false для никогда не вставленного, проверенного для как минимум пяти различных ключей.
- Обход посещает только прямые указатели (без обратного сканирования), и путь поиска строго нисходящий по уровням: он никогда не возвращается на уровень после спуска.
Самопроверка
Проследи обход вектора обновления для insert(7) в список [1, 3, 5, 9] с двухуровневой структурой и покажи, какие указатели изменяются; senior-ревьюер проверяет, что ровно два уровня обновляются для двухуровневого узла и что цепочка уровня 0 остаётся полной после встраивания.
- 04Удаление: сканирование предшественников и многоуровневое отсоединение
Удаление — это вставка наоборот: выполни тот же обход вектора обновления, затем проверь, является ли узел update[0].forward[0] целью — если нет (ключ никогда не вставлялся), немедленно верни false без структурных изменений. Если да, отсоедини его от каждого уровня, где он появляется: для каждого уровня k от 0 до высоты узла установи update[k].forward[k] = node.forward[k]. Заманчивая ошибка — безусловно отсоединять от всех уровней; ты должен остановиться на фактической высоте узла, потому что выше него у узла нет прямого указателя и его предшественники на него не ссылаются. Тонкость дублирующихся ключей: если твоя вставка молча игнорирует дубликат (что является правильным дефолтом для похожего на множество списка с пропусками), удаление должно обрабатывать только случай, когда ключ существует один раз или не существует. Если ты допускаешь дубликаты, предшественник вектора обновления на уровне 0 может указывать на первый дубликат и ты удаляешь только один экземпляр — допустимый и распространённый выбор реализации, но он должен быть задокументирован. После удаления, если эффективная высота списка уменьшается (все узлы уровня k исчезли), уменьши currentLevel, чтобы избежать избыточных накладных расходов на обход пустых высоких уровней.
Критерии готовности- delete(k) возвращает true и удаляет узел со всех уровней, которые он занимал, когда k существует; возвращает false и не вносит структурных изменений, когда k никогда не был вставлен; оба случая доказаны вызовом has() и toArray() после каждого удаления.
- После удаления узла с наивысшим уровнем currentLevel уменьшается, отражая новый максимальный уровень — обход не тратит итерации на пустые высокие уровни.
Самопроверка
Удали узел на уровне 3 в четырёхуровневом списке и покажи точные обновления указателей на каждом уровне; senior-ревьюер проверяет, что обновления на уровнях выше высоты узла не затрагиваются и что currentLevel уменьшается, если удалённый узел был единственным на верхнем уровне.
- 05Упорядоченная итерация: toArray() и полоса уровня 0
Простейшее и наиболее полезное свойство списка с пропусками состоит в том, что итерация по цепочке уровня 0 посещает каждый ключ в возрастающем отсортированном порядке за O(n) времени — сортировка не требуется, потому что вставка поддерживает инвариант. toArray() — это поэтому линейный проход от head.forward[0] до tail с накоплением ключей. Загвоздка в дубликатах: если твоя вставка игнорирует уже присутствующий ключ, toArray() никогда не возвращает дубликаты; если вставка их допускает, массив может содержать повторяющиеся записи. Любой контракт допустим, но он должен быть последовательным и протестированным. Senior-вопрос состоит в том, что отсортированный инвариант не может быть нарушен никакой последовательностью вставок и удалений — проверь это с помощью состязательной последовательности: вставляй не по порядку, удаляй некоторые ключи, вставляй снова и утверждай, что toArray() всё ещё строго возрастающий. Это также подходящий момент для бенчмарка: при coinFlip, активно продвигающем (много уровней), как количество посещённых узлов has() соотносится с линейным сканом по массиву для n = 1000 ключей? Даже грубый счётчик — инкремент счётчика посещений в цикле обхода — экспериментально демонстрирует свойство O(log n).
Критерии готовности- toArray() возвращает ключи в строго возрастающем порядке для любой последовательности вставок, включая нарушенный порядок и смешанный с удалениями — проверено состязательным тестом, который вставляет 10 ключей в обратном порядке, удаляет 3, затем проверяет, что массив отсортирован.
- Счётчик посещений узлов в обходе показывает, что has() посещает O(log n) узлов на высоком списке (продвигающий coinFlip) против O(n) для линейного сканирования по тем же данным — соотношение видно при n ≥ 100.
Самопроверка
Вставь [5, 1, 9, 3, 7] в этом порядке и покажи полную цепочку уровня 0 после каждой вставки; senior-ревьюер проверяет, что цепочка отсортирована после каждого шага, а не только в конце, доказывая, что вставка поддерживает инвариант постепенно.
- 06Доказательство сложности, настройка параметров и состязательные входы
Утверждение O(log n) вероятностное, а не для худшего случая — точно выясни, что именно это означает и при каких условиях оно нарушается. Стандартное доказательство показывает, что ожидаемое число сравнений узлов при поиске не превышает (log_{1/p} n)/p + 1/p для вероятности продвижения p (обычно p = 0.5, давая O(log_2 n)). Практический вывод: p настраиваемо — p = 0.25 даёт меньшую ожидаемую высоту (log_4 n ≈ 0.5 log_2 n), но более широкие башни на уровень, обменивая стоимость поиска на память; p = 0.5 — классический баланс. Состязательный ввод — детерминированный coinFlip, всегда возвращающий один и тот же уровень — все узлы на уровне 1, деградация до связного списка O(n) на операцию. Более реалистичный риск — недостаточная энтропия в производственном ГСЧ, засеянном часами с низким разрешением, что может производить коррелированные уровни. Senior-результат — написанный анализ: при n = 10^6 ключей, p = 0.5 и maxLevel = 20, каково ожидаемое число узлов на уровне 20? (около n/2^20 ≈ 1). Какова ожидаемая стоимость поиска? (около 1.33 × log_2(10^6) ≈ 27 сравнений). Какой станет стоимость поиска при случайном использовании p = 1.0? (O(n), все узлы на maxLevel, список деградирует). Эти числа делают выбор параметров конкретным, а не расплывчатым.
Критерии готовности- Ты можешь сформулировать формулу ожидаемой стоимости поиска для заданных n и p, вычислить её для n = 10^6 и p = 0.5 и назвать условие, при котором список с пропусками деградирует до O(n) на операцию.
- Бенчмарк с n = 1000 ключами и продвигающим coinFlip (p = 0.5) показывает, что has() посещает в среднем менее 2 × log2(1000) ≈ 20 узлов, тогда как линейное сканирование всегда посещает n/2 = 500 — счётчик инструментирован в тесте, а не просто утверждается.
Самопроверка
При coinFlip, всегда возвращающем false (каждый узел на уровне 1), какова стоимость поиска для наибольшего ключа в списке из 1000 элементов и как senior-инженер документирует этот вырожденный случай в контракте API, чтобы предупредить вызывающих?
Стартер
- README.md
- src/skiplist.ts
- test/skiplist.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| Структура уровней и вероятностный баланс | Узлы имеют прямые указатели, но назначение уровней использует Math.random() напрямую, делая тесты недетерминированными; maxLevel не соблюдается, рискуя неограниченной генерацией уровней. | coinFlip инжектируется и maxLevel соблюдается; часовые обрамляют каждый уровень; цикл генерации уровней производит геометрическое распределение высот, проверяемое контролируемой последовательностью флипов. | Ты можешь вывести ожидаемое число узлов на каждом уровне как n × p^k, сформулировать формулу стоимости поиска для произвольного p, вычислить её для n = 10^6 и p = 0.5 и назвать вырожденный случай (coinFlip всегда true или всегда false) и его стоимость. |
| Корректность поиска, вставки и удаления | Вставка добавляет только на уровень 0; has() выполняет линейное сканирование; удаление использует второй полный скан, а не путь вектора обновления; отсортированный инвариант поддерживается случайно, а не намеренно. | Все три операции используют обход вектора обновления; has() спускается с верхнего уровня; delete возвращает false для отсутствующих ключей без изменения структуры; дублирующиеся вставки не искажают размер или порядок. | Состязательная последовательность (вставки в обратном порядке, перемежающиеся удаления, повторные вставки) никогда не производит некорректный toArray(); currentLevel уменьшается при удалении, когда верхний уровень опустевает; счётчик посещений доказывает обход O(log n) на высоком списке. |
| Упорядоченность и обход O(log n) | toArray() сортирует вывод после сбора узлов, а не полагается на структурный инвариант сортировки; стоимость сортировки O(n log n) скрывает, что инвариант может не выполняться. | toArray() — простой проход уровня 0, O(n), без сортировки — и вывод возрастающий для любого порядка вставок; инвариант полноты уровня 0 поддерживается каждой вставкой и удалением. | Бенчмаркированный has() со счётчиком посещений показывает сублинейный обход (< 2 × log2 n узлов) против O(n) для линейного сканирования по тем же данным при n ≥ 1000; анализ настройки coinFlip количественно описывает компромисс памяти против скорости p = 0.25 против p = 0.5 с числами. |
Эталонный разбор (спойлер)
Почему список с пропусками, а не сбалансированное BST: список с пропусками достигает ожидаемой стоимости O(log n) без балансировочной бухгалтерии и без метаданных цвета узла или высоты. Каждая вставка и удаление — единственный нисходящий проход (обход вектора обновления) плюс O(высота) перестановок указателей — никакой перебалансировки, никаких ротаций, никаких указателей на родителя. Компромисс в том, что граница O(log n) ожидаемая, а не для худшего случая: патологическая последовательность coinFlip может деградировать любую отдельную операцию до O(n), тогда как красно-чёрное дерево детерминированно гарантирует O(log n). На практике, при качественном ГСЧ, константные факторы списка с пропусками конкурентоспособны, а его поведение кэша при последовательных сканах лучше, чем у дерева с интенсивным использованием указателей.
Внутренности Redis ZSET: Redis использует список с пропусками для своего отсортированного множества (ZSET), потому что он поддерживает ранговые запросы O(log n) и сканирование диапазонов с более простым кодом, чем сбалансированное дерево. Каждый узел ZSET хранится на нескольких уровнях, а команда ZRANK проходит список с пропусками, подсчитывая ширины пролётов (дополнение указателей) для вычисления ранга без явного поля ранга. Линейное сканирование уровня 0 списка с пропусками также идеально для ZRANGE (запросы диапазона по оценке), который Redis выполняет за O(log n + m), где m — число возвращаемых результатов.
Паттерн вектора обновления в одном предложении: перед изменением любого прямого указателя собери последний посещённый узел на каждом уровне во время поиска — это массив update[] — чтобы каждый предшественник обновлялся за O(1) без второго прохода. Каждая вставка и удаление в списке с пропусками — это поиск, запоминающий своих предшественников, затем локальная хирургия указателей с использованием этих предшественников. Без вектора обновления вставка потребовала бы полного второго нисходящего прохода, удваивая стоимость обхода.
Дисциплина часовых устраняет проверки null: использование узлов-часовых −∞ и +∞ на head и tail означает, что каждый поиск чисто завершается на реальном узле (никогда не нулевом указателе) и каждый уровень является полной цепочкой от head до tail. Альтернатива — проверка `node.forward[k] !== null` на каждом шаге — рассыпает null-защиты по всему коду обхода и является распространённым источником ошибок по одному в реализациях списков с пропусками. Часовые — самый простой способ сделать инвариант структурным, а не процедурным.
Почему инжектировать coinFlip вместо использования Math.random(): структуру данных, чьё поведение зависит от глобального ГСЧ, нельзя детерминированно протестировать на уровне юнит-теста. Если два прогона теста производят разные распределения уровней, тест, который проходит сегодня, может завтра провалиться при другом случайном зерне — не потому что код неправильный, а потому что случайный обход оказался неудачным. Инжектирование функции флипа делает структуру чистой функцией своих входов и последовательности флипов, что является стандартной техникой тестирования любого рандомизированного алгоритма. Тот же принцип применяется к инжектированию часов в зависящем от времени коде (токен-бакеты, TTL-кэши, планирование) и инжектированию ID в контентно-адресованном хранилище.
Сделай по-сеньорски
- Реализуй операцию rank() — для ключа k верни количество ключей в списке, меньших k — за O(log n), дополнив каждый прямой указатель пролётом (числом узлов уровня 0, которые он перепрыгивает); обновляй пролёты при каждой вставке и удалении.
- Построй персистентный список с пропусками с использованием копирования пути: insert и delete возвращают новый заголовок без изменения старой структуры, так что каждая версия достижима по указателю head — полезно для снимков чтения и конкуренции в стиле MVCC.
- Замени граф узлов в памяти на страничную раскладку, где прямые указатели каждого узла хранятся в плоском типизированном массиве (например, Int32Array), для улучшения локальности кэша и измерь разницу в пропускной способности для n = 100 000 ключей.
- Реализуй вариант с пальцевым поиском: кэшируй позицию последнего поиска как «палец» и начинай последующие поиски с пальца, а не с head, снижая стоимость до O(log d), где d — расстояние по ключу от пальца — полезно для последовательных или почти последовательных паттернов доступа.
- Проанализируй и продемонстрируй, когда список с пропусками превосходит B-дерево для упорядоченных карт в памяти: аргументируй с помощью паттернов доступа к строкам кэша, стоимости разыменования указателей против коэффициента заполнения страниц и пропускной способности сканирования диапазона — поддержи аргумент бенчмарком при n = 10^5.