Генераторы ES6

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

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

Итак, что такое поиск в глубину?
DFS — это алгоритм обхода или поиска в древовидных или графовых структурах данных. Начинают с корня (выбирая какой-нибудь произвольный узел в качестве корня в случае графа) и исследуют как можно дальше каждую ветвь, прежде чем возвращаться назад. (— википедия)

Как это будет выглядеть на практике?

Итак, учитывая приведенное выше определение и наше изображение слева, мы можем лучше понять, как работает DFS. Мы начинаем с самого верхнего узла (в данном случае 1) и двигаемся влево вниз (в этом примере), насколько это возможно (3 в этом примере) и т. д. Но давайте просто запишем последовательность путей: br /> 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7

Это может немного сбивать с толку, но если мы подумаем о том, что мы зайдем так далеко, как сможем, то вернемся назад, а затем возьмем все существующие ветки (выделены жирным шрифтом выше — новые узлы).

Таким образом, мы можем вернуться к ранее посещенным узлам, чтобы затем найти новые узлы.

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

Круто, приступим.

Давайте создадим наш класс Tree. Я дам все это вперед, тогда мы препарируем его.

class Tree {
  constructor(value = null, children = []) {
    this.value = value;
    this.children = children
  }
// Depth First Solution
*printValues() {
  yield this.value;
  for(let child of this.children) {
    yield* child.printValues();
  }
 }
}
// DEPTH first
// See explanations below for a bit more succinct way to 
// generate this tree.
const tree = 
  new Tree(1, [
    new Tree(2, [
       new Tree(5, [
         new Tree(9),
         new Tree(10)
       ]),
       new Tree(6)
     ]),
    new Tree(3),
    new Tree(4, [
       new Tree(7, [
          new Tree(11), 
          new Tree(12)
        ] ), 
        new Tree(8)])
])
const values = []
for(let value of tree.printValues()) {
  values.push(value);
}
values
// our results are:
// [1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12, 8]

Теперь я создал простое/общее дерево классов (имейте в виду, что класс не является обязательным требованием).

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

constructor(value = null, children = []) {
    this.value = value;
    this.children = children
  }

Просто посмотрите на это как на функцию, которая принимает два аргумента, значение и дочерние элементы.
Если мы сравним эту функцию с сигнатурой (т. е. "арность" или "количество аргументов"), она прекрасно сочетается с:

new Tree(5, [new Tree(9),new Tree(10)])
this.value = 5;
this.children = [new Tree(9),new Tree(10)]
As you can see, the children is an array of "Tree's", that have their own "value" and "children".

Давайте перейдем к нашему методу «printValues()», здесь происходит наше волшебство генератора.

*printValues() {
  yield this.value;
for(let child of this.children) {
    yield* child.printValues();
  }
 }

Что мы здесь замечаем? «*»
Что это за чертовщина? Именно так мы обозначаем функцию «генератор», применяя к ней звездочку.

*printValues() {
  yield this.value;
1. yield - The yield keyword is used to pause and resume a generator function.
2. Here we are "yielding" out this.value, for our current 'this' context. If this was the first iteration of our tree: new Tree(1, then our value is 1. Based on our explanation (see #1), at this point we pause. So, we yielded out 1, now what?

Вот наш второй фрагмент кода. Теперь, когда мы сделали паузу после того, как выдали 1. Наша вторая секунда здесь — это резюмеаспект нашего генератора. Мы перейдем к тому, «как» мы возобновим работу, ниже. Но давайте предположим, что сейчас мы вернемся к этой части кода.

for(let child of this.children) {
    yield* child.printValues();
  }
 }
// Here are some other ways to show the data rather than calling 
// 'new Tree' inline everywhere. We can create a helper function
// to recursively go thru everything.
const tree = {
  1: { 
    2: {
       5: {
         9: {},
         10: {},
       6: {}
    },
    3: {},
    4: {
       7: {
         11: {},
         12: {}
        }, 
       8: {}
    }
  }
}
}
const tree = [1,[ 2,[5, [9,10],6,3,4,7,[ 11, 12],8]]]

Упс: не понял, что я не закончил эту историю. :-( , скоро обновлю.