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 construir una matriz que contiene todos los valores y devolverlos todos a la vez, un generador produce los valores uno a la vez, lo que requiere menos memoria y permite que la persona que llama comience a procesar los primeros valores inmediatamente. En resumen, un generador parece una función pero se comporta como uniterador .
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 de (y más débil) que las corrutinas, ya que siempre devuelven el control al llamador (cuando devuelven un valor), en lugar de especificar una corrutina para saltar a; ver comparación de corrutinas con generadores .
Usos
Los generadores generalmente 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 al principio, 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 rendimiento , la ejecución del cuerpo del generador también se puede terminar con una acción de finalización , momento en el que se termina el bucle más interno que encierra la invocación del generador. En situaciones más complicadas, un generador se puede usar manualmente fuera de un bucle para crear un iterador, que luego se puede usar de varias maneras.
Debido a que los generadores calculan sus valores producidos solo bajo 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 se desea 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 g
se puede evaluar en una lista l
mediante l = list(g)
, mientras que en F # la expresión de secuencia se seq { ... }
evalúa de forma perezosa (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 ... final de bucle; Todas las construcciones de bucle habituales se pueden simular cómodamente utilizando generadores adecuados de la manera correcta. Por ejemplo, un bucle de rango como for x = 1 to 10
se puede implementar como iteración a través de un generador, como en Python for x in range(1, 10)
. Además, break
se puede implementar enviando el final al generador y luego usarlo continue
en el bucle.
Cronología
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 , las últimas versiones de ECMAScript (a partir de ES6 / ES2015) y otros idiomas. En CLU y C #, los generadores se denominan iteradores y en Ruby, enumeradores .
Ceceo
El estándar final Common Lisp no proporciona generadores de forma nativa, sin embargo, existen varias implementaciones de bibliotecas, como SERIES documentadas en CLtL2 o pygen .
CLU
Una declaración de rendimiento se utiliza para implementar iteradores sobre abstracciones de datos definidas por el usuario. [8]
string_chars = iter (s: string) produce (char); índice: int: = 1; límite: int: = cadena $ tamaño (s); while índice <= límite hacer rendimiento (cadena $ fetch (s, índice)); índice: = índice + 1; final;end string_chars;para c: char en string_chars (s) do ...final;
Icono
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 usando el mecanismo del generador (la disyunción lógica u "OR" se hace de esta manera).
La impresión de cuadrados de 0 a 20 se puede lograr usando una co-rutina escribiendo:
cuadrados locales, j cuadrados: = crear (seq (0) ^ 2) cada j: = | @squares hacen si j <= 20 entonces escribir (j) demás rotura
Sin embargo, la mayoría de las veces los generadores personalizados se implementan con la palabra clave "suspender" que funciona exactamente como la palabra clave "rendimiento" en CLU.
C
C no tiene funciones generadoras como una construcción del lenguaje, pero, como son un subconjunto de corrutinas , es simple implementarlas usando cualquier marco que implemente corrutinas apilables, como libdill. [9] En las plataformas POSIX, cuando el costo del cambio de contexto por iteración no es una preocupación, o se desea un paralelismo completo en lugar de una mera concurrencia , se puede implementar un marco de función de generador muy simple usando pthreads y tuberías .
C ++
Es posible introducir generadores en C ++ utilizando macros de preprocesador. El código resultante puede tener aspectos muy diferentes a los de C ++ nativo, pero la sintaxis del generador puede ser muy ordenada. [10] El conjunto de macros de preprocesador definido en esta fuente permite a los generadores definidos con la sintaxis como en el siguiente ejemplo:
$ generador ( descenso ) { int i ; // coloca el constructor de nuestro generador, por ejemplo, // descenso (int minv, int maxv) {...} // from $ emit to $ stop es un cuerpo de nuestro generador: $ emit ( int ) // emitirá valores int. 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], invertido. $ parada ; // parada, final de secuencia. Fin del cuerpo del generador. };
Esto luego se puede iterar usando:
int main ( int argc , char * argv []) { descendencia gen ; for ( int n ; gen ( n );) // "obtener el siguiente" invocación del generador printf ( "el siguiente número es% d \ n " , n ); return 0 ; }
Además, C ++ 11 permite que los bucles foreach se apliquen a cualquier clase que proporcione las funciones begin
y end
. Entonces es posible escribir clases de tipo generador definiendo tanto los métodos iterables ( begin
y end
) como los métodos iteradores ( operator!=
, operator++
y operator*
) en la misma clase. Por ejemplo, es posible escribir el siguiente programa:
#include int main () { for ( int i : range ( 10 )) { std :: cout << i << std :: endl ; } return 0 ; }
Una implementación de rango básica se vería así:
rango de clases { privado : int último ; int iter ;public : range ( int end ) : last ( end ), iter ( 0 ) {} // Funciones iterables const range & begin () const { return * this ; } const range & end () const { return * this ; } // Funciones de iterador bool operator ! = ( Const range & ) const { return iter < last ; } operador vacío ++ () { ++ iter ; } int operator * () const { return iter ; } };
Perl
Perl no proporciona generadores de forma nativa, pero el módulo Coro :: Generator proporciona soporte , que utiliza el marco de co-rutina de Coro . Uso de ejemplo:
uso estricto ; use advertencias ; # Habilita el generador {BLOQUEO} y haz uso de Coro :: Generator ; # Referencia de matriz para iterar sobre mis $ chars = [ 'A' ... 'Z' ];# Nuevo generador que se puede llamar como coderef. my $ letras = generador { my $ i = 0 ; para mi $ letra ( @ $ caracteres ) { # obtener la siguiente letra de $ caracteres producir $ letra ; } };# Llame al generador 15 veces. imprimir $ letras -> (), "\ n" para ( 0 .. 15 );
Tcl
En Tcl 8.6, el mecanismo generador se basa en corrutinas con nombre .
proc generator { cuerpo } { coroutine gen [ incr :: desambiguator ] apply {{ script } { # Produce el resultado de [generador], el nombre del generador produce [ info coroutine ] # Realiza la generación eval $ script # Termina el ciclo de la persona que llama usando un retorno de excepción 'break' - código break }} $ body }# Use un simple ciclo 'for' para hacer el recuento de conjuntos de generación real [ generador { para {conjunto i 10 } { $ i <= 20 } { incr i } { rendimiento $ i } }]# Extrae valores del generador hasta que se agote mientras 1 { pone [ $ count ] }
Haskell
En Haskell , con su modelo de evaluación perezosa , todo es un generador: cada dato creado con un constructor de datos no estricto se genera a pedido. Por ejemplo,
contar desde n = n : contar desde ( n + 1 )- Ejemplo de uso: imprimir los números enteros del 10 al 20. test1 = mapM_ print $ takeWhile ( <= 20 ) $ countfrom 10primes = 2 : 3 : nextprime 5 donde nextprime n | b = n : nextprime ( n + 2 ) | de lo contrario = nextprime ( n + 2 ) donde b = all (( / = 0 ) . ( rem n )) $ takeWhile (( <= n ) . ( ^ 2 )) $ tail primes
donde (:)
es un constructor de lista no estricto, contras , y $
es solo un operador "llamado con" , que se usa para entre paréntesis. Esto usa la función de adaptador estándar,
takeWhile p [] = [] takeWhile p ( x : xs ) | p x = x : takeWhile p xs | de lo contrario = []
que recupera valores que están de acuerdo con un predicado y deja de solicitar nuevos valores tan pronto como se encuentra uno no aceptable. El acceso al almacenamiento compartido se utiliza como mediador universal en Haskell. Las listas por comprensión se pueden utilizar libremente:
test2 = mapM_ print $ takeMientras ( <= 20 ) [ x * x | x <- countfrom 10 ] test3 = mapM_ print [ x * x | x <- takeWhile ( <= 20 ) $ countfrom 10 ]
Raqueta
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:
( defina 10 a 20 ( dentro del rango 10 20 )) ( para ([ i 10 a 20 ]) ( printf "i = ~ s \ n " i ))
Algunas secuencias se implementan imperativamente (con variables de estado privadas) y algunas se implementan como listas diferidas (posiblemente infinitas). Además, las nuevas definiciones de estructuras pueden tener una propiedad que especifique cómo se pueden usar como secuencias.
Pero más directamente, Racket viene con una biblioteca de generador para una especificación de generador más tradicional. Por ejemplo,
#lang raqueta ( requerir raqueta / generador ) ( definir ( ints-de de ) ( generador de () ( para ([ i ( en-naturals de )]) ; secuencia infinita de números enteros de 0 ( rendimiento i )))) ( definen 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. Usando esto, la biblioteca del generador se implementa en Racket.
PHP
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:
function fibonacci () { $ last = 0 ; $ actual = 1 ; rendimiento 1 ; while ( verdadero ) { $ actual = $ último + $ actual ; $ último = $ actual - $ último ; rendimiento $ actual ; } }foreach ( fibonacci () como $ número ) { echo $ número , " \ n " ; }
Secuencia de Fibonacci con límite:
función fibonacci ( int $ límite ) : generador { rendimiento $ a = $ b = $ i = 1 ; while ( ++ $ 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.
Rubí
Ruby admite generadores (a partir de la versión 1.9) en la forma de la clase incorporada Enumerator.
# Generador de un objeto Enumerator chars = Enumerator . nuevo ( [ 'A' , 'B' , 'C' , 'Z' ] )4 . veces { pone caracteres . siguiente }# Generador de un recuento de bloques = Enumerador . nuevo hacer | productor | i = 0 bucle { productor . rendimiento i + = 1 } fin100 . veces { pone cuenta . siguiente }
Java
Java ha tenido una interfaz estándar para implementar iteradores desde sus primeros días, y desde Java 5, la construcción "foreach" hace que sea fácil recorrer los objetos que proporcionan la java.lang.Iterable
interfaz. (El marco de las colecciones de Java y otros marcos de las colecciones, normalmente proporcionan iteradores para todas las colecciones).
Sin embargo, Java no tiene generadores integrados en el lenguaje. Esto significa que crear iteradores suele ser mucho más complicado que en lenguajes con generadores integrados, especialmente cuando la lógica de generación es compleja. Debido a que todos los estados deben guardarse y restaurarse cada vez que un elemento se obtiene de un iterador, no es posible almacenar el estado en variables locales o usar rutinas de bucle integradas, como cuando hay generadores disponibles; en su lugar, todo esto debe simularse manualmente, utilizando campos de objeto para contener contadores de bucle y estado local.
Incluso los iteradores simples construidos de esta manera tienden a ser significativamente más voluminosos que los que usan generadores, con mucho código repetitivo .
El ejemplo original anterior podría escribirse en Java 5 como:
// Iterador implementado como clase anónima. Esto usa genéricos pero no es necesario. para ( int i : nueva Iterable < Entero > () { @ Override público Iterator < Entero > iterador () { regrese nuevo Iterator < Entero > () { int contador = 1 ; @Override public boolean hasNext () { contador de retorno <= 100 ; } @Override public Integer next () { contador de retorno ++ ; } @Override public void remove () { lanzar nueva UnsupportedOperationException (); } }; } }) { Sistema . fuera . println ( i ); }
Una secuencia infinita de Fibonacci también podría escribirse en Java 5 como un iterador:
Iterable < Entero > fibo = nuevo Iterable < Entero > () { @ Override público Iterator < Entero > iterador () { volver nuevo Iterator < Entero > () { int un = 1 , b = 2 ; @Override public boolean hasNext () { return true ; } @Override public Integer next () { int temp = a ; a = b ; b = a + temp ; temperatura de retorno ; } @Override public void remove () { lanzar nueva UnsupportedOperationException (); } }; } }; // esto podría usarse como ... for ( int f : fibo ) { System . fuera . println ( "el siguiente número de Fibonacci es" + f ); si ( alguna condición ( f )) se rompe ; }
Además, también se podría escribir una secuencia infinita de Fibonacci usando la interfaz Java 8 Stream:
IntStream . generar ( nuevo IntSupplier () { int a = 1 , b = 2 ; public int getAsInt () { int temp = a ; a = b ; b = a + temp ; temperatura de retorno ; } }). forEach ( System . out :: println );
O consiga un iterador de la superinterfaz BaseStream of Stream de Java 8 .
public Iterable < Integer > fibonacci ( int limit ) { return IntStream . generar ( nuevo IntSupplier () { int a = 1 , b = 2 ; public int getAsInt () { int temp = a ; a = b ; b = a + temp ; temperatura de retorno ; } }). límite ( límite ). boxed () :: iterador ; } // esto podría usarse como ... for ( int f : fibonacci ( 10 )) { System . fuera . println ( f ); }
C#
Un ejemplo de generador de C # 2.0 ( yield
está disponible desde la versión 2.0 de C #): ambos ejemplos utilizan genéricos, pero esto no es necesario. La palabra clave yield también ayuda a implementar iteraciones con estado personalizadas sobre una colección, como se explica en esta discusión. [11]
// 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 devuelve el número ; } } }
Es posible utilizar varias yield return
declaraciones y se aplican en secuencia en cada iteración:
clase pública CityCollection : IEnumerable < string > { public IEnumerator < string > GetEnumerator () { rendimiento devuelve "Nueva York" ; rendimiento rendimiento "París" ; rendimiento rendimiento "Londres" ; } }
SG
En XL , los iteradores son la base de los bucles 'for':
importar IO = XL.UI.CONSOLEiterador IntegerIterator (var out Counter: integer; Low, High: integer) escrito Contador en Low..High es Contador: = Bajo while Contador <= bucle alto producir Contador + = 1// Tenga en cuenta que no es necesario que se declare, porque se declaró 'var out' en el iterador// Por tanto, aquí se hace una declaración implícita de I como un número enteropara I en 1..5 bucle IO.WriteLn "I =", I
F#
F # proporciona generadores a través de expresiones de secuencia , desde la versión 1.9.1. [12] Estos pueden definir una secuencia (evaluado perezosamente, acceso secuencial) vía seq { ... }
, una lista (evaluado con entusiasmo, acceso secuencial) vía [ ... ]
o una matriz (acceso indexado, evaluado con entusiasmo) vía [| ... |]
que contiene código que genera valores. Por ejemplo,
seq { para b en 0 .. 25 hacer si b < 15 entonces produce b * b }
forma una secuencia de cuadrados de números del 0 al 14 al filtrar los números del rango de números del 0 al 25.
Pitón
Los generadores se agregaron a Python en la versión 2.2 en 2001. [6] Un generador de ejemplo:
de tipificación de importación iteradordef countfrom ( n : int ) -> Iterador [ int ]: while True : rendimiento n n + = 1# Ejemplo de uso: imprimir los números enteros del 10 al 20. # Tenga en cuenta que esta iteración termina normalmente, a pesar de que # countfrom () se escribe como un bucle infinito.para i en countfrom ( 10 ): if i <= 20 : print ( i ) else : break# Otro generador, que produce números primos indefinidamente según sea necesario. importar itertoolsdef primes () -> Iterator [ int ]: produce 2 n = 3 p = [] while True : # Si divide n por todos los números en p, hasta e incluyendo sqrt (n), # produce un resto distinto de cero entonces n es primo. if all ( 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 pensar en un generador como un iterador que contiene un marco de pila congelado . Siempre que next()
se invoca en el iterador, Python reanuda el fotograma congelado, que se ejecuta normalmente hasta yield
que se alcanza la siguiente instrucción. A continuación, la trama del generador se congela de nuevo y el valor obtenido se devuelve a la persona que llama.
PEP 380 (implementado en Python 3.3) agrega la yield from
expresión, lo que permite que un generador delegue parte de sus operaciones a otro generador o iterable. [13]
Expresiones generadoras
Python tiene una sintaxis inspirada en la de las listas por comprensión , llamada expresión generadora que ayuda en la creación de generadores. A continuación, se amplía el primer ejemplo anterior mediante el uso de una expresión generadora para calcular cuadrados a partir de la countfrom
función generadora:
cuadrados = ( n * n para n en countfrom ( 2 ))para j en cuadrados : si j <= 20 : print ( j ) else : break
ECMAScript
ECMAScript 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 ; [ prev , curr ] = [ curr , prev + curr ]; } }// delimitado por el límite superior 10 para ( const n of fibonacci ( 10 )) { console . log ( n ); }// generador sin límite superior para ( const n of fibonacci ()) { console . log ( n ); si ( n > 10000 ) se rompe ; }// iterando manualmente let fibGen = fibonacci (); consola . log ( fibGen . next (). valor ); // 1 consola . log ( fibGen . next (). valor ); // 1 consola . log ( fibGen . next (). valor ); // 2 consola . log ( fibGen . next (). valor ); // 3 consola . log ( fibGen . next (). valor ); // 5 consola . log ( fibGen . next (). valor ); // 8// retoma desde donde se detuvo para ( const n of fibGen ) { console . log ( n ); si ( n > 10000 ) se rompe ; }
R
El paquete de iteradores se puede utilizar para este propósito. [14] [15]
biblioteca ( iteradores )# Ejemplo ------------------ abc <- iter ( c ( 'a' , 'b' , 'c' )) nextElem ( abc )
Charla
Ejemplo en Pharo Smalltalk :
El generador de proporción áurea a continuación devuelve a cada invocación 'goldenRatio next' una mejor aproximación a la proporción áurea.
goldenRatio : = Generador en: [ : g | | xyzr | x : = 0 . y : = 1 .[ z : = x + y . r : = ( z / y ) asFloat . x : = y . y : = z . g rendimiento: r ] repetir
] .goldenRatio a continuación .
La siguiente expresión devuelve las siguientes 10 aproximaciones.
Carácter cr join: (( 1 a: 10 ) recolectar: [ : dummy | ratio siguiente ]) .
Vea más en Una joya escondida en Pharo: Generator .
Ver también
- Lista de comprensión de otro constructo que genera una secuencia de valores
- Iterador para el concepto de producir una lista de un elemento a la vez
- Iteratee por una alternativa
- Evaluación perezosa para producir valores cuando sea necesario
- Corecursion para datos potencialmente infinitos por recursividad en lugar de rendimiento
- Corutina para una generalización aún mayor de la subrutina
- Continuación para la generalización del flujo de control.
Notas
- ^ ¿Cuál es la diferencia entre un iterador y un generador?
- ^ Kiselyov, Oleg (enero de 2004). "Formas generales de atravesar colecciones en Scheme" .
- ^ Anthony Ralston (2000). Enciclopedia de informática . Nature Pub. Grupo. ISBN 978-1-56159-248-7. Consultado el 11 de mayo de 2013 .
- ^ El lenguaje de programación de iconos utiliza generadores para implementar su evaluación dirigida a objetivos. En Icon, los generadores se pueden invocar en contextos fuera de las estructuras normales de control de bucle.
- ^ Liskov, Barbara (abril de 1992). "Una historia de CLU" (PDF) . Archivado desde el original (pdf) el 17 de septiembre de 2003 . Consultado el 5 de enero de 2006 .
- ^ a b Propuestas de mejora de Python: PEP 255: Generadores simples , PEP 289: Expresiones de generador , PEP 342: Corutinas a través de generadores mejorados
- ^ rendimiento (referencia de C #)
- ^ Liskov, B .; Snyder, A .; Atkinson, R .; Schaffert, C. (1977). "Mecanismos de abstracción en CLU". Comunicaciones de la ACM . 20 (8). CiteSeerX 10.1.1.112.656 . doi : 10.1145 / 359763.359789 .
- ^ "Concurrencia estructurada para C" .
- ^ http://www.codeproject.com/KB/cpp/cpp_generators.aspx
- ^ "¿Para qué se utiliza la palabra clave de rendimiento en C #?" . stackoverflow.com . Consultado el 1 de enero de 2018 .
- ^ "Algunos detalles sobre las expresiones de cálculo F #" . Consultado el 14 de diciembre de 2007 .
- ^ PEP 380 - Sintaxis para delegar en un subgenerador
- ^ Funciones del generador en R
- ^ http://cartesianfaith.wordpress.com/2013/01/05/infinite-generators-in-r/
Referencias
- Stephan Murer, Stephen Omohundro , David Stoutamire y Clemens Szyperski: abstracción iterativa en Sather . Transacciones ACM sobre lenguajes y sistemas de programación , 18 (1): 1-15 (1996) [1]