Абстрактный тип данных. Часть 2: Управление данными 0


AliExpress RU&CIS

В первой части описал чем руководствоваться при определении Типа Данных (далее ТД). В данной части хочу рассказать что такое Абстрактный Тип Данных (далее АТД), как это помогает решать логически сложные задачи (что подразумевается под логически сложными задачами смотрите первую статью) и какие мы получаем преимущества.


Вместо предисловия:

Абстрактный Тип Данных — это набор, включающий данные и выполняемые над ними операции (С. Макконнелл, “Совершенный код”, глава 6.1. Основы классов: абстрактные типы данных). В данном цикле статей рассмотривается именно такой взгляд на АТД, расширенный типом данных.

Торвальдс Линус — «Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях».

Вычисление — это получение из входных данных нового знания.

Действие (формулировка данной статьи) — изменение состояния ТД в процессе вычислений и регистрация данного состояния не меняя при этом самих данных котрые участвуют в вычислениях. Примеры действий вы можете посмотреть в первой части.

Сосотояние характеризуется тем, что описывает переменные свойства объекта. Состояние устойчиво до тех пор, пока над объектом не будет произведено действие. Формальное описание состояний в программировании — набор атрибутов, определяющих поведение объекта.


АТД (формулировка данной статьи) — рассматривается как класс содержащий в себе структуры данных с которыми мы работаем в дальнейшем, применяем к ним действие. Под данными подразумеваются наборы ТД которые были рассмотрены в первой части.
Структуры АТД для хранения данных — подразумеваются способы хранения данных, т.е. это может быть и стек, и очередь и любая классическая/неклассическая структура данных которая удобна для работы с ними, зависит от контекста задачи и от вашей фантазии.


Почему такой подход позволяет организовывать сложную логику:

  1. Мы работаем только с данными (ТД) не задумываясь над их получением. Логику получения данных мы возлагаем на “провайдеры данных” (см. ниже). По сути это борьба со сложностью — отдельно думаем над способом получения данных которые всегда имеют определенный тип и отдельно думаем как работать с данными этого типа.
  2. Мы можем организовывать АТД только с нужными нам наборами данных, производя декомпозицию АТД при необходимости (также прием борьбы со сложностью).

Требования к АТД аналогичны требованиям к ТД, с небольшим дополнением:

  1. АТД должен уметь работать только со своими данными.
  2. АТД не должны зависеть от внешнего состояния приложения.
  3. Для того, чтобы получить данные используйте “провайдеры данных” и передавайте их результаты в АТД. Не используйте методы АТД для получения данных (ТД, наборов ТД).

Провайдер данных — подразумевается класс, который получает нужные нам данные из доступных источников, различными способами, и возвращает ТД или наборы ТД. Как именно организовывать провайдеры данных является отдельной темой, зависит от контекста задачи и фантазии разработчика системы.

Какие преимущества мы получим если придерживаться требований к АТД:

  1. Кеширование агрегированных данных — Т.к. ТД у нас не изменяемые и мы имеем полный контроль над данными, а АТД это наборы ТД которые мы храним в удобном для нас виде, по сути АТД хранит агрегированные данные, тогда что нам мешает их кэшировать на какой то момент времени? Зависит конечно от контекста задачи и воли разработчика системы.
  2. Предсказуемость результата — результат у нас всегда будет ожидаемый, т.к. соблюдая данные требования мы получаем аналог чистых функций из ФП.
  3. Более простое, а значит и более надежное, тестирование кода — используя провайдеры данных и не получая данные в АТД мы избавим себя от необходимости создания mock-ов, stub-ов и т.п. при его тестировании, мы просто наполним его тестовыми данными и далее будем тестировать функции методом “черный ящик”, т.е. проверять корректность результата только на выходе.

Для описания применимости данного подхода давайте разберем пример который первый пришел мне на ум, игра “Танки”. Никакого отношения к реальной игре “Танки” данный пример отношения не имеет! Пример из своей практики привести не могу т.к. не имею юридического права разглашать данную информацию, скажу только одно, мне приходилось применять данный подход при работе с документами и вычислениях тех или иных показателей в зависимости от полученных данных.

И так, игра “Танки”, что мы имеем:

  1. Множество танков. Танки могут быть различного типа, с различной скоростью, различной толщиной брони, различным набором орудий, различным объемом боеприпасов, различным количеством человек в экипаже, различной емкостью топливного бака. Толщина брони влияет на стойкость танка к попаданию того или иного типа снаряда. Набор оружия влияет на эффективность танка в том или ином бою. И т.п.
  2. Боеприпасы в свою очередь также могут быть различные, с различной массой, различной бронебойностью, с различным типом поражения (например осколочные или разрывные). Масса боеприпаса влияет на вес танка, вес влияет на скорость хода и дальность хода. Тип поражения влияет на эффективность танка в том или ином бою.
  3. Топливо также может быть различного типа, с различным октановым числом и т.п. что влияет на скорость хода танка и дальность его хода.
  4. Мы имеем людей различного роста и различной массы. От роста зависит поместится человек в определенный танк или нет. От веса также зависит масса танка которая в свою очередь влияет на потребление топлива и скорость хода.
  5. Мы имеем различный рельеф местности на котором происходит бой, где то мы можем бить прямой наводкой, где то нет.

Согласитесь, уже немало параметров и одни параметры могут влиять на параметры других сущностей. А потом мы еще вспомним, что у одного типа танка могут стоять разные типы двигателя, для которых подходит только определенный тип топлива. Что делать, переписывать весь код?

Полное решение с применением описанного подхода приводить сильно долго, поэтому постараюсь вкратце описать саму концепцию:

  1. Определяем типы данных согласно правилам описанным в первой части. В примере с танками это как минимум снаряды, топливо, люди (имена существительные), которые в свою очередь могут различаться по количеству или качеству параметров, т.е. будут различного типа данных.
  2. В АТД управляем данными. Например загружаем в АТД местность на которой происходит бой и танки различного типа с различным набором тех или иных данных. Далее просто управляем данными вызывая те или иные методы, например переместить танк 1 в точку B на нашей местности, или выстрелить из танка 2 в точку C. Соответственно зная скорость перемещения танка, скорость полета снаряда, тип поражения снаряда и т.п. мы можем произвести в АТД вычисления где в момент попадания снаряда выпущенного танком 2 будет находится танк 1 и если снаряд танка 2 попадет в танк 1 какой урон будет ему причинен.

Не претендую на то, что данный подход является лучшим решением, просто решил поделиться своими размышлениями, возможно они кому то помогут в решении своих задач.

Итог:

  1. АТД хранит агрегированные данные в удобном нам виде
  2. АТД должен уметь работать только со своими данными.
  3. АТД не должен зависеть от внешнего состояния приложения.
  4. Для получения данных не используйте методы АТД, для этого используйте “Провайдеры Данных” которые возвращают ТД или наборы ТД. Далее полученные данные мы передаем в АТД для вычислений над ними (придаем/применяем действие к ТД).

Теги:




Комментарии (1):

  1. borshak
    /#21732820

    Отличное введение в АТД (как концепцию информатики) есть в курсе MIT 6.001 SiCP (2-я часть, «Абстракция данных»).

    Подробно о ТД (типах данных) — в книге Бенджамина Пирса «Типы в языках программирования».

    И то, и другое, можно легко найти в виде PDF в великолепном переводе на русский.