adt

Абстрактный тип данных (ADT)

Предпосылки: базовое программирование (переменные, типы, условия, циклы, функции), ссылки, базовое чтение Ruby (методы, блоки, массивы и хеши), оценка сложности в O(…).

Массив →

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

Тут возникает соблазн сказать «я работаю с этим набором» и считать, что набор и его внутренняя раскладка — одно и то же. Этот взгляд держится ровно до первой замены раскладки. Допустим, код перебирает элементы:

i = 0
while i < collection.size
  puts collection.get(i)
  i += 1
end

Этот цикл не знает, лежат ли элементы подряд в одном блоке или разбросаны по памяти и связаны ссылками. Он опирается только на то, что у набора есть size и get(i). Поменяем сплошной блок на связку через ссылки — цикл продолжает работать без единого изменения. Поменяли бы мы вместо этого вызов на что-то, чего у второй раскладки нет, — цикл бы сломался.

Значит, набор полезно описывать не его внутренней раскладкой, а набором операций и их поведением: что можно сделать (size, get(i), set(i, value)) и что каждая операция гарантирует (get(i) возвращает ранее записанный элемент номер i). Такое описание — обещание, которое внешний код видит и на которое опирается, не заглядывая внутрь. Это обещание называется абстрактным типом данных (ADT, Abstract Data Type): «абстрактный» — потому что он говорит, что делает структура, и молчит, как именно.

Раскладка, выполняющая обещание, — это реализация ADT. Реализаций у одного ADT может быть несколько, и они взаимозаменяемы: код, опирающийся только на операции, переживает любую замену реализации, потому что обещание не изменилось. Именно это разделение — операции снаружи, устройство внутри — позволяет рассуждать о выборе структуры на одном языке: какие операции нужны и с какой сложностью каждая обходится, отдельно от того, как они устроены под капотом.

Набор операций из примера выше — «положить n значений и достать любое по номеру за O(1)» — это ADT под именем Array. Его простейшая реализация, массив, кладёт элементы в один непрерывный блок. Дальше в серии та же дисциплина — сначала контракт, потом устройство — повторяется для связного списка, хеш-таблицы, дерева: у каждого свой набор обещанных операций и одна или несколько реализаций под ними.

Sources

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (abstract data types, contracts).

---

Массив →