Сжатие таблицы при удалениях: почему порог 1/4, а не 1/2

Если ты знаешь, почему порог сжатия ставят на 1/4, и умеешь доказать это потенциалом из двух ветвей, листай до «Теперь сам».

Как думаешь, что сломается при симметричном правиле

Прошлый урок доказал: удвоение при заполнении даёт вставку за O(1) амортизированно. Добавим удаление. Самое естественное правило - зеркальное: «стало заполнено меньше половины - ужми буфер вдвое». Звучит честно: после сжатия массив снова полон наполовину, как сразу после удвоения.

Прежде чем читать дальше, ответь себе: массив на 1024 элемента, буфер 1024, и дальше идёт бесконечная серия «вставить, удалить, удалить, вставить». Сколько элементов будет скопировано на каждые четыре операции? Если ответ «почти ничего» - урок как раз для тебя.

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

Термостат с одной точкой. Нагреватель включается, когда в комнате ниже 20 градусов, и выключается, когда выше 20. Комната стоит ровно на 20 - и реле щёлкает каждую секунду, пока не сгорит. Настоящие термостаты делают ЗАЗОР: включиться ниже 19, выключиться выше 21. Между порогами система спокойна, и чтобы её снова дёрнуть, нужно реально изменить температуру на два градуса, а не на сотую.

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

Механизм: два порога и потенциал из двух ветвей

ПРАВИЛА
вставка:  num = size  →  удвоить буфер, скопировать num, потом вставить
удаление: удалить; если теперь num < size/4  →  ужать вдвое,
          скопировать num

после удвоения заполнение 1/2, после сжатия - чуть меньше 1/2:
до любой следующей перестройки заполнение должно уйти до 1 или до 1/4

Потенциал теперь из двух ветвей - в зависимости от того, по какую сторону половины стоит коэффициент заполнения α = num/size:

Φ = 2·num − size        если α ≥ 1/2   (копим на удвоение)
Φ = size/2 − num        если α < 1/2   (копим на сжатие)

Обе ветви неотрицательны и обе равны нулю ровно при α = 1/2 - то есть сразу после любой перестройки запас пуст, и его надо накопить заново. Чем дальше заполнение уходит от половины в любую сторону, тем больше запас.

Цена операций (c - настоящая, ĉ = c + ΔΦ - амортизированная):

вставка при α ≥ 1/2, без удвоения     c = 1,      ΔΦ = +2      ĉ = 3
вставка с удвоением (num = size = s)  c = s + 1,  Φ: s → 2     ĉ = 3
вставка при α < 1/2                   c = 1,      ΔΦ = −1      ĉ = 0
удаление при α < 1/2, без сжатия      c = 1,      ΔΦ = +1      ĉ = 2
удаление со сжатием (было num = k, size = 4k)
                                      c = 1 + (k−1) = k
                                      Φ: (2k − k) = k  →  (k − (k−1)) = 1
                                      ĉ = k + 1 − k = 1
удаление при α ≥ 1/2                  c = 1,      ΔΦ = −2      ĉ = −1

Переходы через половину (вставка, после которой α стало 1/2, или удаление, после которого стало меньше) меняют ветвь, но значение Φ в точке α = 1/2 у обеих ветвей одинаковое (ноль), поэтому скачка нет, и цена такой операции тоже ограничена константой. Во всех случаях ĉ ≤ 3.

Правило

При вставках и удалениях буфер удваивают при заполнении 1, а сжимают вдвое при заполнении ниже 1/4 - не 1/2. Зазор между порогами гарантирует, что после любой перестройки (заполнение ровно половина) до следующей нужно Θ(size) операций. Доказательство - потенциал Φ = 2·num − size при α ≥ 1/2 и Φ = size/2 − num при α < 1/2: любая операция стоит не больше 3 амортизированно. Сжатие при 1/2 без зазора даёт Θ(n) на операцию на чередовании у границы.

Разбор: качели у границы при сжатии на половине

Возьмём симметричное правило и серию из начала урока. Буфер 1024, элементов 1024.

