«В компьютерной науке все проблемы могут быть решены с помощью дополнительного уровня косвенности,» — Дэвид Уилер

Типы данных  — это естественно

Человек — существо с очень развитым образным мышлением. Именно наша способность к созданию абстракций и обобщению прожитого опыта стала ключом к развитию цивилизации. Мы пользуемся этими способностями с самого рождения, даже не задумываясь. Например, мы с детства работаем с различными типами данных, действуя скорее интуитивно, не давая им формального описания. Мы знаем, что числа можно складывать и умножать, а из слов составлять предложения. Вряд ли нам придет в голову попытаться перемножать слова. Таким образом, мы понимаем, когда видим написанные символы (буквы, например), что мы можем и чего не можем делать с этими символами, а так же знаем набор допустимых значений символов — наш алфавит. В нашем примере буквы — и есть тип данных. Мы знаем множество значений букв — они составляют алфавит. Кроме того, знаем, что буквы мы можем составлять в слова — это операции.
Это естественное представление человека легло в основу формального определения типа данных.

Тип данных  — множество значений и [допустимых] операций над этими значениями.

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

Представьте себе такой диалог матери и маленького сына лет трех, который еще не очень освоил абстрактное мышление:

— Сынок, принеси, пожалуйста, со стола ручку, мне надо записать кое‑что!

— Мама, тут нет ручки!

— Тогда карандаш.

— И карандаша нет.

— А что есть?

— Фломастеры есть и маркер.

— Ну, тогда неси фломастер!

Взрослый человек скорее всего сразу бы принес фломастер и сказал: «ручки не было, думаю, фломастер сгодится». Почему? — Потому что с какого‑то уровня развития абстрактного мышления и умения взаимодействовать с другими людьми, человек уже понимает, что в этой просьбе главное не конкретный тип объекта — ручка — а ее свойство писать по бумаге. Таким же свойством обладают и другие объекты: карандаши, фломастеры, маркеры, даже кусочек угля. Таким образом, он машинально объединяет несколько типов инструментов в один тип: «то, чем можно писать». Это умение часто упрощает нам повседневную жизнь и общение с окружающими, при этом несколько отдаляя нас от конкретных физических объектов. Чтобы добраться до работы, мы используем «общественный транспорт» — маршруты и конкретные вагоны или машины могут быть разными, но главное, что они обладают нужными нам свойствами: мы можем войти, выйти, оплатить проезд, мы заранее уверены в том, что это можно сделать с каждым из объектов этого типа. Когда мы в незнакомом городе хотим сходить в кафе, мы спрашиваем у друзей или в интернете: «где в городе Н можно вкусно поесть?», — то есть мы не определяем конкретное заведение, даже его тип, а ставим во главу угла самое важное свойство группы заведений: мы можем прийти туда и заказать еду.

Иными словами, в некоторых ситуациях нам важен не объект конкретного типа, а какие‑то определенные его свойства: то есть, что именно мы можем с ним делать. Часто искомыми свойствами обладают несколько типов данных, и все они нам так или иначе подойдут, как в описанных выше примерах. Это подводит нас к определению абстрактного типа данных. Сначала приведем формальное определение, а затем раскроем его в более простых терминах.

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

Что такое математическая модель? Кто такой пользователь данных? Что имеется в виду под поведением операций? Зачем вообще все так усложнять? Давайте разбираться.

Углубляемся в детали и разбираем примеры

Чтобы не перегружать себя новой информацией, давайте будем под математической моделью объекта или явления понимать просто формальное его описание. Возвращаясь к примеру с мамой, которой понадобилась ручка, мы можем переделать ее просьбу следующим образом: «Сын, принеси мне, пожалуйста, какой‑нибудь инструмент, который может оставлять контрастные следы на бумаге и при этом помещается ко мне в руку». Звучит на бытовом уровне достаточно абсурдно, но именно это и будет являться формальным описанием того, что понадобилось маме.

