Введение
Вы, наверное, сталкивались с этим раньше - вам хотелось сохранить в памяти действительно большой список. После тщательного рассмотрения вы пришли к выводу, что это либо невозможно, поскольку память является ценным и ограниченным ресурсом, либо даже не нужно, поскольку нам нужен только один элемент за раз.
Это когда « Генераторы ».
Что такое генераторы?
Генераторы - это функции, которые создают элементы последовательности, один за другим.
Это дает нам возможность сохранять в памяти только один элемент за раз. Это, конечно, делает нашу программу намного более компактной.
Функции генератора существуют на нескольких популярных языках, включая Javascript, Python, C # и Ruby.
Реализация основана на концепции « Ленивые списки ».
Один из способов представления ленивых списков - это следующее определение:
Ленивый список - это пара текущего элемента (индексированного i) и функции генератора, которая лениво создает остальную часть списка.
Мы можем определить его рекурсивно как -
LazyList(i) = (Element(i), Function(() => LazyList(i+1)))
Предположим, у нас есть бесконечный список целых чисел, скажем, простых чисел - 2, 3, 5, 7, 11…
Эта последовательность целых чисел может быть представлена с помощью ленивого списка как -
LazyListPrime(0) = (2, function() => LazyListPrime(1)) LazyListPrime(1) = (3, function() => LazyListPrime(2)) LazyListPrime(2) = (5, function() => LazyListPrime(3)) LazyListPrime(3) = (7, function() => LazyListPrime(4)) LazyListPrime(4) = (11, function() => LazyListPrime(5))
В целом -
LazyListPrime(i) = (Prime(i), function() => LazyListPrime(i+1))
Где Prime (i) - функция, возвращающая i-е простое число.
Очевидно, что невозможно создать этот список и сохранить его в памяти, так как он бесконечен.
Таким образом, мы могли бы создать этот список с помощью генератора.
Давайте поговорим о технологиях
Языки, которые изначально поддерживают генераторы, используют ключевое слово yield для их реализации.
Такими языками, например, являются Javascript, Python, Ruby и C #.
Общая идея генераторов заключается в том, что состояние выполняющейся функции генератора должны сохраняться между вызовами. В разных языках это реализовано по-разному.
В этой части статьи мы сосредоточимся на генераторах в Node.JS.
Генераторы в Node.JS
Генераторы в Javascript (или Typescript) определяются с помощью function* keyword. Внутри генераторов мы можем приостановить выполнение функции с помощью ключевого слова yield.
Примечание. Функция генератора также может содержать оператор return, который останавливает выполнение функции, как обычная функция.
Продолжим наш пример с простыми числами -
function* primeGenerator() {
for (let num = 2; ; num++) {
if (isPrime(num)) {
yield num;
}
}
}
function isPrime(num) {
for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
Функция primeGenerator - это базовый генератор. Мы знаем это, поскольку объявлено с использованием function*.
Хотя функция-генератор не обязательно должна содержать оператор yield, бессмысленно определять ее как таковую.
Все, что она делает, это перебирает целые числа одно за другим, и если целое число является простым числом, оно возвращает это звонящему.
Чтобы создать экземпляр генератора, мы просто вызываем функцию -
const gen = primeGenerator();
Такой вызов не выполняет функцию, а просто создает объект-генератор. Если бы мы проверили созданный объект, мы бы получили -
gen = primeGenerator {[[GeneratorStatus]]: "suspended"}
__proto__ = Generator
[[GeneratorLocation]] = Object
[[GeneratorStatus]] = "suspended"
[[GeneratorFunction]] = function* primeGenerator() {
[[GeneratorReceiver]] = global
[[Scopes]] = Scopes[3]
Local (primeGenerator) {}
Closure {isPrime: Function}
Global {global: global, ...}
Чтобы вызвать созданный генератор, мы используем gen.next().
При первом вызове gen.next() функция начинает выполнение с первой строки. Любые последующие вызовы gen.next() возобновят выполнение с последней точки, в которой оно было приостановлено.
Попробуем запустить этот код. Если бы мы запустили следующую строку:
console.log(gen.next());
Результатом будет {value: 2, done: false}, где value - текущее сгенерированное простое число, а done - состояние генератора, что означает, что функция может возобновить выполнение в будущем. Объект gen будет выглядеть так -
gen = primeGenerator {[[GeneratorStatus]]: "suspended"}
__proto__ = Generator
[[GeneratorLocation]] = Object
[[GeneratorStatus]] = "suspended"
[[GeneratorFunction]] = function* primeGenerator() {
[[GeneratorReceiver]] = global
[[Scopes]] = Scopes[4]
Block (primeGenerator) {num: 2}
Local (primeGenerator) {}
Closure {isPrime: Function}
Global {global: global, ...}
Если бы мы снова запустили gen.next(), то получили бы {value: 3, done: false}.
Чтобы получить, например, первые 10 простых чисел, мы можем перебрать сгенерированные простые числа. Мы можем использовать синтаксис let...of, поскольку функции генератора повторяются -
let i = 0;
for (let prime of primeGenerator()) {
console.log(prime);
i++;
if (i > 10) {
break;
}
}
Или мы можем использовать базовый цикл for -
const gen = primeGenerator();
for (let i = 0; i < 10; i++) {
console.log(gen.next());
}
Обратите внимание, как определенный выше генератор создает бесконечный список элементов.
Это не обязательно, и функции генератора могут создавать конечное число элементов.
Давайте посмотрим на следующий пример:
function* lettersGenerator() {
const letters = 'abc';
for (let letter of letters) {
yield {letter: letter};
}
}
Когда мы бежим -
const gen = lettersGenerator(); console.log(gen.next()); console.log(gen.next()); console.log(gen.next()); console.log(gen.next());
Первые три вызова gen.next() произведут: {value: {letter: a}, done: false} {value: {letter: b}, done: false} {value: {letter: c}, done: false}
Четвертый (и любой последующий вызов gen.next()) произведет {value: undefined, done: true}, что указывает на то, что генератор исчерпал свои ресурсы и больше не будет производить никаких значений.
Под капотом
Так как же на самом деле генераторы работают в Node.JS?
Как мы знаем, Node.JS использует движок V8 для запуска кода Javascript (как и Chrome). После синтаксического анализа кода V8 использует компилятор для создания байтового кода из кода Javascript, который будет запущен, с именем Ignition.
Как можно увидеть здесь, в функции Parser::ParseAndRewriteGeneratorFunctionBody, когда синтаксический анализатор встречает выражение function*, он анализирует его, как если бы добавление yield выражения добавлялось к началу функции, которая при запуске функции просто немедленно возвращает вызывающей стороне.
Код, переводящий операцию yield в байт-код (исполняемый код), можно найти здесь. ByecodeGenerator::VisitYield - это функция, которая вызывается каждый раз, когда движок встречает ключевое слово yield в коде.
VisitYield вызывается с yield выражением из AST (абстрактного синтаксического дерева). Если это первое yield выражение, которое встретилось, оно просто приостанавливает выполнение функции, не возвращая никакого значения. Если это не первый yield, то также возвращается полученное значение. В обоих случаях VisitYield, в свою очередь, вызывает BuildSuspendPoint, который отвечает за приостановку генератора и передачу результата (если таковой имеется) вызывающей стороне, сохраняя при этом состояние для следующей итерации. BuildSuspendPoint делает это, используя функция SuspendGenerator, которая сохраняет все состояние (регистры, контекст, закрытие, параметры, текущий счетчик приостановки и т. д.) в объекте-генераторе, затем возвращает сгенерированное значение и возвращается вызывающей стороне.
В следующий раз генератор вызывается (с использованием gen.next()), функция BuildSuspendPoint возобновляет выполнение после точки приостановки. Затем он просто вызывает функцию ResumeGenerator, которая отвечает за восстановление состояния (которое было сохранено в объекте-генераторе). После этого он продолжает выполнение с точки, в которой он остановился в VisitYield, а остальная часть функции генератора после yield продолжит работу.
В следующий раз, когда мы снова перейдем к yield выражению, этот цикл повторится.
Расширения
Одна концепция, основанная на генераторах, называется асинхронными генераторами.
Эта концепция существует в JavaScript, Python и C #.
Она очень полезна в случаях потоковой передачи данных, так как получаемые результаты Обещания, которые разрешаются асинхронно.
Мы всегда должны стараться распознавать варианты использования, в которых применимы генераторы. Это может значительно улучшить время выполнения и память нашей программы.
