Сжатие пути и почти константа

Коротко

Сжатие пути - вторая и главная оптимизация: раз уж find всё равно поднялся до корня, пусть по дороге назад перевесит КАЖДЫЙ пройденный узел прямо на корень. Следующий find для тех же элементов сделает один шаг. Приём не требует НОВОГО поиска: он переписывает ровно тот путь, по которому подъём уже прошёл, и потому удваивает работу конкретного find, а не умножает её. Зато меняет оценку: вместе с объединением по рангу амортизированная цена операции становится O(α(n)), где α - обратная функция Аккермана. Эта функция растёт настолько медленно, что α(n) <= 4 для любого n, которое вообще можно записать: на практике это константа, хотя формально ею не является - Тарьян доказал, что лучше Ω(α) в этой модели не бывает. Есть и однопроходные варианты (деление пути пополам), с той же оценкой и лучшими константами.

Если ты уверенно пишешь find со сжатием пути, знаешь, что вместе с рангом он даёт амортизированное O(α(n)), и понимаешь, почему это «почти», а не «ровно» константа, листай до «Теперь сам».

Как думаешь, зачем отдавать подъём даром

find(x) поднялся от узла до корня, пройдя, скажем, шесть рёбер, и вернул ответ. Прежде чем читать дальше, подумай: что мы узнали по дороге и что с этим знанием сделали? Мы узнали представителя для ВСЕХ шести узлов пути - и выбросили это знание, оставив их висеть, как висели. Следующий find любого из них снова пойдёт тем же путём. Вопрос: сколько стоит сохранить узнанное?

На что это похоже

Ты спрашиваешь у коллеги, кто отвечает за сервис; он отправляет тебя к своему начальнику, тот - к своему, и на четвёртом человеке находится ответственный. Если после этого каждый в цепочке запомнит: «по этому сервису - сразу к Петрову», следующий вопрос решится одним обращением. Знание уже добыто; записать его стоит столько же, сколько прошёл сам вопрос, а экономия - вся длина цепочки для каждого, кто в ней был.

Механизм: перевесить весь путь на корень

find(x):                       # два прохода: найти корень, потом перевесить
    r = x
    пока parent[r] != r:
        r = parent[r]          # нашли корень
    пока parent[x] != r:
        следующий = parent[x]
        parent[x] = r          # перевесили узел пути прямо на корень
        x = следующий
    вернуть r

Однопроходные варианты делают почти то же, но за один подъём:

деление пути пополам (path halving):
    пока parent[x] != x:
        parent[x] = parent[parent[x]]   # перевесили на деда
        x = parent[x]
    вернуть x                           # по выходе x - корень

Оценка у них та же - O(α(n)) амортизированно, - а констант меньше: один проход, меньше записей в память. Какой брать, решают замером: где-то стоит полное сжатие, где-то деление пути пополам.

Сжатие пути: подъём всё равно состоялся, поэтому на обратном ходу каждый узел пути перевешивают прямо на корень. Дерево становится плоским там, где им пользуются.

Правило

Сжатие пути: после подъёма find перевешивает каждый узел пройденного пути прямо на корень (либо однопроходно - на деда). Вместе с объединением по рангу амортизированная цена операции - O(α(n)), где α - обратная функция Аккермана; α(n) <= 4 для любого практически возможного n. Одно сжатие без ранга и один ранг без сжатия дают только O(log n) (для сжатия без ранга это отдельный результат Тарьяна и ван Леувена, а не очевидность). Ранг после сжатия не пересчитывают - он остаётся верхней оценкой высоты.

Разбор: два find подряд

Цепочка a → b → c → r (корень r), и пусть так сложилось, несмотря на ранги (например, сжатие включили позже или дерево пришло из другой реализации).

Первый find(a): поднимаемся a → b → c → r - три шага вверх. Теперь обратный ход: parent[a] = r, parent[b] = r; на c цикл пока parent[x] != r уже останавливается - c и так висел на корне. Итого три шага вверх и ДВЕ записи. Дерево стало плоским: a, b, c висят прямо на r.

Второй find(a): parent[a] == r, и parent[r] == r - один шаг. То же для find(b) и find(c). Более того, любой будущий find элемента, который окажется под a, тоже выиграет: путь сократился для всей ветви.

Сравни суммарную работу. Без сжатия сто вызовов find(a) стоили бы 100 × 3 = 300 шагов. Со сжатием - 3 + 99 × 1 ≈ 102, и почти вся экономия пришла от одной-единственной дополнительной записи на узел. Это и есть амортизация в чистом виде: первый вызов платит за всех.

Разбор: почему «почти константа» и почему не просто константа

Полное доказательство границы α - одно из самых тонких в анализе структур данных, и здесь важнее понять, ЧТО именно делает сжатие, чем воспроизвести выкладку. Ключевое наблюдение: когда узел перевешивают на корень, его новый родитель имеет СТРОГО БОЛЬШИЙ ранг, чем прежний (ранг вдоль пути к корню строго возрастает). Значит один и тот же узел нельзя двигать бесконечно: каждый переезд поднимает ранг его родителя, а ранги ограничены log₂ n. Честно говоря, само по себе это даёт только O(m·log n): каждый узел переезжает не больше log₂ n раз. Чтобы получить α, Тарьян разбивает ранги на блоки (границы блоков растут как башня степеней) и считает отдельно переезды ВНУТРИ блока и переходы МЕЖДУ блоками: блоков оказывается α(n) штук, и суммарная работа за m операций - O(m·α(n)). Полное доказательство сюда не поместится, но важно не потерять, где проходит граница: наблюдение про рост ранга даёт логарифм, а константу даёт разбиение на блоки.

