Дни 1–2,5 в программе удаленного погружения Fullstack Academy

В первые два с половиной дня младшего этапа Fullstack мы создали игру с командной строкой «Создай свое собственное приключение», где пользователь мог выбрать один из нескольких вариантов, и игра изменялась в зависимости от выбранной опции. Затем мы сразу перешли к абстрактным типам данных и структурам данных.

Абстрактный тип данных - это описание информации, то, как эта информация связана, и выполняемые операции с этой информацией. Если вы думаете, что это немного расплывчато, то потому, что это так. Несколько (чуть более) конкретных примеров абстрактных типов данных - это списки, которые представляют собой упорядоченные коллекции элементов, и словари, которые представляют собой наборы пар ключ-значение.

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

В классе мы сосредоточились на двух структурах данных, очереди и связанном списке. Затем мы реализовали два абстрактных типа данных: двоичное дерево поиска и хеш-таблицу.

Очереди

Очередь, как ее удачно назвали, можно представить как очередь людей (или, для нас, американцев, очередь). У них есть передняя и задняя части. Вы можете добавить (поставить в очередь) только сзади, и вы можете удалить (удалить из очереди) только спереди. У очередей нет индексов, поэтому вы не можете получить доступ к элементам таким образом, но элементы сортируются по порядку вставки. Очереди работают по принципу «первым пришел - первым ушел» - то есть первое, что добавляется, будет первым, что будет удалено.

Мы реализовали очередь, используя простой массив с возможностью добавления элемента в очередь, удаления элемента из очереди и определения размера очереди. Нам было категорически запрещено использовать какие-либо методы Array.prototype (включая, помимо прочего, .push, .shift, .length и т. Д.). Вместо этого нам было приказано использовать индексы head и tail.

Наше решение было относительно простым. Мы создали конструктор Queue и поместили в него свойства array, head и tail. Мы поместили методы enqueue, dequeue и size в прототип Queue. Мы использовали хвостовой индекс нашего созданного массива, чтобы добавить элемент в нашу очередь, а затем увеличили хвостовой индекс на единицу, чтобы любой элемент, который мы добавили после, был помещен после. Мы сделали нечто подобное в нашем методе удаления из очереди - мы вернули индекс заголовка массива и увеличили индекс заголовка на единицу.

Затем, чтобы найти размер, мы вычли индекс хвоста из индекса головы. Мы столкнулись с небольшой проблемой при попытке справиться с недостаточным переполнением - то есть не допустить, чтобы индекс заголовка был больше, чем индекс хвоста, и в этом случае размер становится отрицательным. Простая инструкция if, которая возвращала undefined в методе dequeue, исправила это, и все!

Связанные списки

Далее мы создали связанный список. Связанный список выглядит так:

Каждый узел состоит из двух частей: где фактически хранятся данные, и ссылки на то, где хранится следующий узел (node.next). Связанные списки также могут быть двунаправленными и иметь третью часть: ссылку на то, где хранится предыдущий узел.

Связанные списки предпочтительнее других методов хранения, таких как массивы, когда:

  • Вам нужно вставлять / удалять элементы в середине или в начале - массивы должны полностью сдвинуть «остальные» элементы при вставке или удалении.
  • Вам нужен гибкий способ хранения данных. Массивы имеют фиксированную длину, и их расширение может означать копирование в другое место в памяти. (Примечание: массивы в JavaScript не являются «настоящими» массивами, поэтому это не вызывает беспокойства, но это утверждение верно для многих других языков.)

Чтобы создать связанный список, мы создали две функции-конструктора: LinkedList, который был пустым, но необходим, чтобы мы могли размещать методы в прототипе, и Node, который представлял каждый «элемент» в связанном списке. Наш был двунаправленным, поэтому конструктор узла имел свойство value, свойство previous и свойство next.

Чтобы добавить узел к хвосту, мы создали новый экземпляр узла. Если хвост уже существует в нашем списке, мы бы назначили этот новый узел свойству .next текущего хвоста. Если хвост еще не существует, мы бы назначили свойства head и tail новому узлу. (Потому что, если хвоста еще нет, значит и головы нет.)