Двигаемся дальше. Представим себе программиста, перед которым стоит задача создания системы электронной очереди в травмпункте.

При поступлении в травмпункт человеку выдается талон с номером (порядковым номером посетителя травмпункта) и определяется приоритетность очереди: его травма оценивается по шкале от 1 до 10, где 10 — травма, требующая немедленной медицинской помощи. Необходимо реализовать механизм добавления человека в очередь и определения следующего пациента на прием.

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

Под пользователем данных мы в этой статье будем понимать программиста, который использует эти типы данных в своем коде.

Остается самый важный вопрос: зачем все это нужно? Чтобы ответить на него, давайте рассмотрим задачу подробнее.

Представим, что в очереди уже есть талоны с номерами 109, 101, 105, 112 с приоритетами 5, 3, 1, 1 соответственно. Следующему пациенту выдается талон 113 с приоритетом 3. Тогда этот талон «обходит» номера 105 и 112, потому что их приоритет ниже, и встает позади талона 101, с которым их приоритеты равны (рис. 1). Когда врач готов принять следующего пациента, то вызван будет пациент с номером 109 (рис. 2).

Давайте напишем код, реализующий эту логику. Будем использовать язык javascript. Сначала опишем обычную очередь, без учета приоритета. Создадим класс PriorityQueue. Объекты этого класса будут содержать изначально пустой массив data (создается в конструкторе). Функция add_elem будет добавлять переданный ей параметр — номер талона — в конец массива data, а функция get_next будет описывать вызов врачом пациента на прием: возвращать значение первого элемента в массиве — номер пациента, который встал в очередь раньше всех остальных, удаляя из массива этот элемент, так как, отправляясь на прием, пациент покидает очередь. Также определим функцию print_queue, которая будет выводить в консоль все элементы очереди по порядку.

class PriorityQueue{  
  
  constructor(){ this.data = []; }

  add_elem(e){ this.data.push(e); }

  get_next() { return this.data.shift() }

  print_queue() {
      for(var i in this.data)	
          console.log(this.data[i]);  
  }
};

Приведем пример использования этого класса в коде программы:

Q = new PriorityQueue();
Q.add_elem(105);
Q.add_elem(101);
Q.add_elem(109);

console.log("next:",Q.get_next()) // next: 105
console.log("remains:") 
Q.print_queue(); // 101 109

Давайте модифицируем получившийся класс, чтобы очередь учитывала приоритет элемента. Для этого будем в массиве data хранить не просто переданный элемент, а объект с двумя полями: значение (value) и приоритет (priority). В коде такой объект будет задаваться выражением вида var obj = {‘priority’: 1, ‘value’: 112}; Перепишем функцию добавления элемента в очередь:

//теперь функция принимает два аргумента: значение и приоритет
add_elem(e,p)  {		
  //просматриваем очередь с конца       
  for (var i = this.data.length - 1; i >= 0; i--) {		
    // как только нашли элемент с равным или большим приоритетом 
    if(this.data[i].priority >= p){                
      //вставляем новый элемент позади найденного		     
      this.data.splice(i+1,0,{'value':e, 'priority':p});                
      return; //выходим из функции, добавление завершено            
    }     
  }

  //если более приоритетных (или равных) элементов в очереди нет,	
  //то новый элемент становиться первым в очереди.      
  this.data.splice(0,0,{'value':e, 'priority':p});  
}

Смоделируем ситуацию, проиллюстрированную на рисунках 1 и 2.

Q = new PriorityQueue();
Q.add_elem(109,5);
Q.add_elem(101,3);
Q.add_elem(105,1);
Q.add_elem(112,1);
Q.add_elem(113,3);

console.log("next:",Q.get_next()) // next: { value: 109, priority: 5 }
console.log("remains:")
Q.print_queue(); // value: 101, priority: 3 }
                 //{ value: 113, priority: 3 }
                 //{ value: 105, priority: 1 }
                 //{ value: 112, priority: 1 }

