Генераторы в программировании: итераторы и эффективное использование памяти
Generator (computer programming)
Генераторы в программировании: эффективные итераторы, экономящие память. Создают последовательность значений "на лету", в отличие от массивов. Оптимизация циклов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В информатике генератор — это подпрограмма, которая может использоваться для управления поведением итерации в цикле. Все генераторы также являются итераторами. Генератор очень похож на функцию, возвращающую массив: у генератора есть параметры, его можно вызвать, и он генерирует последовательность значений. Однако вместо построения массива, содержащего все значения, и возврата их разом, генератор выдает значения по одному, что требует меньше памяти и позволяет вызывающей стороне немедленно начать обработку первых нескольких значений. Короче говоря, генератор выглядит как функция, но ведет себя как итератор. Генераторы могут быть реализованы с использованием более выразительных конструкций управления потоком, таких как корутины или продолжения первого класса. Генераторы, также известные как полукорутины, являются частным случаем (и более слабым вариантом) корутин, поскольку они всегда возвращают управление вызывающей стороне (при передаче значения), а не указывают, к какой корутине следует перейти; см. сравнение корутин и генераторов.
In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator. Generators can be implemented in terms of more expressive control flow constructs, such as coroutines or first class continuations. Generators, also known as semicoroutines, are a special case of (and weaker than) coroutines, in that they always yield control back to the caller (when passing a value back), rather than specifying a coroutine to jump to; see comparison of coroutines with generators.
Применение
Генераторы обычно вызываются внутри циклов. При первом достижении вызова генератора в цикле создается объект итератора, который инкапсулирует состояние процедуры генератора в начале, с аргументами, привязанными к соответствующим параметрам. Затем тело генератора выполняется в контексте этого итератора до тех пор, пока не встретится специальная операция `yield`; в этот момент значение, предоставленное с операцией `yield`, используется как значение выражения вызова. При следующем достижении того же вызова генератора в последующей итерации выполнение тела генератора возобновляется после операции `yield`, пока не встретится очередная операция `yield`. Помимо операции `yield`, выполнение тела генератора также может быть завершено операцией `finish`, при которой завершается ближайший цикл, охватывающий вызов генератора. В более сложных ситуациях генератор может быть использован вручную вне цикла для создания итератора, который затем можно использовать различными способами. Поскольку генераторы вычисляют свои значения только по требованию, они полезны для представления потоков данных, таких как последовательности, которые было бы дорого или невозможно вычислить сразу. К ним относятся, например, бесконечные последовательности и потоки данных в реальном времени. Когда требуется немедленное вычисление (преимущественно, когда последовательность конечна, поскольку в противном случае вычисление никогда не завершится), можно либо преобразовать последовательность в список, либо использовать конструкцию, которая создает список вместо генератора. Например, в Python генератор `g` можно преобразовать в список `l` с помощью `l = list(g)`, а в F# выражение последовательности `seq { }` вычисляется лениво (как генератор или последовательность), но `[ ]` вычисляется немедленно (как список). При наличии генераторов, конструкции циклов языка, такие как `for` и `while`, можно свести к единой конструкции `loop ... end loop`; все обычные конструкции циклов можно затем удобно смоделировать, используя подходящие генераторы. Например, цикл по диапазону, такой как `for x = 1 to 10`, можно реализовать как итерацию через генератор, как в Python: `for x in range(1, 10)`. Кроме того, оператор `break` можно реализовать как отправку сигнала `finish` генератору, а затем использование оператора `continue` в цикле.
Generators are usually invoked inside loops. The first time that a generator invocation is reached in a loop, an iterator object is created that encapsulates the state of the generator routine at its beginning, with arguments bound to the corresponding parameters. The generator's body is then executed in the context of that iterator until a special yield action is encountered; at that time, the value provided with the yield action is used as the value of the invocation expression. The next time the same generator invocation is reached in a subsequent iteration, the execution of the generator's body is resumed after the yield action, until yet another yield action is encountered. In addition to the yield action, execution of the generator body can also be terminated by a finish action, at which time the innermost loop enclosing the generator invocation is terminated. In more complicated situations, a generator may be used manually outside of a loop to create an iterator, which can then be used in various ways. Because generators compute their yielded values only on demand, they are useful for representing streams, such as sequences that would be expensive or impossible to compute at once. These include e. g. infinite sequences and live data streams. When eager evaluation is desirable (primarily when the sequence is finite, as otherwise evaluation will never terminate), one can either convert to a list, or use a parallel construction that creates a list instead of a generator. For example, in Python a generator g can be evaluated to a list l via l = list(g), while in F# the sequence expression seq { } evaluates lazily (a generator or sequence) but [ ] evaluates eagerly (a list). In the presence of generators, loop constructs of a language – such as for and while – can be reduced into a single loop end loop construct; all the usual loop constructs can then be comfortably simulated by using suitable generators in the right way. For example, a ranged loop like for x = 1 to 10 can be implemented as iteration through a generator, as in Python's for x in range(1, 10). Further, break can be implemented as sending finish to the generator and then using continue in the loop.
Хронология
Генераторы впервые появились в CLU (1975), были важной особенностью языка манипулирования строками Icon (1977) и теперь доступны в Python (2001), C#, Ruby, PHP, ECMAScript (начиная с ES6/ES2015) и других языках. В CLU и C# генераторы называются итераторами, а в Ruby – перечислителями.
Generators first appeared in CLU (1975), were a prominent feature in the string manipulation language Icon (1977) and are now available in Python (2001), C#, Ruby, PHP, ECMAScript (as of ES6/ES2015), and other languages. In CLU and C#, generators are called iterators, and in Ruby, enumerators.
Липс
Окончательный стандарт Common Lisp не предусматривает генераторы нативно, однако существует множество библиотечных реализаций, таких как SERIES, описанная в CLtL2, или pygen.
The final Common Lisp standard does not natively provide generators, yet various library implementations exist, such as SERIES documented in CLtL2 or pygen.
С
В C нет генераторных функций как встроенной языковой конструкции, но поскольку они являются подмножеством корутин, их легко реализовать, используя любую библиотеку, поддерживающую корутины с сохранением стека, например, libdill. На платформах POSIX, если стоимость переключения контекста на каждой итерации несущественна или требуется полный параллелизм, а не просто конкурентность, можно реализовать очень простую библиотеку генераторных функций с помощью pthreads и каналов.
C does not have generator functions as a language construct, but, as they are a subset of coroutines, it is simple to implement them using any framework that implements stackful coroutines, such as libdill. On POSIX platforms, when the cost of context switching per iteration is not a concern, or full parallelism rather than merely concurrency is desired, a very simple generator function framework can be implemented using pthreads and pipes.
Python (англ.)
Генераторы были добавлены в Python в версии 2.2 в 2001 году.
Generators were added to Python in version 2.2 in 2001.