Амортизационный анализ
Также: Amortized analysis · амортизированная сложность · амортизированно O(1) · метод бухгалтера · метод потенциалов · accounting method · potential method · двоичный счётчик · очередь на двух стеках
«Добавление в конец — O(1) амортизированно» — а на замере одно добавление из четырёх миллионов длится 57 миллисекунд. Что на самом деле обещает амортизированная оценка, три способа её доказать — суммой, монетами и потенциалом — и что делают системы, которым редкая долгая пауза недопустима.
Четыре миллиона раз подряд программа на Go добавляет число в конец среза, и каждое добавление засекает отдельно. В среднем выходит около сотни наносекунд. Но три десятка добавлений из четырёх миллионов длятся миллисекунды, а самое долгое — 57 мс, в шестьсот тысяч раз дольше среднего: в такие моменты срез переезжает в память побольше и копирует всё, что в нём было. Ниже — тот же замер на сервере сайта для четырёх структур.
Срез в Go и словарь в Python ведут себя одинаково: почти все операции укладываются в тонкую полосу внизу, а самые высокие столбы — моменты, когда структура перестроилась целиком: у среза 57 мс на переезде к 3,2 миллиона элементов, у словаря 75 мс. Список в Python растёт так же часто, но его перестройки почти ничего не стоят: память под него выделяется функцией realloc, которая часто просто удлиняет блок на месте, без копирования. А карта в Go с версии 1.24 разбита на маленькие таблицы и перестраивает их по одной. И всё же столбы в миллисекунды есть у всех четырёх: у карты Go их десять, и ни один не совпадает с перестройкой. Это паузы не структуры, а машины: сервер делит процессор с другими программами, а песочница, в которой исполняется код, медленнее обычной системы выдаёт программе новую память. От устройства структуры такие паузы не зависят. И при всём этом про все четыре структуры правильно сказать: добавление стоит O(1) амортизированно. Что это значит и чего не значит — тема статьи.
Идея
Амортизированная стоимость операции — это не время одной операции и не среднее по случайным входам. Это обещание про последовательность: любые m операций подряд, в каком бы порядке их ни вызвали, вместе стоят не больше m·c. Дорогие операции бывают, но они редки и оплачены дешёвыми, которые были до них.
Отличие от среднего важно. Средняя оценка, как у быстрой сортировки, говорит: на случайных данных обычно быстро, но злой вход может всё испортить. Амортизированная гарантирует сумму всегда, на любых входах, — случайности в ней нет. Зато она ничего не обещает про отдельную операцию: отдельное добавление в срез может стоить O(n), и замер выше это показывает.
Слово взято из бухгалтерии: большую покупку списывают по частям на много лет вперёд. Откуда берутся множители роста массивов и почему вдвое, а не на единицу, — в статье о динамическом массиве. Здесь — три способа доказывать такие оценки и что они говорят о настоящих структурах.
Способ первый: сложить всё
Самый прямой способ — посчитать стоимость всей последовательности и поделить на число операций. Двоичный счётчик: прибавляем к нему единицу n раз, начиная с нуля. Одно прибавление переключает хвост из единиц и ещё один бит — от 0111 к 1000 переключаются все четыре. В худшем случае это все биты числа. Но посмотрим на каждый бит отдельно.
n прибавлений единицы к двоичному счётчику, начиная с нуля, переключают меньше 2n бит.
Младший бит переключается при каждом прибавлении, следующий — через раз, бит номер j — раз в 2j прибавлений: всего ⌊n/2j⌋ раз. Сумма по всем битам — n + n/2 + n/4 + … < 2n.
Сумма ⌊n/2⌋ + ⌊n/4⌋ + … считается и точно: она равна n минус число единиц в двоичной записи n. Поэтому миллион прибавлений переключают ровно 2 000 000 − 7 = 1 999 993 бита — так и печатает программа ниже. С массивом то же самое: если ёмкость каждый раз удваивается, то к моменту, когда в массиве n элементов, копирования стоили 1 + 2 + 4 + … + n/2 < n, и вместе с самими записями выходит меньше 2n.
Способ второй: монеты
Сложить всё удаётся не всегда — операции бывают разные, и их последовательность заранее неизвестна. Тогда назначают каждой операции плату, как в магазине, — не её настоящую стоимость, а фиксированную сумму. Если операция стоит меньше, чем заплатила, разница идёт в копилку; если больше, недостающее берут из копилки. Если копилка никогда не уходит в минус, то сумма плат — оценка сверху для суммы настоящих стоимостей. Это метод бухгалтера.
Для счётчика плата — две монеты. Прибавление ставит ровно одну единицу: одну монету оно тратит на это переключение, а вторую кладёт на новую единицу. Стирание хвоста из единиц оплачивают монеты, которые на них лежат. Монет на счётчике всегда столько, сколько в нём единиц, — меньше нуля не бывает, и 2n монет хватает на n прибавлений.
Для массива, который растёт вдвое, хватает трёх монет за добавление: одна оплачивает запись, две идут в копилку. После роста от ёмкости k до 2k копилка пуста, а до следующего роста будет k добавлений — они положат 2k монет, ровно столько, сколько стоит копирование 2k элементов. Под графиком в первой сцене тот же счёт проведён на настоящей последовательности роста среза в Go: видно, какой платы хватает и как копилка опустошается на каждом росте.
Способ третий: потенциал
Монеты удобно положить не на элементы, а на всю структуру: пусть Φ — число, которое зависит только от состояния структуры, «запасённая энергия». Амортизированной стоимостью операции назовём её настоящую стоимость плюс изменение Φ. Если Φ в начале ноль и никогда не бывает отрицательным, сумма амортизированных стоимостей не меньше суммы настоящих: все изменения Φ складываются в Φконец − Φначало ≥ 0.
Пусть массив растёт в g раз (g > 1), когда заполнен. Тогда добавление стоит не больше 1 + g/(g − 1) амортизированно.
Возьмём Φ = g/(g − 1) · (n − C/g), где n — число элементов, C — ёмкость. Сразу после роста n = C/g и Φ = 0, а дальше n только растёт, так что Φ ≥ 0. Добавление без роста стоит 1 и увеличивает Φ на g/(g − 1): амортизированно 1 + g/(g − 1). Добавление с ростом происходит при n = C: оно копирует C элементов, и потенциал перед ним равен g/(g − 1) · C(1 − 1/g) = C — ровно на копирование. После роста потенциал снова ноль, плюс одна запись. Итого не больше 1 + g/(g − 1) в обоих случаях.
При удвоении это 3, при росте в полтора раза — 4, а при росте в 1,25 раза — уже 6. Так выглядит выбор, который делает каждый язык: чем меньше множитель, тем меньше пустой памяти держит массив, но тем больше раз каждый элемент переезжает. Срезы Go растут вдвое, пока они маленькие, а с нескольких сотен элементов множитель плавно уменьшается к 1,25. В CPython список растёт примерно на восьмую часть: s + s/8 + 6 — это разбирает задача о росте списка.
Код
Три множителя на миллионе добавлений, наименьшая достаточная плата и проверка формулы для счётчика:
Плата при росте в 1,25 раза вышла 6,14, чуть больше теории. Дело в маленьких массивах: ёмкость 1, умноженная на 1,25 с округлением вниз, — снова 1, и такой массив растёт на единицу, копируя всё при каждом добавлении. Теорема про множитель g работает, когда множитель настоящий, поэтому настоящие реализации начинают с ёмкости побольше или первое время растут вдвое.
Вторая классика — очередь на двух стеках. Кладём во «вход», берём из «выхода», а когда выход пуст, перекладываем в него весь вход. Отдельное извлечение может переложить сотни тысяч элементов, но каждый элемент перекладывается не больше одного раза за всю жизнь, — значит, перекладываний не больше, чем добавлений.
Когда амортизации мало
Амортизированная оценка хороша, когда важно общее время: обработать файл, посчитать отчёт. Но бывает, что важна каждая операция. Игре нужно уложить кадр в 16 миллисекунд, серверу — ответить каждому клиенту быстро, а не всем в среднем. Пауза в пять миллисекунд на одной записи из миллиона для такой системы — сбой, сколько бы ни стоили остальные. Тогда дорогую работу раскладывают на части, и это называют деамортизацией:
- Перестройка по частям. Redis при росте хеш-таблицы держит две таблицы сразу, старую и новую, и при каждом обращении переносит в новую по корзине, а в свободное время — столько, сколько успеет за миллисекунду. Ни одна операция не платит за перестройку целиком.
- Много маленьких таблиц. Карта в Go с версии 1.24 состоит из таблиц не больше чем на 1024 места; когда таблица заполняется, делится на две только она. Цена одного роста ограничена размером таблицы, а не всей карты, — на замере это видно.
- Сборка мусора. Сборщики мусора в Go и Java работают в основном параллельно с программой и частями, чтобы не останавливать её надолго, — по той же причине.
Есть и случай, когда амортизация ломается совсем: если можно вернуться к старому состоянию и повторить дорогую операцию. Дорогое прибавление к счётчику 0111…1 оплачено монетами, которые копились долго, но если сразу вычесть единицу и прибавить снова, монет уже нет, а операция снова дорогая. Задача о счётчике туда-обратно построена именно на этом. По той же причине амортизированные оценки плохо переносятся на персистентные структуры, где любая старая версия остаётся доступной.
Сколько это стоит
| Структура и операция | Амортизированно | Одна операция в худшем случае |
|---|---|---|
| Динамический массив, добавление в конец | O(1) | O(n) — копирование при росте |
| Хеш-таблица, вставка | O(1) в среднем | O(n) — перестройка, если она не по частям |
| Очередь на двух стеках, извлечение | O(1) | O(n) — перекладывание |
| Двоичный счётчик из k бит, прибавление | O(1) | O(k) |
| Монотонный стек, новый элемент | O(1) | O(n) — снять со стека всех |
| Система непересекающихся множеств | O(α(n)) | O(log n) при слиянии по размеру |
| Косое дерево, поиск | O(log n) | O(n) |
Сам анализ ничего не стоит программе — это способ рассуждать. Но выбор между амортизированной структурой и структурой с гарантией на каждую операцию — инженерный: первая обычно проще и быстрее в сумме, вторая нужна там, где важен хвост задержек, а не среднее.
Оба способа — бухгалтерский и через потенциал — подробно описал Роберт Тарьян в статье «Amortized computational complexity» 1985 года. В том же году он вместе с Дэниелом Слейтором опубликовал косые деревья, для которых амортизированная оценка — главная: отдельная операция там бывает линейной, а любые m операций стоят O(m log n).
Задачи
В первой счётчик ходит туда и обратно, и оценка «меньше двух переключений на операцию» перестаёт работать. Во второй — точное правило роста списка в CPython: сколько раз он выделит память и сколько элементов скопирует.
Счётчик туда-обратно Как растёт список Python