Возможная модификация: если пациент находится в очереди в течение долгого времени, например, за это время доктор уже принял как минимум одного пациента из очереди, то приоритет его талона повышается на 1, однако, не может превзойти 8, чтобы оставить возможность срочного приёма тяжёлых больных

Для этого изменим функцию выбора следующего элемента get_next.

get_next() {       	
  var e = this.data.shift();	
  for(var i in this.data){ 
    //для всех оставшихся в очереди элементов		
    if(this.data[i].priority<8) //если они еще не достигли максимума
      this.data[i].priority++; //увеличиваем приоритет на 1	
  }	
  return e; 
}

Можем заметить, что в данном случае при изъятии элемента из очереди, изменяются все ее элементы. Это и будет то самое «поведение операции», о котором говорилось ранее.

Получившийся код программы можно условно разделить на две части: описание класса PriorityQueue и использование этого класса. Заметим, что использование класса выглядит достаточно лаконично по сравнению с его описанием. При работе с классом и его функциями программист, который выступает в данном случае как пользователь класса, может не иметь представления, как именно реализована логика работы внутри функций класса. Для его работы достаточно того, что эта логика соответствует заявленному описанию работы приоритетной очереди. В таком случае говорят, что класс реализует определенный интерфейс — набор методов работы с классом, где зафиксированы входные и выходные параметры. В данном примере это методы add_elem, get_next и print_queue. Можно поменять внутреннюю логику работы этих методов, если того потребует задача, как это было в случае с повышением приоритета при долгом ожидании. Однако для пользователя класса эти изменения не будут заметны и не потребуют изменения кода основной программы.

Бонус. Что такое структура данных?

В программировании также есть понятие структуры данных, которое в некотором роде близко по смыслу типу данных.

В чем же разница? Структура данных — это конкретная программная реализация типа данных. Если двух людей попросить реализовать приоритетную очередь, скорее всего даже при использовании одного языка программированиях их реализации будут отличаться, хотя обе будут соответствовать заявленному интерфейсу. То есть они создадут две разных структуры данных.

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Заключение

Подведем итоги проделанной работы. Класс PriorityQueue обладает следующими свойствами:

1. Он может хранить в себе любые элементы с приоритетом, который задается числом.

2. Определен интерфейс взаимодействия с классом: методы add_elem, get_next и print_queue.

3. Описанные методы реализуют заявленную логику работы приоритетной очереди.

4. Методы обладают определенным поведением (см., например, бонус).

Таким образом, мы создали свой абстрактный тип данных и реализовали его на языке javascript. Что мы от этого выиграли:

1. Код основной программы лаконичен и понятен, так как не содержит «технических» подробностей внутренней работы очереди.

2. Удобно вносить изменения в логику работы очереди, не затрагивая основной код.

3. Класс PriorityQueue может быть переиспользован в других программах, где требуется похожая логика.

4. В случае командной работы можно разделить между людьми работу над классом и разработку с использованием этого класса. Связующим звеном будет являться интерфейс класса.

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

Кончено, АТД — это не панацея, которая поможет сделать любой код прекрасным, читаемым и понятным, избежав всех ошибок. Очень часто даже опытные программисты в своем стремлении сделать все правильно и красиво заходят слишком далеко в дебри абстракций, что наоборот все усложняет. Когда стоит создавать новую абстракцию, а когда это лишнее, понять можно только с опытом. Универсального рецепта нет, можно лишь посоветовать стараться периодически пересматривать свой старый код, чтобы сделать выводы, что из написанного делает его понятнее, а что по прошествии некоторого времени непонятно уже даже вам самим.

Помните, что у высказывания Дэвида Уиллера и есть и вторая, менее известная, часть:

В компьютерной науке все проблемы могут быть решены с помощью дополнительного уровня косвенности. Но как правило это создаёт другую проблему