+   num = size = 1024 → удвоение, копируем 1024; size 2048, num 1025
−   num 1024 = ровно половина, сжатия нет
−   num 1023 < 1024 → сжатие, копируем 1023; size 1024
+   num 1024 = size, вставка без перестройки
+   ...и цикл повторяется: снова полон

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

def run(ops, porog):
    num, size, copies = 0, 1, 0
    for op in ops:
        if op == "+":
            if num == size:
                copies += num
                size *= 2
            num += 1
        else:
            num -= 1
            if size > 1 and num < size * porog:
                copies += num
                size //= 2
    return copies


n = 1024
zapolnenie = ["+"] * n                 # заполнили ровно до 1024
kacheli = ["+", "-", "-", "+"] * 1000  # туда-обратно у границы
for porog, imya in ((1 / 2, "сжатие при 1/2"),
                    (1 / 4, "сжатие при 1/4")):
    c = run(zapolnenie + kacheli, porog)
    print(f"{imya}: копирований {c}, на операцию {c / (n + 4000):.1f}")

сжатие при 1/2: копирований 2048023, на операцию 407.6
сжатие при 1/4: копирований 2047, на операцию 0.4

Разница в тысячу раз. При пороге 1/4 все 2047 копирований - это удвоения при первом заполнении (1 + 2 + 4 + ... + 1024), а качели вообще ничего не перестраивают: чтобы дойти до сжатия, нужно опустить заполнение с половины до четверти, то есть сделать сотни удалений подряд.

Разбор: сжатие по шагам с потенциалом

Проверим ветвь сжатия на числах. Буфер 16, элементов 4, заполнение ровно 1/4. Потенциал по ветви α < 1/2: Φ = 16/2 − 4 = 4.

удаляем элемент: num = 3 < 16/4 = 4 → сжатие
настоящая цена: 1 (удаление) + 3 (копируем оставшиеся) = 4
после: size = 8, num = 3, α = 3/8 < 1/2 → Φ = 8/2 − 3 = 1
амортизированная цена: 4 + 1 − 4 = 1

Откуда взялся запас 4? Его накопили удаления, которые вели массив от половины к четверти: каждое поднимало Φ на единицу. Если массив был 16 с 8 элементами (Φ = 0), то четыре удаления до 4 элементов накопили ровно Φ = 4 - и этим заплатили за копирование трёх оставшихся. Тот же механизм, что у удвоения, только зеркальный: дешёвые операции заводят пружину, перестройка её отпускает.

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

Симметричный порог - классическая ошибка, и её симптом коварен: на тестах всё быстро, потому что тесты обычно либо заполняют, либо очищают структуру. Медленно становится только на реальной нагрузке, где размер колеблется у одной точки - очередь задач, которая то наполняется, то разгребается. Профиль показывает, что всё время уходит в memcpy или в перевыделение памяти, а размер структуры почти не меняется. Вторая ошибка - не сжимать вовсе: тогда после пикового часа структура на миллион элементов держит память под миллион, хотя в ней сто. Третья - взять потенциал из одной ветви 2·num − size: при заполнении ниже половины он отрицательный, и доказательство перестаёт быть оценкой сверху.

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

Так устроены реальные контейнеры. list в CPython при удалении ужимает буфер, только когда занято меньше половины выделенного, а выделяет с запасом около восьмой части - зазор есть, просто другой формы. Хеш-таблицы с открытой адресацией расширяются при заполнении около 2/3 и не сжимаются при удалении вовсе, пока их не перестроят явно, - это сознательный выбор «память в обмен на отсутствие качелей». Когда пишешь свой кольцевой буфер, пул соединений или кеш с переменным размером, правило «расширять и сжимать на одном пороге» - первое, что стоит проверить в чужом коде.

Теперь сам

Буфер 64, элементов 32. Правило «удвоить при заполнении 1, ужать вдвое ниже 1/4». Сколько удалений подряд нужно сделать, чтобы случилось первое сжатие? Какой будет потенциал перед ним и сколько элементов скопирует сжатие?