Конспект: абстрактный тип и реализация

Понятия

Абстрактный тип данных (АТД) - описание структуры набором операций и их контрактом (что каждая делает), без единого слова о хранении в памяти. Пример: «список» - это длина, взять(i), добавить, вставить, удалить плюс обещания их поведения.

Реализация - конкретное представление данных в памяти плюс код операций под это представление. Одной абстракции отвечает МНОГО реализаций.

Стоимость операции - часть контракта наравне с поведением. Разные реализации одного АТД дают одинаковые ответы, но разную цену операций.

Таблица «операция × реализация» - способ выбрать реализацию: строки - операции, столбцы - реализации, в клетках - порядок роста. Берут ту, где ЧАСТЫЕ операции дёшевы.

Инвариант представления - условие про внутреннее состояние, истинное между операциями: каждая на него опирается и каждая его восстанавливает. На нём держится и корректность, и обещанная цена.

Что унести

Абстракцию и реализацию разделяют, чтобы код-пользователь опирался на операции, а не на устройство: тогда начинку можно поменять, ничего не сломав. На этом стоит вся стандартная библиотека - list, dict, set - интерфейсы, начинка спрятана.

Одинаковый ответ - не одинаковая цена. Выбор реализации - это выбор по профилю операций: какие нужны часто и где именно они дёшевы.

Ключевые клетки таблицы:

Массив силён в индексации, связный список - во вставке с краю, множество - в проверке принадлежности. «Принадлежит?» в цикле по n - это O(n²) со списком и O(n) с множеством: та самая задача главы.

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

Вид цены пишут в контракт честно: «O(1) амортизированно», «в среднем», «в худшем» - разные обещания. append - не «O(1) всегда»: отдельная вставка при удвоении O(n), гарантирована средняя по серии.

Ловушки джокера

Спутал интерфейс с реализацией. Заложился на «как хранится» (читаю память напрямую) - и код привязан к одной реализации, сменят её, и всё посыпется.

Решил, что раз ответы равны, реализации взаимозаменяемы. Ответ один, цена разная; индексация по связному списку в цикле снова даёт O(n²).

Выбрал структуру по привычке. «Везде беру список» - и проверка «принадлежит?» в цикле даёт квадрат там, где годилось множество.

Полез в приватное представление снаружи. Нарушил инвариант - структура начинает «иногда» отвечать неверно, и поймать это тяжело.

Принял амортизированную цену за гарантию на каждый вызов. Где важен худший ОДИН шаг (реальное время), редкая дорогая операция подведёт - нужна гарантия в худшем случае.

Проверь себя

Чем абстрактный тип отличается от реализации?

Почему две реализации одного АТД дают одинаковые ответы, но выбирают между ними по цене?

Где дешевле «принадлежит?» и где «взять i-й» - и почему?

Что такое инвариант представления и на что он опирает обещанную стоимость?

Почему append пишут «O(1) амортизированно», а не «O(1) всегда»?