LinkedList.prototype.addToTail = function(value) {
  var newNode = new Node(value, this.tail);
  if (this.tail) {
    this.tail.next = newNode;
  } else {
    this.head = newNode;
  }
  this.tail = newNode;
};

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

Чтобы удалить узел из головы, мы сначала проверили, существует ли свойство head - если нет, вернем undefined. Если это так, то мы сохранили значение головы в переменной и установили значение головы равным следующей. Если следующее свойство head (которое теперь является текущим свойством head) существовало, мы устанавливаем предыдущий заголовок равным нулю. (Если бы мы действительно удалили голову, то после ее удаления на ее месте не было бы ничего.) Если следующее свойство head не существует, это означает, что мы только что удалили последний элемент в нашем списке, и ничего не было left в нашем связанном списке, поэтому мы устанавливаем для свойства tail значение null. Затем мы вернули переменную нашей исходной головы.

LinkedList.prototype.removeHead = function() {
  if (!this.head) return;
  var oldHead = this.head.value;
  this.head = this.head.next;
  if (this.head) {
    this.head.previous = null;
  } else {
    this.tail = null;
  }
  return oldHead;
};

Деревья двоичного поиска

Деревья двоичного поиска выглядят так:

Вы начинаете с корневого узла наверху, который представляет собой некоторую ценность. Затем, когда вы добавляете узел, если он меньше родительского узла, он перемещается влево. Если больше, то вправо. Итак, в нашем примере выше, если мы используем 3 в качестве родительского узла и хотим добавить число 6, оно переместится вправо от 3, потому что оно больше.

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

Чтобы найти какой-либо узел в приведенном выше дереве, вам нужно просмотреть максимум 6 раз!

Мы реализовали двоичное дерево поиска со связанным списком. Мы начали с конструктора BinarySearchTree, у которого были свойства для значения, левого узла (this.left), правого узла (this.right) и this.length, который мы изначально установили на 1 как количество узлов в дерево.

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

BinarySearchTree.prototype.insert = function(value) {
 if (value < this.value) {
  if (this.left === null) {
   this.left = new BinarySearchTree(value);
   this.length++;
  } else {
   this.left.insert(value);
  }
 } else {
  if (this.right === null) {
   this.right = new BinarySearchTree(value);
   this.length++;
  } else {
   this.right.insert(value);
  }
 }
};

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

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

Наш код изначально выглядел так:

BinarySearchTree.prototype.contains = function(value) {
  if (value === this.value){ 
    return true;
  } else {
    if (value < this.value) {
      if (this.left === null) {
        return false;
      }
      this.left.contains(value);
    } else {
      if (this.right === null) {
        return false;
      }
      this.right.contains(value);
    }
  }
  return false;
};

Вы видите проблему в этом коде? Когда мы запускали его с числами, которые, как мы знали, были в наборе, мы всегда получали ложь. Когда мы изменили «return false» на «return« foo », мы получили бы foo. Итак, нам нужно было выяснить, почему наша функция, похоже, полностью игнорирует все, что в ней было.

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

Если у нас есть простое дерево, которое выглядит так:

 1 <=a
2 3 <= b, c

Где 1, 2 и 3 - значения каждого узла, а a, b и c - имена каждого узла. Если мы пытаемся найти число «3» и вызываем a.contains (3), программа сначала проверяет, было ли оно 3. Это не так, а 3 больше 1, поэтому проверить c. c.contains (3) IS 3, поэтому он вернет true - за исключением того, что мы никогда не возвращали это значение, поэтому программа переходит непосредственно к нижней части и вместо этого возвращает a.contains (3) (что неверно!).

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

BinarySearchTree.prototype.contains = function(value) {
  if (value === this.value){ 
    return true;
  } else {
    if (value < this.value) {
      if (this.left === null) {
        return false;
      }
      return this.left.contains(value);
    } else {
      if (this.right === null) {
        return false;
      }
      return this.right.contains(value);
    }
  }
  return false;
};

