En informática , un generador es una rutina que se puede utilizar para controlar el comportamiento de iteración de un bucle . Todos los generadores también son iteradores . [1] Un generador es muy similar a una función que devuelve una matriz , en el sentido de que un generador tiene parámetros , se puede llamar y genera una secuencia de valores. Sin embargo, en lugar de crear una matriz que contenga todos los valores y devolverlos todos a la vez, un generador genera los valores uno a la vez, lo que requiere menos memoria y permite a la persona que llama comenzar a procesar los primeros valores inmediatamente. En resumen, un generador parece una función pero se comporta como un iterador .
Los generadores se pueden implementar en términos de construcciones de flujo de control más expresivas , como corrutinas o continuaciones de primera clase . [2] Los generadores, también conocidos como semicorutinas, [3] son un caso especial (y más débiles) de corrutinas, ya que siempre devuelven el control a la persona que llama (al devolver un valor), en lugar de especificar una corrutina para saltar. a; ver comparación de corrutinas con generadores .
Los generadores normalmente se invocan dentro de bucles. [4] La primera vez que se alcanza una invocación de generador en un bucle, se crea un objeto iterador que encapsula el estado de la rutina del generador en su inicio, con argumentos vinculados a los parámetros correspondientes . Luego, el cuerpo del generador se ejecuta en el contexto de ese iterador hasta que se encuentra una acción de rendimiento especial; en ese momento, el valor proporcionado con la acción de rendimiento se utiliza como valor de la expresión de invocación. La próxima vez que se alcance la misma invocación del generador en una iteración posterior, la ejecución del cuerpo del generador se reanuda después de la acción de rendimiento , hasta que se encuentre otra acción de rendimiento . Además de la acción de ceder , la ejecución del cuerpo del generador también puede terminar mediante una acción de finalización , en cuyo momento finaliza el bucle más interno que encierra la invocación del generador. En situaciones más complicadas, se puede usar un generador manualmente fuera de un bucle para crear un iterador, que luego se puede usar de varias maneras.
Debido a que los generadores calculan los valores obtenidos solo según demanda, son útiles para representar flujos , como secuencias que serían costosas o imposibles de calcular a la vez. Estos incluyen, por ejemplo, secuencias infinitas y flujos de datos en vivo.
Cuando es deseable una evaluación entusiasta (principalmente cuando la secuencia es finita, ya que de lo contrario la evaluación nunca terminará), se puede convertir a una lista o usar una construcción paralela que cree una lista en lugar de un generador. Por ejemplo, en Python un generador gse puede evaluar en una lista lmediante l = list(g), mientras que en F# la expresión de secuencia seq { ... }se evalúa con pereza (un generador o secuencia) pero [ ... ]se evalúa con entusiasmo (una lista).
En presencia de generadores, las construcciones de bucle de un lenguaje, como for y while, se pueden reducir a una sola construcción de bucle... finalizar bucle; Luego, todas las construcciones de bucle habituales se pueden simular cómodamente utilizando generadores adecuados de la manera correcta. Por ejemplo, un bucle a distancia como for x = 1 to 10se puede implementar como iteración a través de un generador, como en Python for x in range(1, 10). Además, breakse puede implementar enviando el fin al generador y luego usándolo continueen el bucle.
Los generadores aparecieron por primera vez en CLU (1975), [5] fueron una característica destacada en el lenguaje de manipulación de cadenas Icon (1977) y ahora están disponibles en Python (2001), [6] C# , [7] Ruby , PHP , [8] ECMAScript (a partir de ES6/ES2015 ) y otros lenguajes. En CLU y C#, los generadores se denominan iteradores y en Ruby, enumeradores .
El estándar final Common Lisp no proporciona generadores de forma nativa, sin embargo, existen varias implementaciones de biblioteca, como SERIES documentada en CLtL2 o pygen.
Se utiliza una declaración de rendimiento para implementar iteradores sobre abstracciones de datos definidas por el usuario. [9]
string_chars = iter (s: cadena) produce (char); índice: int := 1; límite: int := cadena$tamaño (s); mientras que el índice <= límite lo hace rendimiento (cadena$fetch(s, índice)); índice := índice + 1; fin;finalizar string_chars;para c: char en string_chars(s) hacer ...fin;Cada expresión (incluidos los bucles) es un generador. El lenguaje tiene muchos generadores incorporados e incluso implementa parte de la semántica lógica utilizando el mecanismo generador ( la disyunción lógica u "OR" se realiza de esta manera).
Se puede imprimir cuadrados del 0 al 20 usando una co-rutina escribiendo:
Sin embargo, la mayoría de las veces los generadores personalizados se implementan con la palabra clave "suspender" que funciona exactamente igual que la palabra clave "rendimiento" en CLU.
C no tiene funciones generadoras como construcción de lenguaje, pero, como son un subconjunto de corrutinas , es sencillo implementarlas usando cualquier marco que implemente corrutinas apilables, como libdill. [10] En plataformas POSIX, cuando el costo del cambio de contexto por iteración no es una preocupación, o se desea un paralelismo total en lugar de simplemente concurrencia , se puede implementar un marco de función de generador muy simple utilizando pthreads y pipes .
Es posible introducir generadores en C++ utilizando macros de preprocesador. El código resultante puede tener aspectos muy diferentes del C++ nativo, pero la sintaxis del generador puede ser muy ordenada. [11] El conjunto de macros de preprocesador definido en esta fuente permite generadores definidos con la sintaxis como en el siguiente ejemplo:
$generador ( descenso ) { int i ; // coloca el constructor de nuestro generador, por ejemplo // descent(int minv, int maxv) {...} // de $emit a $stop es un cuerpo de nuestro generador: $emit ( int ) // emitirá int valores. Arranque del cuerpo del generador. para ( i = 10 ; i > 0 ; - i ) $rendimiento ( i ); // similar al rendimiento en Python, // devuelve el siguiente número en [1..10], al revés. $parar ; // detener, fin de secuencia. Extremo del cuerpo del generador. }; Luego, esto se puede iterar usando:
int main ( int argc , char * argv []) { descenso gen ; for ( int n ; gen ( n );) // "obtener la siguiente" invocación del generador printf ( "el siguiente número es %d \n " , n ); devolver 0 ; } Además, C++ 11 permite aplicar bucles foreachbegin a cualquier clase que proporcione las funciones y end. Entonces es posible escribir clases tipo generador definiendo tanto los métodos iterables ( beginy end) como los métodos iteradores ( operator!=, operator++y operator*) en la misma clase. Por ejemplo, es posible escribir el siguiente programa:
#include <iostream> int main () { for ( int i : rango ( 10 )) { std :: cout << i << std :: endl ; } devolver 0 ; } Una implementación de rango básico se vería así:
rango de clase { privado : int último ; iterar ; público : rango ( int fin ) : último ( fin ), iter ( 0 ) {} // Funciones iterables rango constante & comenzar () const { retorno * esto ; } rango constante y fin () const { retorno * esto ; } // Funciones iteradoras operador bool != ( rango constante & ) const { retorno iter < último ; } operador nulo ++ () { ++ iter ; } int operador * () const { return iter ; } }; Perl no proporciona generadores de forma nativa, pero el módulo Coro::Generator proporciona soporte y utiliza el marco de co-rutina Coro. Uso de ejemplo:
utilizar estricto ; utilizar advertencias ; # Habilitar generador { BLOCK } y producir uso Coro::Generator ; # Referencia de matriz para iterar sobre mis $chars = [ 'A' ... 'Z' ]; # Nuevo generador que se puede llamar como coderef. mis $letras = generador { mi $i = 0 ; para mi $carta ( @$chars ) { # obtener la siguiente letra de $chars produce $carta ; } }; # Llame al generador 15 veces. imprimir $letras -> (), "\n" para ( 0 .. 15 ); El ejemplo paralelo a Icon utiliza la clase Range Raku (anteriormente también conocida como Perl 6) como una de varias formas de lograr generadores con el lenguaje.
La impresión de cuadrados del 0 al 20 se puede lograr escribiendo:
para ( 0 .. *). mapa (* ** 2 ) -> $i { último si $i > 20 ; decir $yo}Sin embargo, la mayoría de las veces los generadores personalizados se implementan con palabras clave "reunir" y "tomar" en un contexto vago.
En Tcl 8.6, el mecanismo generador se basa en corrutinas con nombre .
proc generador { body } { coroutine gen [ incr :: desambiguator ] apply {{ script } { # Produce el resultado de [generator], el nombre del generador yield [ info coroutine ] # Realiza la generación eval $script # Termina el ciclo de la persona que llama usando un retorno de excepción 'interrupción' - interrupción de código }} $body } # Utilice un bucle 'for' simple para realizar el recuento del conjunto de generación real [ generador { for {set i 10 } { $i <= 20 } { incr i } { yield $i } }] # Extrae valores del generador hasta que se agota mientras 1 { pone [ $count ] } En Haskell , con su modelo de evaluación diferido , cada dato creado con un constructor de datos no estricto se genera bajo demanda. Por ejemplo,
contarDesde :: Entero -> [ Entero ] contarDesde n = n : contarDesde ( n + 1 ) de 10 a 20 :: [ Entero ] de 10 a 20 = tomar mientras ( <= 20 ) $ contar desde 10 números primos :: [ Entero ] números primos = 2 : 3 : siguientePrimo 5 donde siguientePrimo n | noDivisible n = n : siguientePrimo ( n + 2 ) | de lo contrario = nextPrime ( n + 2 ) notDivisible n = all (( /= 0 ) . ( rem n )) $ takeWhile (( <= n ) . ( ^ 2 )) $ primos de cola donde (:)es un constructor de listas no estricto, cons , y $es simplemente un operador "llamado con" , usado para el uso de paréntesis. Esto utiliza la función de adaptador estándar,
tomarMientras p [] = [] tomarMientras p ( x : xs ) | p x = x : tomarMientras p xs | de lo contrario = [] que recorre la lista y se detiene en el primer elemento que no satisface el predicado. Si la lista se ha recorrido antes hasta ese momento, es solo una estructura de datos estricta, pero si alguna parte no se ha recorrido antes, se generará a pedido. Las listas por comprensión se pueden utilizar libremente:
cuadradosUnder20 = tomarMientras ( <= 20 ) [ x * x | x <- countFrom 10 ] cuadradosParaNúmerosUnder20 = [ x * x | x <- takeWhile ( <= 20 ) $ countFrom 10 ] Racket proporciona varias instalaciones relacionadas para generadores. Primero, sus formas de bucle for funcionan con secuencias , que son una especie de productor:
( para ([ i ( dentro del rango 10 20 )]) ( printf "i = ~s \n " i )) y estas secuencias también son valores de primera clase:
( define 10 a 20 ( dentro del rango 10 20 )) ( para ([ i 10 a 20 ]) ( printf "i = ~s \n " i )) Algunas secuencias se implementan de forma imperativa (con variables de estado privadas) y otras se implementan como listas diferidas (posiblemente infinitas). Además, las nuevas definiciones de estructuras pueden tener una propiedad que especifica cómo se pueden utilizar como secuencias.
Pero más directamente, Racket viene con una biblioteca de generadores para una especificación de generador más tradicional. Por ejemplo,
#lang raqueta ( requiere raqueta/generador ) ( definir ( ints-from de ) ( generador () ( para ([ i ( in-naturals de )]) ; secuencia infinita de números enteros desde 0 ( rendimiento i )))) ( definir g ( ints-de 10 )) ( lista ( g ) ( g ) ( g )) ; -> '(10 11 12) Tenga en cuenta que el núcleo de Racket implementa potentes funciones de continuación, proporcionando continuaciones generales (reentrantes) que se pueden componer y también continuaciones delimitadas. Con esto, la biblioteca generadora se implementa en Racket.
La comunidad de PHP implementó generadores en PHP 5.5. Los detalles se pueden encontrar en la Solicitud de comentarios original: Generadores.
Secuencia infinita de Fibonacci:
función fibonacci () : \Generador { $último = 0 ; $actual = 1 ; rendimiento 1 ; mientras ( verdadero ) { $actual = $último + $actual ; $último = $actual - $último ; rendimiento $actual ; } }foreach ( fibonacci () as $número ) { echo $número , " \n " ; }Secuencia de Fibonacci con límite:
función fibonacci ( int $límite ) : generador { rendimiento $a = $b = $i = 1 ; mientras ( ++ $i < $límite ) { rendimiento $a = ( $b = $a + $b ) - $a ; } }foreach ( fibonacci ( 10 ) como $número ) { echo " $número \n " ; }Cualquier función que contenga una declaración de rendimiento es automáticamente una función generadora.
Ruby admite generadores (a partir de la versión 1.9) en forma de la clase Enumerator incorporada.
# Generador de un objeto Enumerador chars = Enumerator . nuevo ( [ 'A' , 'B' , 'C' , 'Z' ] ) 4 . veces { pone caracteres . próximo } # Generador a partir de un recuento de bloques = Enumerador . nuevo hacer | productor | i = 0 bucle { ceder . rendimiento i += 1 } final 100 . veces { pone cuenta . próximo } Java ha tenido una interfaz estándar para implementar iteradores desde sus inicios y, desde Java 5, la construcción "foreach" facilita el recorrido por los objetos que proporcionan la java.lang.Iterableinterfaz. (El marco de colecciones de Java y otros marcos de colecciones generalmente proporcionan iteradores para todas las colecciones).
par de registros ( int a , int b ) {}; Iterable <Entero> myIterable = Flujo . iterar ( nuevo par ( 1 , 1 ), p -> nuevo par ( p . b , p . a + p . b )) . límite ( 10 ) . mapa ( p -> p . a ):: iterador ; miIterable . paraCada ( Sistema . out :: println );O obtenga un iterador de la superinterfaz BaseStream de Stream de Java 8 .
par de registros ( int a , int b ) {}; // Guarda el iterador de una secuencia que genera la secuencia Fib Iterator < Integer > myGenerator = Stream // Genera la secuencia Fib . iterar ( nuevo par ( 1 , 1 ), p -> nuevo par ( p . b , p . a + p . b )) . mapa ( p -> p . a ). iterador (); // Imprime los primeros 5 elementos para ( int i = 0 ; i < 5 ; i ++ ) { System . afuera . println ( miGenerador . next ()); } Sistema . afuera . println ( "hecho con la primera iteración" );// Imprime los siguientes 5 elementos para ( int i = 0 ; i < 5 ; i ++ ) { System . afuera . println ( miGenerador . next ()); } Producción:
1 1 2 3 5 hecho con la primera iteración 8 13 21 34 55Un ejemplo de generador de C# 2.0 ( yieldestá disponible desde la versión 2.0 de C#): ambos ejemplos utilizan genéricos, pero esto no es obligatorio. La palabra clave de rendimiento también ayuda a implementar iteraciones con estado personalizadas sobre una colección, como se analiza en esta discusión. [12]
// Método que toma una entrada iterable (posiblemente una matriz) // y devuelve todos los números pares. public static IEnumerable < int > GetEven ( IEnumerable < int > números ) { foreach ( int número en números ) { if (( número % 2 ) == 0 ) { rendimiento número de retorno ; } } } Es posible utilizar varias yield returndeclaraciones y se aplican en secuencia en cada iteración:
clase pública CityCollection : IEnumerable < cadena > { IEnumerator público < cadena > GetEnumerator () { rendimiento retorno "Nueva York" ; rendimiento retorno "París" ; rendimiento retorno "Londres" ; } } En XL , los iteradores son la base de los bucles 'for':
importar IO = XL.UI.CONSOLEiterador IntegerIterator (var out Contador: entero; Bajo, Alto: entero) Contador escrito en Bajo..Alto es Contador := Bajo while Contador <= bucle alto producir Contador += 1// Tenga en cuenta que no es necesario declarar I, porque declaró 'var out' en el iterador// Por lo tanto, aquí se realiza una declaración implícita de I como un número enteropara I en 1..5 bucle IO.WriteLn "I=", yoF# proporciona generadores mediante expresiones de secuencia , desde la versión 1.9.1. [13] Estos pueden definir una secuencia (evaluada con entusiasmo, acceso secuencial) a través de seq { ... }, una lista (evaluada con entusiasmo, acceso secuencial) a través de [ ... ]o una matriz (evaluada con entusiasmo, acceso indexado) a través [| ... |]de que contiene código que genera valores. Por ejemplo,
seq { para b en 0 .. 25 hazlo si b < 15 entonces produce b * b } forma una secuencia de cuadrados de números del 0 al 14 filtrando números del rango de números del 0 al 25.
Los generadores se agregaron a Python en la versión 2.2 en 2001. [6] Un generador de ejemplo:
al escribir import Iteratordef contar desde ( n : int ) -> Iterador [ int ]: mientras que Verdadero : producir n n += 1# Uso de ejemplo: imprimir los números enteros del 10 al 20. # Tenga en cuenta que esta iteración termina normalmente, a pesar de que # countfrom() esté escrito como un bucle infinito.para i en cuenta desde ( 10 ): si i <= 20 : imprimir ( i ) más : romper# Otro generador, que produce números primos indefinidamente según sea necesario. importar itertoolsdef primos () -> Iterador [ int ]: """Genera números primos indefinidamente según sea necesario.""" produce 2 n = 3 p = [ 2 ] while True : # Si se divide n por todos los números en p, hasta e incluyendo sqrt(n), # produce un resto distinto de cero, entonces n es primo. si todo ( n % f > 0 para f en itertools . take while ( lambda f : f * f <= n , p )): rendimiento n p . añadir ( n ) n += 2 En Python, se puede considerar un generador como un iterador que contiene un marco de pila congelado . Cada vez que next()se llama al iterador, Python reanuda el marco congelado, que se ejecuta normalmente hasta que yieldse llega a la siguiente declaración. Luego, el marco del generador se congela nuevamente y el valor obtenido se devuelve a la persona que llama.
PEP 380 (implementado en Python 3.3) agrega la yield fromexpresión, permitiendo a un generador delegar parte de sus operaciones a otro generador o iterable. [14]
Python tiene una sintaxis modelada a partir de la de listas por comprensión , llamada expresión generadora que ayuda en la creación de generadores. Lo siguiente amplía el primer ejemplo anterior utilizando una expresión generadora para calcular cuadrados a partir de la countfromfunción generadora:
cuadrados = ( n * n para n en conteo desde ( 2 ))para j en cuadrados : si j <= 20 : imprimir ( j ) más : romperECMAScript 6 (también conocido como Harmony) introdujo funciones de generador.
Se puede escribir una secuencia infinita de Fibonacci usando un generador de funciones:
función * fibonacci ( límite ) { let [ prev , curr ] = [ 0 , 1 ]; while ( ! límite || curr <= límite ) { rendimiento curr ; [ anterior , actual ] = [ actual , anterior + actual ]; } } // delimitado por el límite superior 10 for ( const n de fibonacci ( 10 )) { console . iniciar sesión ( norte ); } // generador sin límite superior para ( const n de fibonacci ()) { console . iniciar sesión ( norte ); si ( n > 10000 ) se rompe ; } // iterando manualmente let fibGen = fibonacci (); consola . iniciar sesión ( fibGen . siguiente (). valor ); // 1 consola . iniciar sesión ( fibGen . siguiente (). valor ); // 1 consola . iniciar sesión ( fibGen . siguiente (). valor ); // 2 consolas . iniciar sesión ( fibGen . siguiente (). valor ); // 3 consolas . iniciar sesión ( fibGen . siguiente (). valor ); // 5 consola . iniciar sesión ( fibGen . siguiente (). valor ); // 8 // continúa desde donde se detuvo durante ( const n of fibGen ) { console . iniciar sesión ( norte ); si ( n > 10000 ) se rompe ; } El paquete de iteradores se puede utilizar para este propósito. [15] [16]
biblioteca ( iteradores )# Ejemplo ------------------ abc <- iter ( c ( 'a' , 'b' , 'c' )) nextElem ( abc ) Ejemplo en Pharo Smalltalk :
El siguiente generador de proporción áurea devuelve a cada invocación 'goldenRatio next' una mejor aproximación a la proporción áurea.
goldenRatio := Generador activado: [ : g | | xyz | x := 0 . y := 1 .[ z := x + y . r := ( z / y ) comoFlotante . x := y . y := z . g rendimiento: r ] repetir
] .goldenRatio siguiente .La siguiente expresión devuelve las siguientes 10 aproximaciones.
Carácter cr unirse: (( 1 a: 10 ) recopilar: [ : ficticio | relación siguiente ]) .Ver más en Una joya escondida en Pharo: Generador.