Стоимость операции - часть контракта

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

Как думаешь, раз ответы одинаковые - всё равно какую реализацию брать

В прошлой главе мы увидели: у одного абстрактного типа много реализаций, и все дают одни и те же ответы. Соблазн сделать вывод «значит, бери любую» - и он неверный. Одинаковый ответ не значит одинаковая цена. Одна реализация ответит на «принадлежит ли x?» мгновенно, другая переберёт полсписка. На десяти элементах разницы не заметишь, на миллионе - программа из мгновенной станет минутной. Значит, у выбора есть второй слой, кроме «что операция делает»: сколько она СТОИТ.

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

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

Механизм: таблица «операция × реализация»

Опиши абстрактный тип не только операциями, но и их СТОИМОСТЬЮ у каждой реализации. Получается таблица: строки - операции, столбцы - реализации, в клетках - порядок роста. Возьмём последовательность (тот самый «список») в двух реализациях: массив (элементы подряд в памяти) и связный список (цепочка узлов со ссылкой на следующий).

\* амортизированно, за счёт удвоения буфера - об этом следующий урок.

Клетки разные, и это не мелочь: массив мгновенно берёт i-й (адрес считается арифметикой), но дорого вставляет в начало (надо сдвинуть весь хвост); связный список наоборот - вставит в начало за шаг (перецепил ссылку), но за i-м элементом идёт от головы по цепочке. Выбор реализации - это выбор, какие операции сделать дешёвыми за счёт каких дорогих.

Правило

Стоимость каждой операции - такая же часть контракта, как и её поведение. Одна абстракция в разных реализациях даёт одинаковые ответы, но разную цену. Выбирай реализацию по таблице «операция × реализация»: посмотри, какие операции тебе нужны ЧАСТО, и возьми ту, где именно они дёшевы. «По привычке» - не критерий; критерий - профиль твоих операций.

Разбор: «принадлежит?» - список против множества

Вопрос «лежит ли x в структуре?» - одна операция АТД «множество элементов». В списке ответ ищут перебором: идут по элементам, пока не встретят x или не кончится список, - до n сравнений, O(n). В множестве значение превращают в адрес ячейки и смотрят сразу туда - O(1) В СРЕДНЕМ, независимо от размера (внутри работает хеш-таблица; её устройство и почему цена именно «в среднем», а не «всегда», - отдельный раздел дальше, здесь берём как готовый инструмент). Ответ («да/нет») у обоих один и тот же. А цена отличается принципиально: спрятать проверку «принадлежит?» внутрь цикла по n элементам - и со списком выйдет O(n²), а с множеством O(n). Это ровно та задача, которую ты будешь решать в конце главы: одна операция, две обёртки, квадрат против линии.

Разбор: «взять i-й» - массив против связного списка

Обратный пример, где выигрывает уже массив. «Взять i-й элемент»: в массиве адрес i-го - это начало + i · размер_элемента, чистая арифметика, O(1), хоть первый элемент, хоть миллионный. В связном списке прямого адреса нет: чтобы попасть в i-й узел, идёшь от головы по ссылкам i раз - O(n). Поэтому «пройти по всем подряд» связный список делает нормально (шаг за шагом), а «дай мне сразу серединный» - медленно. Тот же интерфейс «последовательность», а сильные стороны противоположные: массив силён в индексации, список - во вставке с краю.

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

Первая беда - выбирать структуру по привычке («везде беру список») и получить квадрат там, где годилось множество: проверка «принадлежит?» в цикле - классический источник внезапно медленного кода. Вторая - помнить про поведение, но забыть про цену: «оба хранят последовательность, разницы нет» - и вот индексация по связному списку в цикле снова даёт O(n²). Абстракция прячет устройство, и поэтому цену операций надо держать в голове ОТДЕЛЬНО - сама она из интерфейса не видна.

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

Каждый раз, выбирая между list, set и dict в Python (или их аналогами в любом языке), ты выбираешь по этой таблице. Нужны частые проверки «есть ли элемент?» или «убрать дубликаты» - бери set/dict с их O(1), а не список с O(n). Нужен доступ по индексу и проход подряд - бери список. Нужны частые вставки в начало - в Python для этого есть deque (двусторонняя очередь) с O(1) на оба конца, тогда как у списка вставка в начало O(n). Опытный инженер не помнит эти клетки наизусть как таблицу умножения - он умеет прикинуть цену операции из устройства реализации, и следующие главы учат именно этому.

Теперь сам

Тебе нужна структура, куда часто добавляют элементы и часто спрашивают «а такой уже есть?», а вот по номеру i обращаться не приходится вовсе. Что важнее в этой задаче - дешёвая индексация или дешёвая проверка принадлежности? Список или множество?