Вот и снова наше дерево. Мы воспользуемся этим через секунду.

Бинарное дерево можно искать одним из двух основных способов. Первый - в ширину, когда вы начинаете с первого уровня, затем просматриваете все узлы на уровне ниже, затем все узлы на уровне ниже и т. Д. Это полезно, когда уровень дерева имеет некоторое значение (например, иерархическая организационная диаграмма), но менее полезен для деревьев двоичного поиска. В нашем дереве выше мы получили значения в следующем порядке: 8, 3, 10, 1, 6, 14, 4, 7, 13.

Мы могли бы выполнить поиск в ширину одним из двух способов: итеративно или рекурсивно. Было ли это из-за того, что мы устали от рекурсии на этом этапе или просто не думали делать это рекурсивно (подсказка - это последнее), мы сделали это итеративно с очередью.

Наша функция-итератор принимает значение, возвращаемое функцией widththFirstForEach, и помещает его в массив.

BinarySearchTree.prototype.breadthFirstForEach = function(iterator, queue) {
  queue = queue || [this];
  var tree;
  tree = queue.shift();
  if (!tree) {
    return undefined;
  }
  iterator(tree.value);
  if (tree.left) {
    queue.push(tree.left);
  }
  if (tree.right) {
    queue.push(tree.right);
  }
  return tree.breadthFirstForEach(iterator, queue);
};

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

Другой основной способ поиска в двоичном дереве - сначала в глубину, когда вы спускаетесь до определенных точек остановки, прежде чем перейти к следующей ветви. Существуют три типа поиска в глубину:

  • Предварительный заказ: обработайте текущее значение узла, затем перейдите по левой ветви вниз, затем по правой ветви. Наиболее полезно при копировании дерева. В нашем дереве выше мы получили значения в следующем порядке: 8, 3, 1, 6, 4, 7, 10, 14, 13.
  • По порядку: обрабатываются все левые дочерние элементы, затем значение этого узла, затем правые дочерние элементы. Это наиболее полезно для двоичного дерева поиска, поскольку значения обрабатываются от наименьшего к наибольшему. В нашем дереве выше мы получили значения в следующем порядке: 1, 3, 4, 6, 7, 8, 10, 13, 14.
  • Пост-заказ: обрабатываются все левые дочерние элементы, затем правые дочерние элементы, а затем значение этого узла. Это наиболее полезно для безопасного удаления узлов, поскольку вы удалили дочерние узлы перед удалением узлов над ними. В нашем дереве выше мы получили значения в следующем порядке: 1, 4, 7, 6, 3, 13, 14, 10, 8.

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

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

BinarySearchTree.prototype.depthFirstForEach = function(iterator, order) {
  if (order === 'pre-order') {
    iterator(this.value);
  }
  if (this.left) {
    this.left.depthFirstForEach(iterator, order);
  }
  if (!order || order === 'in-order') {
    iterator(this.value);
  }
  if (this.right) {
    this.right.depthFirstForEach(iterator, order);
  }
  if (order === 'post-order') {
    iterator(this.value);
  }
};

По сути, большая часть структуры этих трех элементов похожа, поэтому мы можем объединить их в одну функцию. Единственная разница заключается в порядке, в котором обрабатывается центральный «родительский» узел: в предварительном порядке он первый, в порядке очереди - между левым и правым, а в последующем - последний. Мы рекурсивно проходим каждую левую и правую ветвь, чтобы убедиться, что мы получили каждый узел.

Хеш-таблицы и прочее

Мы также говорили о хэш-таблицах, и наша последняя проблема в этом наборе заключалась в их реализации. Мы с напарником не успели так далеко за то время, которое у нас было. Существует также невероятно большое количество других абстрактных типов данных и структур данных - таких как графики, красно-черные деревья, круговые буферы, кучи и т. Д. Список можно продолжить. Я определенно заинтересован в том, чтобы заниматься этим в свободное время (то немногое, что существует в настоящее время), и я отчитаюсь!