Инвариант представления: чем реализация держит обещание

Коротко

Откуда реализация ЗНАЕТ, что её операция уложится в обещанную цену? Она держит инвариант представления - условие, истинное между операциями, на которое каждая операция опирается и которое каждая сохраняет. Отсортированный массив держит порядок - и поэтому находит бинарным поиском за O(log n). Динамический массив держит num ≤ size и удваивается при заполнении - и поэтому вставка O(1) амортизированно. Нарушь инвариант снаружи - и обещание цены (или даже корректности) рухнет. Поэтому амортизированную цену тоже пишут в контракт честно: «O(1) амортизированно», а не «O(1) всегда».

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

Как думаешь, откуда берётся обещание «найду за log n»

Реализация обещает: бинарный поиск в массиве - O(log n). Но бинарный поиск работает только на ОТСОРТИРОВАННОМ массиве: он на каждом шаге отбрасывает половину, полагаясь на то, что слева меньше, справа больше. На беспорядочном массиве он даст неверный ответ. Значит, обещание держится не само по себе - оно опирается на условие «массив отсортирован». Кто-то должен это условие ПОДДЕРЖИВАТЬ. Такое условие, на которое операции опираются и которое сами же сохраняют, и называют инвариантом представления.

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

Библиотека обещает найти книгу за минуту. Обещание держится на порядке: книги стоят по алфавиту (это инвариант). Пришёл посетитель, поставил книгу куда попало - порядок нарушен, и следующий поиск «по алфавиту» промахнётся. Поэтому в библиотеке книги ставят на место сотрудники, а не читатели: только так инвариант выживает между запросами. Реализация структуры - тот же библиотекарь: каждая её операция обязана вернуть полку в порядок, иначе обещание «найду быстро» перестаёт работать.

Механизм: условие, которое каждая операция бережёт

Инвариант представления - это условие про внутреннее состояние, истинное ДО и ПОСЛЕ каждой операции (внутри операции оно может временно нарушаться). Работает он в связке: каждая операция ОПИРАЕТСЯ на инвариант (пользуется тем, что он верен) и ОБЯЗАНА его восстановить к своему концу. Разберём два примера.

Отсортированный массив. Инвариант: a[0] ≤ a[1] ≤ ... ≤ a[n−1]. На него опирается поиск (бинарный, O(log n)). Его обязана сохранить вставка: она ставит новый элемент не в конец, а на его место в порядке (за O(n) - сдвигает хвост). Дорогая вставка - плата за дешёвый поиск, и держится всё на инварианте порядка.

Динамический массив. Инвариант: num ≤ size, и буфер удваивается ровно при заполнении. На него опирается обещание «вставка O(1) амортизированно»: раздел про амортизацию доказал это потенциалом Φ = 2·num − size - но доказательство верно ТОЛЬКО пока буфер удваивается. Нарушь правило удвоения (расти на +1) - и инвариант другой, и вставка честно становится O(n) амортизированно.

Правило

Инвариант представления - условие про внутреннее состояние, истинное между операциями: каждая операция на него опирается и каждая его восстанавливает. На инварианте держится и корректность, и обещанная стоимость. Нарушишь инвариант извне (полезешь в приватное представление) - и операции перестают держать и цену, и правильность. Обещание цены - это всегда обещание «при сохранённом инварианте».

Разбор: инвариант динамического массива

Вернёмся к динамическому массиву из прошлого раздела уже с новым словом. Почему его append стоит O(1) амортизированно? Потому что реализация держит инвариант: занято не больше, чем вмещает буфер (num ≤ size), и как только num упёрся в size, буфер удваивается. Этот инвариант - причина, по которой потенциал Φ = 2·num − size остаётся неотрицательным, а значит амортизированная цена выходит константной. Убери удвоение - инвариант станет другим, потенциал перестанет работать, и та же операция «добавить в конец» подорожает до O(n) амортизированно. То есть обещанная цена - не свойство операции самой по себе, а следствие инварианта, который реализация бережёт.

Разбор: амортизированную цену пишут в контракт честно

Раз обещание цены опирается на инвариант, его и формулируют аккуратно. append в динамический массив - это не «O(1) всегда»: отдельная вставка при удвоении стоит O(n). Честная запись контракта - «O(1) амортизированно», то есть по любой серии вставок средняя цена константна. Разница не придирка: если ты рассчитываешь на O(1) в каждом ОТДЕЛЬНОМ вызове (скажем, у тебя жёсткий предел времени на один шаг реального времени), редкая дорогая вставка тебя подведёт. Поэтому в контракте пишут именно тот вид цены, который гарантирован: «амортизированно», «в среднем», «в худшем» - это разные обещания, и путать их нельзя.

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

Главная беда - нарушить инвариант снаружи, полезши в приватное представление. Влез руками в буфер динамического массива, сбил num - и append начинает писать не туда; переставил элементы отсортированного массива - и бинарный поиск молча промахивается. Именно поэтому внутренности контейнеров прячут: не из вредности, а чтобы никто извне не сломал инвариант, на котором держатся все обещания. Вторая беда - принять амортизированную цену за гарантию на каждый вызов и напороться на редкую дорогую операцию там, где важен именно худший ОДИН шаг.

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

Инвариант объясняет, почему нельзя менять внутренности стандартных структур и почему поля контейнеров прячут (это и называют инкапсуляцией - «спрятать внутренности за операциями», дать снаружи только контракт, а не сами данные). Структура держит инвариант в своём собственном коде - в тех самых операциях; пусти чужой код к внутренним полям напрямую - и он его нарушит, а поймать такую поломку тяжело: структура «иногда» отвечает неверно. Отсюда же практическое правило: если структура обещает цену «амортизированно» или «в среднем», а тебе нужен предсказуемый ХУДШИЙ случай на каждый вызов (реальное время, интерактивность), выбирай структуру с гарантией в худшем случае - обещания разной силы решают разные задачи. Умение читать, КАКОЙ вид цены гарантирован, - часть инженерного выбора структуры.

Теперь сам

Стек (кладём и снимаем только с одного конца) реализован на динамическом массиве: элементы лежат в буфере, num - сколько занято. Какой инвариант держит реализация и на что он опирает обещание «push и pop - O(1) амортизированно»?

Ответ. Инвариант тот же, что у динамического массива: num ≤ size, и буфер удваивается при заполнении (а push кладёт в a[num] и растит num, pop - уменьшает num). На нём держится цена: pop всегда снимает с конца за O(1), а push - O(1) амортизированно, потому что удвоение - редкое (доказано потенциалом Φ = 2·num − size в прошлом разделе, и доказательство верно ровно пока инвариант удвоения соблюдён). Обещание «O(1) амортизированно» - следствие инварианта: расти буфер на константу, инвариант стал бы другим, и push подорожал бы до O(n) амортизированно.

Главное

Инвариант представления - условие про внутреннее состояние, истинное между операциями: каждая на него опирается и каждая его восстанавливает. На нём держится и корректность, и обещанная цена. Отсортированный массив держит порядок - отсюда поиск O(log n); динамический массив держит num ≤ size с удвоением - отсюда вставка O(1) амортизированно. Нарушишь инвариант извне - рухнут и цена, и правильность, поэтому внутренности прячут. И цену в контракт пишут честно по её виду: «O(1) амортизированно» - не то же, что «O(1) всегда».