Memoização - Memoization

Em computação , memoization ou memoisation é uma otimização técnica utilizada principalmente para acelerar programas de computador , armazenando os resultados de caras chamadas de função e retornando o resultado em cache quando as mesmas entradas ocorrer novamente. Memoização também foi usada em outros contextos (e para outros fins que não ganhos de velocidade), como na análise descendente mutuamente recursiva simples . Embora relacionada ao armazenamento em cache , a memoização se refere a um caso específico dessa otimização, distinguindo-a das formas de armazenamento em cache, como armazenamento em buffer ou substituição de página . No contexto de algumas linguagens de programação lógica , memoização também é conhecida como tabling .

Etimologia

O termo "memoização" foi cunhado por Donald Michie em 1968 e é derivado da palavra latina " memorando " ("para ser lembrado"), geralmente truncado como "memo" no inglês americano e, portanto, carrega o significado de "girando [o resultados de] uma função em algo a ser lembrado ". Enquanto "memoização" pode ser confundida com " memorização " (porque são cognatos etimológicos ), "memoização" tem um significado especializado em computação.

Visão geral

Uma função memoized "lembra" os resultados correspondentes a algum conjunto de entradas específicas. Chamadas subsequentes com entradas lembradas retornam o resultado lembrado em vez de recalculá-lo, eliminando assim o custo primário de uma chamada com parâmetros fornecidos de todos, exceto a primeira chamada feita para a função com esses parâmetros. O conjunto de associações lembradas pode ser um conjunto de tamanho fixo controlado por um algoritmo de substituição ou um conjunto fixo, dependendo da natureza da função e de seu uso. Uma função só pode ser memorizada se for referencialmente transparente ; ou seja, apenas se chamar a função tiver exatamente o mesmo efeito que substituir essa chamada de função por seu valor de retorno. (No entanto, existem exceções de casos especiais a essa restrição.) Embora relacionado a tabelas de pesquisa , uma vez que a memoização geralmente usa tais tabelas em sua implementação, a memoização preenche seu cache de resultados de forma transparente durante o processo, conforme necessário, em vez de antecipadamente.

Memoização é uma maneira de reduzir o custo de tempo de uma função em troca de custo de espaço ; isto é, as funções memorizadas tornam-se otimizadas para velocidade em troca de um maior uso do espaço da memória do computador . O "custo" de tempo / espaço dos algoritmos tem um nome específico na computação: complexidade computacional . Todas as funções têm uma complexidade computacional no tempo (ou seja, levam tempo para serem executadas) e no espaço .

Embora ocorra uma compensação de espaço-tempo (ou seja, espaço usado é ganho de velocidade), isso difere de algumas outras otimizações que envolvem compensação de tempo-espaço, como redução de força , em que a memoização é um tempo de execução em vez de tempo de compilação otimização. Além disso, a redução de resistência potencialmente substitui uma operação cara, como a multiplicação, por uma operação menos cara, como a adição, e os resultados na economia podem ser altamente dependentes da máquina (não portátil entre máquinas), enquanto a memoização é um método cruzado mais independente da máquina estratégia de plataforma .

Considere a seguinte função de pseudocódigo para calcular o fatorial 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 inteiro n tal que n ≥ 0, o resultado final da função factorialé invariante ; se invocado como x = factorial(3), o resultado é tal que x será sempre atribuído ao valor 6. A implementação não memoizada acima, dada a natureza do algoritmo recursivo envolvido, exigiria n + 1 invocações de factorialpara chegar a um resultado, e cada um de essas invocações, por sua vez, têm um custo associado no tempo que a função leva para retornar o valor calculado. Dependendo da máquina, esse custo pode ser a soma de:

  1. O custo para configurar o quadro de pilha de chamadas funcional.
  2. O custo para comparar n com 0.
  3. O custo para subtrair 1 de n .
  4. O custo para configurar o quadro de pilha de chamadas recursivo. (Como acima.)
  5. O custo para multiplicar o resultado da chamada recursiva para factorialpor n .
  6. O custo para armazenar o resultado de retorno para que possa ser usado pelo contexto de chamada.

Em uma implementação não memoized, cada chamada de nível superior para factorialinclui o custo cumulativo das etapas 2 a 6 proporcional ao valor inicial de n .

A factorialseguir, uma versão memorizada da função:

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

Neste exemplo específico, se factorialfor invocado primeiro com 5 e, em seguida, invocado posteriormente com qualquer valor menor ou igual a cinco, esses valores de retorno também terão sido memorizados, uma vez factorialque terão sido chamados recursivamente com os valores 5, 4, 3, 2, 1 e 0, e os valores de retorno para cada um deles terão sido armazenados. Se for então chamada com um número maior que 5, como 7, apenas 2 chamadas recursivas serão feitas (7 e 6), e o valor para 5! terá sido armazenado na chamada anterior. Desta forma, a memoização permite que uma função se torne mais eficiente em termos de tempo quanto mais vezes é chamada, resultando assim em uma eventual aceleração geral.

Algumas outras considerações

Programação funcional

Memoização é muito usada em compiladores para linguagens de programação funcionais , que freqüentemente usam estratégia de avaliação de chamada por nome . Para evitar sobrecarga com o cálculo de valores de argumento, os compiladores dessas linguagens usam intensamente funções auxiliares chamadas thunks para calcular os valores de argumento e memorizar essas funções para evitar cálculos repetidos.

Memoização automática

Embora a memoização possa ser adicionada às funções interna e explicitamente por um programador de computador da mesma maneira que a versão memoizada acima factorialé implementada, as funções referencialmente transparentes também podem ser automaticamente memoizadas externamente . As técnicas empregadas por Peter Norvig têm aplicação não apenas no Common Lisp (a linguagem em que seu artigo demonstrou memoização automática), mas também em várias outras linguagens de programação . Aplicações de memoização automática também foram formalmente exploradas no estudo de reescrita de termos e inteligência artificial .

Em linguagens de programação em que as funções são objetos de primeira classe (como Lua , Python ou Perl ), a memoização automática pode ser implementada substituindo (em tempo de execução) uma função por seu valor calculado, uma vez que um valor tenha sido calculado para um determinado conjunto de parâmetros. A função que faz essa substituição de objeto de valor para função pode envolver genericamente qualquer função referencialmente transparente. Considere o seguinte pseudocódigo (onde se presume que as funções são valores de primeira classe):

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 chamar uma versão memorizada automaticamente do factorialuso da estratégia acima, em vez de chamar factorialdiretamente, o código invoca . Cada uma dessas chamadas verifica primeiro se uma matriz de titular foi alocada para armazenar os resultados e, se não, anexa essa matriz. Se nenhuma entrada existir na posição (onde são usadas como a chave do array associativo), uma chamada real é feita para com os argumentos fornecidos. Finalmente, a entrada na matriz na posição-chave é retornada ao chamador. memoized-call(factorial(n))values[arguments]argumentsfactorial

A estratégia acima requer agrupamento explícito em cada chamada para uma função que deve ser memoizada. Nessas línguas que permitem fechamentos , memoization pode ser efectuada de forma implícita através de um functor fábrica que retorna um objeto de função memoized envolto em um padrão de decorador . Em pseudocódigo, isso pode ser expresso da seguinte forma:

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

Em vez de chamar factorial, um novo objeto de função memfacté criado da seguinte maneira:

 memfact = construct-memoized-functor(factorial)

O exemplo acima assume que a função factorialjá foi definida antes da chamada para construct-memoized-functorser feita. Deste ponto em diante, é chamado sempre que o fatorial de n é desejado. Em linguagens como Lua, existem técnicas mais sofisticadas que permitem que uma função seja substituída por uma nova função com o mesmo nome, o que permitiria: memfact(n)

 factorial = construct-memoized-functor(factorial)

Essencialmente, tais técnicas envolvem anexar o objeto de função original ao functor criado e encaminhar chamadas para a função original sendo memoizada por meio de um alias quando uma chamada para a função real é necessária (para evitar recursão infinita ), conforme ilustrado abaixo:

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

(Nota: Algumas das etapas mostradas acima podem ser gerenciadas implicitamente pela linguagem de implementação e são fornecidas para ilustração.)

Analisadores

Quando um analisador descendente tenta analisar uma entrada ambígua em relação a uma gramática livre de contexto ambígua (CFG), pode ser necessário um número exponencial de etapas (com relação ao comprimento da entrada) para tentar todas as alternativas do CFG para produzir todas as árvores de análise sintática possíveis. Isso eventualmente exigiria espaço de memória exponencial. Memoização foi explorada como uma estratégia de análise em 1991 por Peter Norvig, que demonstrou que um algoritmo semelhante ao uso de programação dinâmica e conjuntos de estados no algoritmo de Earley (1970) e tabelas no algoritmo CYK de Cocke, Younger e Kasami, poderia ser gerado pela introdução de memoização automática para um analisador descendente recursivo de retrocesso simples para resolver o problema de complexidade de tempo exponencial. A ideia básica na abordagem de Norvig é que quando um analisador é aplicado à entrada, o resultado é armazenado em um memotable para reutilização subsequente se o mesmo analisador for reaplicado à mesma entrada. Richard Frost também usou a memoização para reduzir a complexidade de tempo exponencial dos combinadores de analisador , que podem ser vistos como uma técnica de análise "Purely Functional Top-Down Backtracking". Ele mostrou que combinadores básicos de analisador memoized podem ser usados ​​como blocos de construção para construir analisadores complexos como especificações executáveis ​​de CFGs. Foi novamente explorado no contexto da análise em 1995 por Johnson e Dörre. Em 2002, foi examinado em profundidade considerável pela Ford na forma chamada análise de packrat .

Em 2007, Frost, Hafiz e Callaghan descreveram um algoritmo de análise de cima para baixo que usa memoização para refinar cálculos redundantes para acomodar qualquer forma de CFG ambígua em tempo polinomial ( Θ (n 4 ) para gramáticas recursivas à esquerda e Θ (n 3 ) para gramáticas não recursivas à esquerda). Seu algoritmo de análise de cima para baixo também requer espaço polinomial para árvores de análise ambíguas potencialmente exponenciais por 'representação compacta' e 'agrupamento de ambiguidades locais'. Sua representação compacta é comparável à representação compacta de análise de baixo para cima do Tomita . Seu uso de memoização não se limita apenas a recuperar os resultados calculados anteriormente quando um analisador é aplicado a uma mesma posição de entrada repetidamente (o que é essencial para o requisito de tempo polinomial); é especializado para realizar as seguintes tarefas adicionais:

  • O processo de memoização (que pode ser visto como um 'invólucro' em torno de qualquer execução do analisador) acomoda uma análise recursiva à esquerda direta cada vez maior , impondo restrições de profundidade com respeito ao comprimento de entrada e posição de entrada atual.
  • O procedimento de 'pesquisa' da memo-table do algoritmo também determina a capacidade de reutilização de um resultado salvo, comparando o contexto computacional do resultado salvo com o contexto atual do analisador. Essa comparação contextual é a chave para acomodar a recursão esquerda indireta (ou oculta) .
  • Ao realizar uma pesquisa bem-sucedida em um memotable, em vez de retornar o conjunto de resultados completo, o processo apenas retorna as referências do resultado real e, eventualmente, acelera o cálculo geral.
  • Durante a atualização do memotable, o processo de memoização agrupa os resultados ambíguos (potencialmente exponenciais) e garante o requisito de espaço polinomial.

Frost, Hafiz e Callaghan também descreveram a implementação do algoritmo em PADL'08 como um conjunto de funções de ordem superior (chamadas de combinadores de analisadores ) em Haskell , que permite a construção de especificações executáveis ​​diretamente de CFGs como processadores de linguagem. A importância do poder de seu algoritmo polinomial para acomodar 'qualquer forma de CFG ambígua' com análise de cima para baixo é vital com relação à sintaxe e análise semântica durante o processamento de linguagem natural . O site X-SAIGA tem mais informações sobre o algoritmo e detalhes de implementação.

Enquanto Norvig aumentava o poder do analisador por meio de memoização, o analisador aumentado ainda era tão complexo quanto o algoritmo de Earley, o que demonstra um caso de uso de memoização para algo diferente da otimização de velocidade. Johnson e Dörre demonstram outra aplicação de memoização não relacionada à velocidade: o uso de memoização para atrasar a resolução de restrições linguísticas a um ponto em uma análise onde informações suficientes foram acumuladas para resolver essas restrições. Por outro lado, na aplicação de otimização de velocidade de memoização, Ford demonstrou que a memoização poderia garantir que a análise gramatical de expressões poderia analisar em tempo linear até mesmo aquelas linguagens que resultaram no pior caso de comportamento de retrocesso.

Considere a seguinte gramática :

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

(Nota de notação: no exemplo acima, a produção S → (A c ) | (B d ) diz: "Um S é um A seguido por a c ou um B seguido por um d ." A produção X → x [ X] diz "Um X é um x seguido por um X opcional .")

Esta gramática gera uma das três variações de string a seguir : xac , xbc ou xbd (onde x aqui é entendido como um ou mais x 's .) Em seguida, considere como essa gramática, usada como uma especificação de análise, pode afetar um análise de cima para baixo, esquerda-direita da string xxxxxbd :

A regra A reconhecerá xxxxxb (primeiro descendo em X para reconhecer um x , e novamente descendo em X até que todos os x sejam consumidos e, em seguida, reconhecerá b ) e, em seguida, retornará a S e não reconhecerá um c . A próxima cláusula de S então descerá para B, que por sua vez novamente desce para X e reconhece os x por meio de muitas chamadas recursivas para X , e então a b , e retorna para S e finalmente reconhece a d .

O conceito chave aqui é inerente a frase desce novamente em X . O processo de olhar para frente, falhar, fazer backup e, em seguida, tentar novamente a próxima alternativa é conhecido na análise como retrocesso, e é principalmente o retrocesso que apresenta oportunidades para memoização na análise. Considere uma função RuleAcceptsSomeInput(Rule, Position, Input), onde os parâmetros são os seguintes:

  • Rule é o nome da regra em consideração.
  • Position é a compensação atualmente em consideração na entrada.
  • Input é a entrada em consideração.

Deixe o valor de retorno da função RuleAcceptsSomeInputser o comprimento da entrada aceita por Rule, ou 0 se essa regra não aceitar nenhuma entrada naquele deslocamento da string. Em um cenário de retrocesso com tal memoização, o processo de análise é o seguinte:

Quando a regra A desce em X no deslocamento 0, que memoizes o comprimento 5 contra que a posição e a regra X . Depois de ter falhado em d , B então, ao invés de descer novamente para X , consulta a posição 0 contra a regra X no mecanismo de memoização e é retornado com um comprimento de 5, evitando assim ter que realmente descer novamente para X , e continua como se tivesse descido para X tantas vezes quanto antes.

No exemplo acima, uma ou mais descidas em X podem ocorrer, permitindo strings como xxxxxxxxxxxxxxxxbd . Na verdade, pode haver qualquer número de x antes de b . Enquanto a chamada para S deve descer recursivamente em X tantas vezes quanto há x , B nunca terá que descer em X, já que o valor de retorno de será 16 (neste caso particular). RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

Esses analisadores que fazem uso de predicados sintáticos também são capazes de memorizar os resultados de analisadores de predicado, reduzindo, assim, construções como:

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

a uma descida para A .

Se um analisador construir uma árvore de análise durante uma análise, ele deve memorizar não apenas o comprimento da entrada que corresponde a algum deslocamento em relação a uma determinada regra, mas também deve armazenar a subárvore que é gerada por aquela regra naquele deslocamento no entrada, uma vez que as chamadas subsequentes à regra pelo analisador não irão realmente descer e reconstruir essa árvore. Pela mesma razão, algoritmos de analisador memoized que geram chamadas para código externo (às vezes chamado de rotina de ação semântica ) quando uma regra coincide deve usar algum esquema para garantir que tais regras sejam invocadas em uma ordem previsível.

Uma vez que, para qualquer analisador capaz de retrocesso ou predicado sintático, nem toda gramática precisará de verificações de retrocesso ou predicado, a sobrecarga de armazenar os resultados da análise de cada regra em relação a cada deslocamento na entrada (e armazenar a árvore de análise se o processo de análise fizer isso implicitamente) pode realmente desacelera um analisador. Este efeito pode ser mitigado pela seleção explícita das regras que o analisador irá memorizar.

Veja também

Referências

links externos

Exemplos de memoização em várias linguagens de programação