Usuario:Edgard MV/Taller

De Wikipedia, la enciclopedia libre
Este es el taller de Edgard MV. Un taller de usuario es una subpágina de usuario que sirve para iniciar el desarrollo de artículos o realizar pruebas. Esto no es un artículo de la enciclopedia.
También puedes realizar pruebas de edición desechables en la zona de pruebas común, o crear otros talleres o subpáginas.

En informática, memoización es una técnica de optimización de software principalmente usada para acelerar programas de computadora al almacenar los resultados de llamadas a funciones costosas y devolver el resultado guardado cuando las mismas entradas son dadas nuevamente. Memoización también ha sido usada en otros contextos (y para otros fines diferentes a ganancias de velocidad), como en parsing descendiente mutuamente recursivo simple.[1]​ A pesar de estar relacionada a caching, memoización se refiere a un caso específico de optimización, distinguiéndole de otras formas de caching, tales como buffering o reemplazo de página. En el contexto de algunos lenguajes de programación lógicos, memoización es también conocida como tabling.[2]​

Etimología[editar]

El termino “memoización” fue acuñado por Donald Michie en 1968[3]​ y es derivado de la palabra en latín “memorandum” (“ser recordado”), usualmente truncado como “memo” en el inglés americano (lenguaje de origen del término), y como tal carga con el significado de “convertir [los resultados de] una función en algo a ser recordado”. Mientras que “memoización” puede ser confundido con “memorización” (porque estas son etimológicamente cognadas), “memoización” tiene un significado especializado en computación.

Resumen[editar]

Una función memoizada “recuerda” el resultado correspondiente a algún conjunto de entradas específicas. Llamadas subsecuentes con entradas recordadas retornan el resultado guardado en lugar de calcularlo nuevamente, de esta forma eliminando el costo primario de una llamada con ciertos parámetros dados de todas, excepto la primera llamada hecha a la función con esos parámetros. El conjunto de asociaciones recordadas puede ser un conjunto de tamaño definido controlado por un algoritmo de reemplazo o un conjunto predefinido, dependiendo de la naturaleza de la función y su utilización. Una función solo puede ser memoizada si esta es referencialmente transparente; es decir, solo si llamar a la función tiene el mismo efecto que reemplazar ese llamado a la función con su valor de retorno. (No obstante, existen algunas excepciones de casos especiales a esta restricción.) A pesar de estar relacionada a lookup tables, ya que memoización a menudo usa dichas tablas en su implementación, memoización pobla su cache de resultados transparentemente durante la ejecución, cuando se necesite, en lugar de hacerlo por adelantado.

Memoización es una manera de reducir el costo de tiempo de una función a cambio de costo de espacio; es decir, funciones memoizadas se vuelven optimizadas en velocidad a cambio de un uso más alto de espacio de memoria de la computadora. El “costo” espacio/tiempo de un algoritmo tiene un nombre específico en computación: complejidad computacional. Todas las funciones tienen una complejidad computacional en tiempo (i.e., el tiempo que les toma de ejecución) y en espacio.

A pesar de que ocurre un intercambio espacio-tiempo (i.e., espacio usado es velocidad ganada), esto difiere de otras optimizaciones que involucran intercambios espacio-tiempo, tales como reducción de fuerza, en que memoización es una optimización en tiempo de ejecución en lugar de tiempo de compilación. Además, reducción de fuerza muy probablemente reemplaza una operación costosa tal como multiplicación con una menos costosa como adición, y el resultado en ganancias puede ser altamente dependiente de la máquina (no-portable a través de máquinas), mientras que memoización es una estrategia multiplataforma más independiente de la máquina.

Considere la siguiente función en pseudocódigo para calcular el factorial de n: 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else   
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Para cada entero n tal que n≥0, el resultado final de la función factorial es invariante; si es invocada como x = factorial(3), el resultado es tal que a x siempre le será asignado el valor 6. La implementación no memoizada de arriba, dada la naturaleza del algoritmo recursivo involucrado, requeriría n + 1 invocaciones de factorial para llegar a un resultado, y cada una de estas invocaciones, a su vez, tiene un costo asociado en el tiempo que le toma a la función retornar el valor computado. Dependiendo de la máquina, este costo podría ser la suma de:

  1. El costo de establecer el marco de pila de llamadas funcional.
  2. El costo de comparar n con 0.
  3. El costo de substraer 1 de n.
  4. El costo de establecer el marco de pila para llamadas recursivas.
  5. El costo de multiplicar el resultado de la llamada recursiva a factorial por n.
  6. El costo de almacenar el resultado retornado, de tal forma, que pueda ser usado por el contexto invocador.

En una implementación no memoizada, cada llamada de nivel superior hecha a factorial incluye el costo acumulativo de los pasos 3 hasta 6 proporcionales a el valor inicial de n. Una versión memoizada de la función factorial sería: 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

En este ejemplo en particular, si factorial es invocada primero con el valor 5, y luego invocada con cualquier valor menor que o igual a 5, esos valores de retorno también habrán sido memoizados, ya que factorial habrá sido llamada recursivamente con los valores 5, 4, 3, 2, 1, y 0, y los valores de retorno para cada uno de estos habrá sido almacenado. Si entonces es llamada con un número mayor que 5, como 7, solo se harán 2 llamadas recursivas (7 y 6), y el valor para 5! habrá sido almacenado de llamadas previas. De esta manera, memoización permite a una función volverse mas eficiente en tiempo mientras sea llamada a menudo, así resultando en una eventual ganancia de velocidad general.

Algunas otras consideraciones[editar]

Programación funcional[editar]

Artículo principal: Programación funcional

Memoización es muy usada en compiladores para lenguajes de programación funcional, los cuales usan a menudo estrategia de evaluación llamar por nombre. Para evitar sobrecarga por calcular valores de argumentos, los compiladores para estos lenguajes usan intensamente funciones auxiliares llamadas thunks para computar los valores de argumentos, y memoizar estas funciones para evitar cálculos repetidos.

Memoización automática[editar]

Si bien un programador de computadoras puede agregar la memoización a las funciones interna y explícitamente de la misma manera que se implementa la versión memoizada anterior de factorial, las funciones referencialmente transparentes también pueden memoizarse automáticamente externamente.[1]​ Las técnicas empleadas por Peter Norvig tienen aplicación no solo en Common Lisp (el lenguaje en el que su trabajo demostró la memoización automática), sino también en varios otros lenguajes de programación. Las aplicaciones de la memoización automática también se han explorado formalmente en el estudio de la reescritura de términos[4]​ y la inteligencia artificial.[5]​

En los lenguajes de programación donde las funciones son objetos de primera clase (como Lua, Python o Perl [1]​), la memorización automática se puede implementar reemplazando (en tiempo de ejecución) una función con su valor calculado una vez que se ha calculado un valor para Un conjunto dado de parámetros. La función que realiza esta sustitución de valor-por-función-objeto puede envolver genéricamente cualquier función transparente referencial. Considere el siguiente pseudocódigo (donde se supone que las funciones son valores de primera clase): 

function memoized-call (F is a function object parameter)
    if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
    end if;
 
    if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;
 
    return F.values[arguments];     
end function

Para llamar a una versión memorizada automáticamente de factorial utilizando la estrategia anterior, en lugar de llamar a factorial directamente, el código invoca Llamada-Memoizada (factorial (n)). Cada una de estas llamadas primero verifica si se ha asignado una matriz de soporte para almacenar resultados y, si no, adjunta esa matriz. Si no existe una entrada en los valores de posición [argumentos] (donde los argumentos se usan como la clave de la matriz asociativa), se realiza una llamada real a factorial con los argumentos proporcionados. Finalmente, la entrada en la matriz en la posición clave se devuelve a la persona que llama.

La estrategia anterior requiere un ajuste explícito en cada llamada a una función que se debe memoizar. En aquellos lenguajes que permiten clausuras, la memoización puede ser efectuada implícitamente por una fábrica de functor que devuelve un objeto de función memoizado envuelto. En pseudocódigo, esto se puede expresar de la siguiente manera: 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;
 
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];     
    end let;
 
    return memoized-version;
end function

En lugar de llamar factorial, se crea un nuevo objeto de función memfact de la siguiente manera: 

 memfact = construct-memoized-functor(factorial)

Esencialmente, tales técnicas implican adjuntar el objeto de función original al funtor creado y reenviar llamadas a la función original que se está memoizando a través de un alias cuando se requiere una llamada a la función real (para evitar una recursión sin fin), como se ilustra a continuación: 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;
 
    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];     
    end let;
 
    return memoized-version;
end function

Analizadores[editar]

Cuando un analizador de arriba hacia abajo intenta analizar una entrada ambigua con respecto a una ambigua gramática libre de contexto (CFG), puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas de la CFG para producir todos los posibles árboles de análisis. Esto eventualmente requeriría un espacio de memoria exponencial. La memorización fue explorada como una estrategia de análisis en 1991 por Peter Norvig, quien demostró que un algoritmo similar al uso de programación dinámica y conjuntos de estados en el algoritmo de Earley (1970), y tablas en el algoritmo CYK de Cocke, Younger y Kasami, podrían generarse introduciendo la memorización automática a un simple analizador descendente recursivo de retroceso para resolver el problema de la complejidad exponencial en el tiempo.[1]​ La idea básica en el enfoque de Norvig es que cuando se aplica un analizador a la entrada, el resultado se almacena en un memotable para su posterior reutilización si el mismo analizador alguna vez se vuelve a aplicar a la misma entrada. Richard Frost también usó la memorización para reducir la complejidad de tiempo exponencial de los combinadores de analizador, que puede verse como una técnica de análisis de "Retroceso de arriba hacia abajo puramente funcional".[6]​ Mostró que los combinadores de analizadores básicos memorizados se pueden usar como bloques de construcción para construir analizadores complejos como especificaciones ejecutables de CFGs.[7]​[8]​ Fue nuevamente explorado en el contexto del análisis en 1995 por Johnson y Dörre.[9]​[10]​ En 2002, Ford lo examinó en profundidad considerable en la forma llamada análisis de paquete.[11]​

En 2007, Frost, Hafiz y Callaghan describieron un algoritmo de análisis de arriba hacia abajo que utiliza la memorización para refrenar los cálculos redundantes para acomodar cualquier forma de CFG ambiguo en tiempo polinomial (Θ(n4) para gramáticas recursivas a la izquierda y Θ(n3) para gramáticas no recursivas a la izquierda). Su algoritmo de análisis de arriba hacia abajo también requiere un espacio polinómico para árboles de análisis ambiguos potencialmente exponenciales mediante 'representación compacta' y 'agrupación de ambigüedades locales'. Su representación compacta es comparable con la representación compacta de Tomita de análisis ascendente.[12]​ Su uso de la memorización no solo se limita a recuperar los resultados previamente calculados cuando un analizador se aplica a una misma posición de entrada repetidamente (lo cual es esencial para el requisito de tiempo polinómico); Está especializado para realizar las siguientes tareas adicionales:

  • El proceso de memorización (que podría verse como un 'envoltorio' alrededor de cualquier ejecución de analizador) acomoda un análisis recursivo directo a la izquierda cada vez mayor al imponer restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual.
  • El procedimiento de 'búsqueda' de la tabla de notas del algoritmo también determina la reutilización de un resultado guardado al comparar el contexto computacional del resultado guardado con el contexto actual del analizador. Esta comparación contextual es la clave para acomodar la recursión izquierda indirecta (u oculta).
  • Cuando se realiza una búsqueda exitosa en un memotable (o tabla de notas), en lugar de devolver el conjunto de resultados completo, el proceso solo devuelve las referencias del resultado real y finalmente acelera el cálculo general.
  • Durante la actualización del memotable, el proceso de memorización agrupa los resultados ambiguos (potencialmente exponenciales) y garantiza el requisito de espacio polinómico.

Frost, Hafiz y Callaghan también describieron la implementación del algoritmo en PADL'08 como un conjunto de funciones de orden superior (llamadas combinadores de analizador sintáctico) en Haskell, que permite la construcción de especificaciones directamente ejecutables de CFG como procesadores de lenguaje. La importancia del poder de su algoritmo polinomial para acomodar 'cualquier forma de CFG ambiguo' con análisis de arriba hacia abajo es vital con respecto al análisis de sintaxis y semántica durante el procesamiento del lenguaje natural. El sitio X-SAIGA tiene más información sobre el algoritmo y los detalles de implementación.

Mientras Norvig aumentó el poder del analizador a través de la memorización, el analizador aumentado aún era tan complejo como el algoritmo de Earley, lo que demuestra un caso de uso de la memorización para algo más que la optimización de la velocidad. Johnson y Dörre[10]​ demuestran otra aplicación de memorización no relacionada con la velocidad: el uso de la memorización para retrasar la resolución de restricciones lingüísticas a un punto en un análisis donde se ha acumulado suficiente información para resolver esas restricciones. Por el contrario, en la aplicación de optimización de velocidad de la memorización, Ford demostró que la memorización puede garantizar que las gramáticas de análisis de expresión puedan analizarse en tiempo lineal, incluso en esos lenguajes que resultó en el peor comportamiento de retroceso.[11]​

Considere la siguiente gramática: 

S → (A c) | (B d)
A → X (a|b)
B → X b
X → x [X]

(Nota: en el ejemplo anterior, la producción S → (A c) | (B d) dice: "Una S es una A seguida de una c o una B seguida de una d ". La producción X → x [ X] dice "Una X es una x seguida de una X opcional ")

Esta gramática genera una de las siguientes tres variaciones de cadena: xac, xbc o xbd (donde x aquí se entiende que significa una o más x 's). A continuación, considere cómo esta gramática, utilizada como especificación de análisis, podría afectar a análisis de arriba a abajo, izquierda-derecha de la cadena xxxxxbd:

  • La regla A reconocerá xxxxxb (al descender primero en X para reconocer una x, y nuevamente descender a X hasta que se consuman todas las x, y luego reconocer la b), y luego regresa a la S, y no reconocer una c. La siguiente cláusula de S descenderá luego a B, que a su vez desciende nuevamente a X y reconoce las x por medio de muchas llamadas recursivas a X, y luego a b, y regresa a S y finalmente reconoce a d.

El concepto clave aquí es inherente a la frase desciende de nuevo en X. El proceso de mirar hacia adelante, fallar, retroceder y luego volver a intentar la siguiente alternativa se conoce en análisis como retroceso, y es principalmente el retroceso que presenta oportunidades para la memorización en el análisis. Considere una función RuleAcceptsSomeInput (Rule, Position, Input), donde los parámetros son los siguientes:

  • Rule es el nombre de la regla bajo consideración.
  • Position es el desplazamiento actualmente bajo consideración en la entrada.
  • Input es la entrada bajo consideración.

Deje que el valor de retorno de la función RuleAcceptsSomeInputsea ​​la longitud de la entrada aceptada por Rule, o 0 si esa regla no acepta ninguna entrada en ese desplazamiento en la cadena. En un escenario de retroceso con dicha memorización, el proceso de análisis es el siguiente:

  • Cuando la regla A desciende en X en la posición 0, se memoiza la longitud 5 contra esa posición y la regla X. Después de haber fallado en d, B entonces, en lugar de descender nuevamente a X, consulta la posición 0 contra la regla X en el motor de memorización, y se devuelve una longitud de 5, ahorrando así tener que descender nuevamente a X, y continúa como si hubiera descendido a X tantas veces como antes.

En el ejemplo anterior, pueden ocurrir uno o varios descensos en X, lo que permite cadenas como xxxxxxxxxxxxxxxxbd. De hecho, puede haber cualquier número de x antes de la b. Mientras que la llamada a S debe descender recursivamente a X tantas veces como haya x, B nunca tendrá que descender a X en absoluto, ya que el valor de retorno de RuleAcceptsSomeInput (X, 0, xxxxxxxxxxxxxxxxbd) será 16 (en este caso particular).

Los analizadores que hacen uso de predicados sintácticos también pueden memoizar los resultados de los análisis de predicados, reduciendo así construcciones como: 

S → (A)? A
A → /* some rule */

a un descenso en A.

Si un analizador construye un árbol de análisis durante un análisis, debe memorizar no solo la longitud de la entrada que coincide en algún desplazamiento con una regla determinada, sino que también debe almacenar el subárbol generado por esa regla en ese desplazamiento en la entrada, ya que las llamadas posteriores a la regla por parte del analizador no descenderán y reconstruirán ese árbol. Por la misma razón, los algoritmos analizadores memorizados que generan llamadas a código externo (a veces llamado rutina de acción semántica) cuando una regla coincide debe usar algún esquema para garantizar que dichas reglas se invoquen en un orden predecible.

Dado que, para cualquier analizador con capacidad de predicado sintáctico o de retroceso dado, no toda gramática necesitará retrocesos o comprobaciones de predicado, la sobrecarga de almacenar los resultados de análisis de cada regla contra cada desplazamiento en la entrada (y almacenar el árbol de análisis si el proceso de análisis lo hace implícitamente) en realidad ralentizar un analizador. Este efecto puede mitigarse mediante la selección explícita de esas reglas que el analizador memoizará.[13]​

Véase también[editar]

References[editar]

  1. ↑ a b c d Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1, pp. 91–98, March 1991.
  2. ↑ Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009.
  3. ↑ Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19–22, 1968.
  4. ↑ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.), pp. 128–142, Volterra, Italy, 2–4 September 1992.
  5. ↑ Mayfield, James, et al., Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems, Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95), pp. 87-93, 1995.
  6. ↑ Frost, Richard. and Szydlowski, Barbara. "Memoizing Purely Functional Top-Down Backtracking Language Processors. " "Sci. Comput. Program. " 1996 – 27(3): 263–288.
  7. ↑ Frost, Richard. "Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers. " "SIGPLAN Notices" 29(4): 23–30.
  8. ↑ Frost, Richard. "Monadic Memoization towards Correctness-Preserving Reduction of Search. " "Canadian Conference on AI 2003." p 66-80.
  9. ↑ Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3, pp. 405–417, September 1995.
  10. ↑ a b Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.
  11. ↑ a b Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.
  12. ↑ Tomita, Masaru. “Efficient Parsing for Natural Language.” Kluwer, Boston, MA, 1985.
  13. ↑ Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana, pp. 14–25, 15–17 January 2003.

Enlaces externos[editar]

Ejemplos de memoización en varios lenguajes de programación


[[Categoría:Optimización de software]] [[Categoría:Rendimiento de computadoras]]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Usuario:Edgard_MV/Taller&oldid=127873479»