Что такое α. Функция Аккермана A(k, j) строится ступенями: A(0, j) = j + 1 (прибавить единицу), каждая следующая ступень - это повторение предыдущей j раз, то есть сложение, умножение, возведение в степень, башня степеней и дальше вверх. Растёт она чудовищно быстро уже на третьей-четвёртой ступени. α(n) - обратная к ней: НОМЕР СТУПЕНИ, которой хватает, чтобы перешагнуть n. Насколько медленно это растёт, удобно понять через более простую функцию log* (сколько раз надо взять логарифм, чтобы получить число не больше единицы): log*(65536) = 4, log*(2^65536) = 5. Так вот, α растёт МЕДЛЕННЕЕ, чем log*. Практический итог: α(n) <= 4 для всех n, которые можно записать в этой вселенной, поэтому в оценках её часто просто опускают.

Но называть операцию константной нельзя, и это не педантизм: Тарьян доказал НИЖНЮЮ границу - Ω(m·α(n)) - для алгоритмов в модели указателей с разделением (separable pointer machine), то есть для естественного класса реализаций вроде нашей. α - не слабость анализа, а свойство самой задачи. Правильная формулировка звучит так: «амортизированно почти константа, и лучше не бывает».

Что ломается без этого

Первое: сжимать путь, но подвешивать корни как попало, - получится O(log n) вместо α, и на специально подобранном входе разница заметна. Второе: реализовать find рекурсивно и получить переполнение стека на длинной цепочке - при первом же вызове на непожатом дереве глубина может быть большой; итеративный вариант безопаснее. Третье: сжимать путь в структуре, которой нужен откат к прежнему состоянию (такие структуры называют персистентными: они хранят все свои версии и умеют отвечать на запрос «а как было до этого объединения») - переписывание указателей уничтожает историю, там оставляют только ранг. Четвёртое: пересчитывать ранги после сжатия «для точности» - лишняя работа, ранг обязан быть лишь верхней оценкой. Пятое: ожидать O(α) от КАЖДОГО вызова - оценка амортизированная: первый find по длинной цепочке честно заплатит за всю её длину.

Зачем это в работе

Практический вывод простой: пишешь union-find - пиши сразу обе оптимизации, они занимают три строки и превращают структуру в почти бесплатную. В алгоритме Крускала это доводит стоимость до O(E·log E), где логарифм берётся сортировкой рёбер, а не работой со множествами: структура перестаёт быть узким местом вовсе. Так же ведут себя разметка связных областей на изображениях (миллионы пикселей), проверка перколяции, дедупликация, объединение эквивалентных типов в компиляторах, оффлайновый поиск наименьшего общего предка.

Более широкий урок этой главы - про амортизацию как инженерный инструмент. Union-find устроен по принципу «плати за уборку тогда, когда всё равно пришёл»: сжатие не делает лишнего прохода, оно использует уже состоявшийся подъём. Тот же принцип ты видел в удвоении динамического массива, в ленивом удалении из очереди, в уплотнении кучи Фибоначчи при извлечении минимума. Заметив его, начинаешь замечать и обратное: код, который «наводит порядок» отдельным проходом там, где можно было попутно.

Теперь сам

Дерево-цепочка: parent = [0, 0, 1, 2, 3] (то есть 4 → 3 → 2 → 1 → 0). Выполни find(4) со сжатием пути и выпиши массив parent. Сколько шагов сделает после этого find(3)? А find(4)?

Ответ. find(4): поднимаемся 4 → 3 → 2 → 1 → 0, корень 0, подъём - четыре шага. Обратный ход перевешивает на корень каждый узел пути: parent[4] = 0, parent[3] = 0, parent[2] = 0, parent[1] = 0 (последний уже указывал на 0). Массив становится parent = [0, 0, 0, 0, 0] - дерево стало плоским целиком. Теперь find(3): parent[3] == 0, а parent[0] == 0 - значит один шаг. И find(4) тоже один шаг. Заметь, что выиграл не только узел 4, ради которого всё затевалось, но и все промежуточные - 3, 2 и 1; именно поэтому амортизированная стоимость получается такой низкой: одна операция оплачивает путь сразу для целой группы. И обрати внимание на то, чего в этом примере не было: рангов. Сжатие само по себе даёт только O(log n) в среднем; чтобы получить α, нужны оба приёма - иначе длинные цепочки будут создаваться заново быстрее, чем сжатие успевает их распрямлять.

Главное

Сжатие пути: find всё равно поднимается до корня - значит на обратном ходу он перевешивает каждый узел пути прямо на корень (или однопроходно на деда - «деление пути пополам», та же оценка и меньшие константы). Знание, добытое подъёмом, сохраняется, и следующий find для всей ветви стоит один шаг. Вместе с объединением по рангу это даёт амортизированную цену O(α(n)), где α - обратная функция Аккермана, растущая медленнее, чем log*; α(n) <= 4 для любого записываемого n. По отдельности приёмы дают лишь O(log n): нужны оба. Слово «почти» существенно - Тарьян доказал нижнюю границу Ω(m·α(n)) в модели указателей, то есть α - свойство задачи, а не слабость анализа. Оценка амортизированная: отдельный find по длинной цепочке заплатит за всю её длину, зато оплатит её сразу для всех узлов пути. Принцип, который стоит унести шире структуры: прибирайся там, куда всё равно пришёл.