Что такое абстрактный тип данных
Абстрактный тип данных
Из Википедии — свободной энциклопедии
Абстра́ктный тип да́нных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.
Формально АТД может быть определён как множество объектов, определяемое списком компонентов (операций, применимых к этим объектам, и их свойств). Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения — в этом и заключается суть абстракции. Абстрактный тип данных определяет набор функций, независимых от конкретной реализации типа, для оперирования его значениями. Конкретные реализации АТД называются структурами данных.
В программировании абстрактные типы данных обычно представляются в виде интерфейсов, которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании. Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешнего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надёжности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка с использованием различных методов динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Концепция Абстрактного Типа Данных
Доброго времени суток, хабравчане!
Следующий пост является изложением моих размышлений на тему природы классов и АТД. Эти размышления дополнены интересными цитатами из книг гуру разработки программного обеспечения
Введение
Начнем с того, что плавно подойдем к определению АТД. АТД, в первую очередь, представляет собой тип данных, что означет следущее:
наличие определенных доступных операций над элементами этого типа;
а также данные, относительно которых эти операции выполняются (диапазон значений).
Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:
Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.
Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:
АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).
Я считаю, что при разработке АТД сначала нужно определить интерфейс, так как интерфейс не должен зависеть от внутреннего представления данных в АТД. После определения операций, сотставляющих интерфейс, нужно сосредоточиться на данных, которые и будут реализовать заданное поведение АТД. В итоге мы получим некую структуру данных – механизм позволяющий хранить и обрабатывать данные. При этом, прелесть АТД в том, что если нам захочется изменить внутренне представление данных, то нам не придется блуждать по всей программе и менять каждую строку кода, которая зависит от данных, которые мы хотим поменять. АТД инкапсулирует эти данные, что позволяет менять работу объектов этого типа, а не всей программы.
Преимущества АТД
Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):
Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.
Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.
Стоит отметить, что концепция АТД нашла гирокое применение в ООП, т.к именно эта концепция дополняет ООП и позволяет уменшить сложность программ в быстроменяющемся мире требований к ПО.
Данную статью я писал для того, что бы обратить внимание разработчиков на АТД с целью повышения качества работы и разработки программного обеспечения.
Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».
Абстрактный тип данных. Часть 1: Данные (Тип Данных)
В данном цикле статье хочу поделиться приемом, который помогает мне решать весьма и весьма сложные логические задачи. Под сложной логической задачей подразумевается задача с большим количеством исходных параметров которые влияют на итоговый результат и так же могут влиять друг на друга, где сложно организовать корректное взаимодействие этих параметров и просто можно запутаться как в них, так и в логике организации кода. Начать хочу с данных, а управление данными будет во второй части.
Вместо предисловия
Абстрактный Тип Данных (далее АТД) — это набор, включающий данные и выполняемые над ними операции.… Набор данных и методов, служащих одной цели, — это и есть АТД (С. Макконнелл, “Совершенный код”, глава 6.1. Основы классов: абстрактные типы данных). В данном цикле статей будет рассмотрен именно такой взгляд на АТД, расширенный типом данных.
Информация — сведения независимо от формы их представления. Знания относительно фактов, событий, вещей, идей и понятий, которые в определенном контексте имеют конкретный смысл (ISO/IEC 2382:2015).
Данные — это зарегистрированная информация.
Информационные Технологии — это приемы, способы и методы применения средств вычислительной техники при выполнении функций сбора, хранения, обработки, передачи и использования данных (ГОСТ 34.003-90).
Класс, наряду с понятием «объект», является важным понятием объектно-ориентированного подхода в программировании (хотя существуют и бесклассовые объектно-ориентированные языки, например, Прототипное программирование)
Класс является типом данных, определяемым пользователем.
Вычисление — это получение из входных данных нового знания.
Сосотояние характеризуется тем, что описывает переменные свойства объекта. Состояние устойчиво до тех пор, пока над объектом не будет произведено действие. Формальное описание состояний в программировании — набор атрибутов, определяющих поведение объекта.
Действие (формулировка данной статьи) — изменение состояния данных в процессе вычислений и регистрация данного состояния не меняя при этом самих данных которые участвуют в вычислениях. Например: мы меняем состояние автомобиля на плоскости (находился в точке А, переместился в точку Б), при этом данные самого автомобиля мы не затрагиваем. Еще один пример: мы имеем какой либо документ у которого есть срок действия, в процессе вычислений мы получаем состояние документа на какой-то момент времени и фиксируем его, сообщаем/отмечаем, что на такой то момент времени документ действителен/недействителен, при этом сам документ мы не меняем.
Теперь к сути
Если не вдаваться в подробности, согласитесь, весь окружающий нас мир это объекты мира (имена существительные) материальные или нематериальные, параметры (свойства) этих объектов и действия которые можно производить с этими объектами или действия которые эти объекты производят самостоятельно.
Параметры у объектов мира есть всегда! У яблока например это его вкус, его цвет. У цели это ожидаемый результат, параметры достижения результата и т.д. и т.п. Объекты мира могут обладать каким либо действием, а могут и не обладать, но всегда действие можно применить к ним. Например обычная палка не способна самостоятельно производить какие либо действия, но мы можем применить к ней действие, допустим подпереть ею дверь. Автомобиль обладает действием “передвижение на плоскости”, и мы можем применить к нему действие, например завести двигатель или заглушить его. Также мы можем применить действие к автомобилю такое же как он может произвести самостоятельно, переместить его на плоскости (установить параметры нахождения на используемой плоскости).
Из вышесказанного можно сделать вывод — объект мира и его параметры неразделимы, в то время как действие необязательная его черта. Объект мира и его параметры это просто набор данных, зарегистрированная информация о данном объекте. Далее, при написании приложения, мы применяем действие к этим наборам данных.
Т.о. первая задача которая стоит перед нами, это корректное выделение данных из всего нас окружающего, данных к которым будем применять действие.
Научившись корректно выделять данные вам значительно легче будет решать логически сложные задачи, код станет более гибким т.к. изменяя логику работы с одними данными вы не будете задевать другие части программы. Блоки кода будут менее зависимы друг от друга. В голове будет ясность и понимание что да как работает.
Далее, выделенные данные (совокупность объекта мира и его параметров) буду определять как Тип Данных (далее ТД).
ТД (формулировка данной статьи) — атомарная, неделимая единица данных определяемая пользователем, представляющая из себя совокупность объекта мира и его параметров. ТД не способен производить действие.
В концепции ООП ТД это класс, в классе мы определяем поля которые хранят данные и как было написано выше, создавая класс мы создаем новый тип данных определяемый пользователем. СУБД служат для хранения данных и работы с ними — то же самое, нам надо корректно определить данные (сущности БД), с которыми мы в дальнейшем будем работать, применять действие.
Для корректного выделения ТД (данных) из окружающего нас мира определил следующие правила:
До данного момента говорил о данных в ООП и данных в реляционной СУБД, но в них есть существенное отличие, данные в БД не могут производить вычисления сами над собой, это просто зарегистрированная информация, в то время как ТД ООП может производить вычисление со своими данными, хотя принципы выделения ТД одинаковые. Более того, в ООП Классы данных являются плохим тоном и придают коду “запашок”, ТД в ООП должен уметь производить вычисления со своими данными, например для фигуры он должен быть способен вычислить ее площадь.
Может возникнуть закономерный вопрос — чем отличается ТД ООП от АТД по С.Макконнеллу? ТД ООП (по определению данной статьи) может производить вычисления со своими данными, но не может придавать им действие, в то время как АТД может производить вычисления со своими наборами данных, получать результаты вычислений ТД и придавать им действие (формулировку, что такое действие смотрите выше)
Какие есть требования по работе ТД ООП со своими данными смотрите ниже.
Чтобы лучше донести свою мысль, давайте рассмотрим классический пример, Квадрат и Ромб:
И квадрат и ромб являются частным случаем параллелограмма. Обе фигуры соответствуют первому правилу, это параллелограмм, но не соответствуют второму правилу, для квадрата нам достаточен один параметр (длина одной из сторон), тогда как для ромба это два параметра (длина одной из сторон и размер одного из углов). Т.о. это различные типы данных, в ООП эти фигуры должны быть представлены различными классами и различными таблицами в реляционной БД.
У кого-то наверняка появится страх копипаста и он решит представить эти две фигуры в коде или в реляционной БД как одну сущность (один тип данных (класс) в коде ООП или одна таблица реляционной БД) дав ему оба параметра (ширина одной стороны и значение одного из углов) плюс добавив признак квадрат это или ромб. Теперь, для получения площади нашей фигуры в ТД ООП надо добавить условие проверки какую фигуру мы используем и исходя из этого каким способом нам получить ее площадь (в реляционной БД смысл приблизительно такой же, надо добавлять проверки). А потом мы еще вспомним про прямоугольник, он ведь так же является параллелограммом, и нам придется добавлять еще один параметр и еще один признак и еще один условный оператор в методе получения площади фигуры.
Представьте, у нас есть миллиард таких фигур и нам надо получить суммарную их площадь. У каждой фигуры есть метод получения ее площади, нам надо вызвать этот метод миллиард раз. При каждом вызове этого метода условный оператор будет задействован до трех раз, таким образом, для получения площади миллиарда фигур будет вызван условный оператор до трех миллиардов раз. А теперь сравните с другим решением — создаем интерфейс Parallelogram (Параллелограмм) с контрактном (методом) на получения площади этой фигуры и реализуем этот интерфейс для ромба, квадрата и прямоугольника по отдельности. Теперь, при получении площади миллиарда фигур, наш условный оператор не будет задействован ни одного раза, мы просто перебираем все фигуры и у каждой вызываем метод получения ее площади не задумываюсь над тем, что это за фигура. Представляете какую экономию ресурсов вы получите? Да, пускай площадь миллиарда фигур вам никогда не понадобится, но из капли получается река, здесь потеряли ресурсы, в другом месте немного потеряли, в третьем, в итоге приложение будет очень ресурсоемким и дорогим в производительности.
Какие есть требования к ТД:
ВАЖНО: в первую очередь надо бояться непредсказуемого изменения данных, т.е. при использовании в вычислениях данные не должны меняться (требование к ТД №3), если же вы намеренно меняете их, то это изменение предсказуемо и вы можете произвести какие либо действия для получения в дальнейшем корректного результата.
На первый взгляд может показаться что я вступил в противоречие с самим собой — данные должны быть неизменяемыми, изменения данных должны быть предсказуемы. Просто я забегаю немного вперед, предсказуемый результат больше относится ко второй части (управление данными), но как бороться с непредсказуемостью решил описать здесь, т.к. ТД также имеет методы работы со своими данными (полями) и поэтому эти правила распространяются также и на него.
И так, правила для достижения неизменяемости (стабильности) данных:
Никоем образом не хочу сказать, что это все является панацеей, конечно же есть и другие способы решения сложных задач, волшебной таблетки не существует, будьте гибче, применяйте в своей работе разные подходы. Приведу также в пример цитату одной из моих любимых статей на хабре “Топ-11 самых частых ошибок в JavaScript” — ошибка №11: Ты следуешь всем правилам, правила для того, чтобы их ломать, если вы понимаете, почему нельзя использовать тот или иной прием, то он становится инструментом, который вы можете правильно применять в правильной ситуации.
Абстрактный тип данных
Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения — в этом и заключается суть абстракции. Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями. Конкретные реализации АТД называются структурами данных.
В программировании абстрактные типы данных обычно представляются в виде интерфейсов, которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании. Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешнего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надежности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных методов динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Примеры АТД
См. также
Ссылки
Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void
Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism
Полезное
Смотреть что такое «Абстрактный тип данных» в других словарях:
абстрактный тип данных — Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика
Алгебраический тип данных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия
Целое (тип данных) — Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия
Множество (тип данных) — У этого термина существуют и другие значения, см. Множество (значения). Множество тип и структура данных в информатике, является реализацией математического объекта множество. Данные типа множество позволяют хранить ограниченное число значений… … Википедия
Комплексный тип данных — Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия
Указатель (тип данных) — У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия
Обобщённый алгебраический тип данных — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия
Типаж (абстрактный тип) — Типаж (англ. trait) это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ»[1]. Типажи подобны mixins, но могут включать определения методов класса.… … Википедия
Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
Высший тип — (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия
Абстрактный тип данных. Часть 2: Управление данными
В первой части описал чем руководствоваться при определении Типа Данных (далее ТД). В данной части хочу рассказать что такое Абстрактный Тип Данных (далее АТД), как это помогает решать логически сложные задачи (что подразумевается под логически сложными задачами смотрите первую статью) и какие мы получаем преимущества.
Вместо предисловия:
Абстрактный Тип Данных — это набор, включающий данные и выполняемые над ними операции.… Набор данных и методов, служащих одной цели, — это и есть АТД (С. Макконнелл, “Совершенный код”, глава 6.1. Основы классов: абстрактные типы данных). В данном цикле статей рассмотривается именно такой взгляд на АТД, расширенный типом данных.
Торвальдс Линус — «Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях».
Вычисление — это получение из входных данных нового знания.
Действие (формулировка данной статьи) — изменение состояния ТД в процессе вычислений и регистрация данного состояния не меняя при этом самих данных котрые участвуют в вычислениях. Примеры действий вы можете посмотреть в первой части.
Сосотояние характеризуется тем, что описывает переменные свойства объекта. Состояние устойчиво до тех пор, пока над объектом не будет произведено действие. Формальное описание состояний в программировании — набор атрибутов, определяющих поведение объекта.
Теперь к сути
АТД (формулировка данной статьи) — рассматривается как класс содержащий в себе структуры данных с которыми мы работаем в дальнейшем, применяем к ним действие. Под данными подразумеваются наборы ТД которые были рассмотрены в первой части.
Структуры АТД для хранения данных — подразумеваются способы хранения данных, т.е. это может быть и стек, и очередь и любая классическая/неклассическая структура данных которая удобна для работы с ними, зависит от контекста задачи и от вашей фантазии.
Почему такой подход позволяет организовывать сложную логику:
Требования к АТД аналогичны требованиям к ТД, с небольшим дополнением:
Какие преимущества мы получим если придерживаться требований к АТД:
Для описания применимости данного подхода давайте разберем пример который первый пришел мне на ум, игра “Танки”. Никакого отношения к реальной игре “Танки” данный пример отношения не имеет! Пример из своей практики привести не могу т.к. не имею юридического права разглашать данную информацию, скажу только одно, мне приходилось применять данный подход при работе с документами и вычислениях тех или иных показателей в зависимости от полученных данных.
И так, игра “Танки”, что мы имеем:
Полное решение с применением описанного подхода приводить сильно долго, поэтому постараюсь вкратце описать саму концепцию: