Теоретические структуры данных и их применение в JavaScript. Ч1. Пары

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

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

Пара — это структура данных, которая хранит в себе два любых элемента данных, подразумевая, что мы хотим как-то логически объединить их в один. Она решает именно эту задачу, т.е. если некие элементы данных а и b нам нужно представить в виде аb, то мы можем реализовать эту конструкцию на паре.

Если вы думаете, что никогда не сталкивались или не столкнётесь с чем-то подобным, то это не так.

Вот самый простой пример вычисляемого свойства из документации VUE:

var vm = new Vue({
  el: '#demo',
  data: {
    firstName: 'Foo',
    lastName: 'Bar'
  },
  computed: {
    fullName: function () {
      return this.firstName + ' ' + this.lastName
    }
  }
})

С точки зрения теории fullName это пара. И таких примеров бесчисленное множество в технике и реальном мире, который мы зачастую моделируем программным кодом.

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

Теория говорит нам, что пары обладают следующими свойствами:

• имутабельность, т.к. пара это не что-то существующее само по себе, а лишь объединённое представление двух других элементов данных, то менять её крайне нежелательно. Если есть необходимость поменять значение пары, то лучше создать новую(как в функциональном программировании в общем-то и положено. Тему имутабельности мы обсуждали в статье про основные идеи функционального программирования, когда говорили про чистые функции)
• пара должна предоставлять интерфейс для получения элементов из которых она состоит. Этот пункт требует определённых пояснений. Мы создаём пару для логического объединения двух разных единиц данных. Геттеры нужны прежде всего для того, чтобы вызывающий код, который не знает изначальные данные, из которых была создана пара, но знает о паре, мог получить элементы составляющие пару.
  
  Представим псевдокодом пару как объект:
  
  

  pair = { a, b }
  

  
  Если мы в вызывающем коде будем работать с парой напрямую в таком стиле: pair.a, то изменив реализацию пары будем вынуждены переписывать вызывающий код везде, где фигурирует обращение к паре. Это не здорово!
  
  Пара это абстракция(пусть даже низкого уровня), поэтому неправильно было бы работать с её составляющими напрямую. Работая с составными частями любой абстракции, мы должны использовать интерфейс абстракции, иначе код превратится в хаос(сложнее станет его читать, проще допустить ошибку, но самое главное сложнее изменять, т.к. одно изменение придётся вносить в разных частях кода).

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

//тут мы храним исходные значения в замыкании 
//для нас не важен тип входных данных
const pair = (first, second) => (elementType) => {
  switch(elementType) {
    case 'first':
     return first;
   case 'second':
     return second;
  }
};
//у нас есть некий интерфейс, который позволяет нам работать с данными,
// из которых состоит пара
const getFirstElement = (pair) => (pair('first'));
const getSecondElement = (pair) => (pair('second'));

Такой способ работы называется отправкой сообщений. Как ни странно, но именно этот способ взаимодействия сущностей когда-то до С/С++ называли ООП.

Обязательно ли нам использовать конструкцию switch ? Разумеется, необязательно. Это детали технической реализации, а реализаций может быть великое множество!

Самое главное — сделать пару имутабельной!

Например, можно реализовать тот же самый функционал используя Map

//тут мы храним данные в мапе
//несмотря на это, тип исходных данных для нас не важен
const pair = (first, second) => (
  new Map([
    ['first', first],
    ['second', second],
  ])
);
//и снова мы предоставляем интерфейс
const getFirst = (pair) => (pair.get('first'));
const getSecond = (pair) => (pair.get('second'));

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

Кстати, допустим, мы не знаем про существование Мапов в js, но умеем работать с объектами.

//снова для нас не важен тип исходных данных
//снова наша абстракция имутабельна
const pair = (first, second) => (
  Object.freeze({
    'first': first,
    'second': second,
  })
);
//снова у нас есть интерфейс, который позволяет работать с составляющими пару данными
const getFirst = (pair) => (pair.first);
const getSecond = (pair) => (pair.second);

Как легко догадаться обе предыдущие реализации также можно заменить на третью и от этого ничего не поменяется (На самом деле, есть некоторое отличие. Мапы не выбрасывают исключения при попытке изменить свойства напрямую, а «замороженные объекты» бросают TypeError: Cannot assign to read only property. Однако, в контексте статьи это не важно. ).

Для чего знание теоретических структур данных может нам пригодится?

Если мы взглянем на работу программистом с «высоты птичьего полёта», то увидим, что по сути он занимается тем. что создаёт инструменты, которые манипулируют определёнными наборами данных. Следовательно, нам постоянно приходится подбирать для данных какую-то структуру хранения и придумывать способы работы с ними или придавать хаотичному набору данных определённую структуру. Понимание типовых структур данных позволяет нам владеть набором готовых решений для разных типовых задач и просто выбирать наиболее удобный в конкретной задаче способ.

Разберём пример:

«Реализуйте механизм работы с дробями. Дроби должны храниться в обыкновенном формате. т.е. в виде 1/2. Также необходимо реализовать базовые операции(сложение, вычитание, умножение, деление). Необходимо предусмотреть нормализацию.»

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

Материал из википедии говорит нам, что дроби бывают обыкновенные (1/4) и десятичные (0.1). Очевидно, что по условию задачи нам необходимо работать с дробями в обыкновенном формате представления.

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

В коде мы могли бы описать данную структуру так:

//в данном случае для нас важен тип передаваемых данных,
//но мы подразумеваем, что это всегда числа
//в любом случае проверку на тип разумно ставить в вызывающем коде,
// а не в самой абстракции
const makeRational = (num, denom) => (
  new Map([
    ['num', num],
    ['denom', denom],
  ])
);

//как вы помните, нам необходимо реализовать гетеры
//для того чтобы код, который не знает о первоначальных данных, но знает о паре
//мог работать с её составляющими
const getNumer = (rat) => (rat.get('num'));
const getDenom = (rat) => (rat.get('denom'));

Далее нам следует разобрать ситуацию с дробями такого плана 8/4, 6/9. В условии задачи сказано о необходимости предусмотреть нормализацию. Нормализацией дроби называют вынесение из неё наибольшего общего делителя(НОД).

Реализуем функцию для поиска НОДдвух чисел:

//Gcd это абревиатура НОД на английском
const getGcd = (a, b) => ((a % b) ? getGcd(b, a % b) : Math.abs(b));

Если текст функции вам не понятен, то советую почитать про рекурсию.

Чтобы нормализовать дробь нам необходимо разделить её числитель и знаменатель на НОД. Напишем функцию нормализации:

const normalize = (n1, n2) => {
  const commonDivisor = getGcd(n1, n2);
  return [n1 / commonDivisor, n2 / commonDivisor];
};

Логично было бы поместить нормализацию в конструктор makeRational, чтобы всегда нормализовать данные при создании дроби.

const makeRational = (num, denom) => {
  const [normalizeNum, normalizeDenom] = normalize(num, denom);
  return new Map([
    ['num', normalizeNum],
    ['denom', normalizeDenom],
  ]);
};

Далее поработаем над интерфейсом операций.

1) Сложение

Чтобы сложить две обыкновенные дроби, следует привести их к общему знаменателю. Затем сложить числители, а знаменатель оставить без изменений.

//т.к. нормализация у нас заложена в конструктор дроби,
//то первый пункт выполнится в момент конструирования результата,
//нам же остаётся передать в конструктор результат выполнения второго пункта
const add = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2) + getNumer(rat2) * getDenom(rat1),
    getDenom(rat1) * getDenom(rat2),
  ));

2) Вычитание

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

//тут ситуация идентичная со сложением
//первый шаг выполняется при конструировании результата
const sub = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2) - getNumer(rat2) * getDenom(rat1),
    getDenom(rat1) * getDenom(rat2),
  ));

3) Умножение

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

const multi = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getNumer(rat2),
    getDenom(rat1) * getDenom(rat2),
  ));

4) Деление

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

const div = (rat1, rat2) => (
  makeRational(
    getNumer(rat1) * getDenom(rat2),
    getDenom(rat1) * getNumer(rat2),
  ));

Как видите, мы в каждой операции создаём новую сущность. Это следствие правила имутабельности. Замечу, что и в математике операции над числами не меняют исходное число, а создают новое: 1 + 2 = 3.

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

Также немаловажно, чтобы пользователь мог получить свои данные в привычном ему представлении, поэтому введём одну дополнительную функцию.

const ratToString = (rat) => `${getNumer(rat)}/${getDenom(rat)}`;

Приложу листинг тестов:

describe('normalize', () => {
  test('should work', () => {
    expect(normalize(21, 6)).toEqual([7, 2]);
    expect(normalize(2, 3)).toEqual([2, 3]);
  });
});


describe('rational', () => {
  test('getters', () => {
    const rat1 = makeRational(3, 9);
    expect(getNumer(rat1)).toBe(1);
    expect(getDenom(rat1)).toBe(3);

    const rat3 = makeRational(-4, 16);
    expect(getNumer(rat3)).toBe(-1);
    expect(getDenom(rat3)).toBe(4);
  });

  test('add&sub', () => {
    const rat1 = makeRational(3, 9);
    const rat2 = makeRational(10, 3);
    expect(add(rat1, rat2)).toEqual(makeRational(11, 3));
    expect(sub(rat1, rat2)).toEqual(makeRational(-3, 1));

    const rat4 = makeRational(12, 5);
    const rat3 = makeRational(-4, 16);
    expect(add(rat3, rat4)).toEqual(makeRational(43, 20));
    expect(sub(rat3, rat4)).toEqual(makeRational(-53, 20));

    const rat5 = makeRational(1, 15);
    const rat6 = makeRational(4, 25);
    expect(add(rat5, rat6)).toEqual(makeRational(17, 75));
    expect(sub(rat5, rat6)).toEqual(makeRational(-7, 75));
  });

  test('multi&div', () => {
    const rat1 = makeRational(1, 2);
    const rat2 = makeRational(2, 3);
    expect(multi(rat1, rat2)).toEqual(makeRational(2, 6));

    const rat3 = makeRational(1, 3);
    const rat4 = makeRational(1, 2);
    expect(div(rat3, rat4)).toEqual(makeRational(2, 3));
  });

  test('ratToString', () => {
    const rat1 = makeRational(3, 9);
    const rat3 = makeRational(-4, 16);
    expect(ratToString(rat1)).toBe('1/3');
    expect(ratToString(rat3)).toBe('-1/4');
  });
});

Заключение

Текст получился довольно объёмным, но надеюсь, понятным. Подведём итоги:

1. Мы можем использовать структуру данных пара всегда, когда нам надо логически объединить два несвязанных между собой значения
2. Пара должна быть имутабельна
3. Пара должна предоставлять интерфейс для работы со своими составляющими

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

Если статья окажется интересна сообществу. то направление типовых структур данных будет продолжено. Следующая тема — связанные списки.