Como faço para memoize uma função recursiva em Lisp?

Question

Eu sou um novato Lisp. Estou tentando memoize uma função recursiva para calcular o número de termos em um Collatz seqüência (para problema 14 em Projeto Euler ). Meu código até o momento é a seguinte:

(defun collatz-steps (n)
  (if (= 1 n) 0
       (if (evenp n) 
           (1+ (collatz-steps (/ n 2)))
           (1+ (collatz-steps (1+ (* 3 n)))))))

(defun p14 ()
  (defvar m-collatz-steps (memoize #'collatz-steps))
  (let 
      ((maxsteps (funcall m-collatz-steps 2))
       (n 2)
       (steps))
    (loop for i from 1 to 1000000
          do 
          (setq steps (funcall m-collatz-steps i))
          (cond 
            ((> steps maxsteps) 
             (setq maxsteps steps)
             (setq n i))
            (t ())))
    n))


(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind 
              (result exists)
            (gethash args cache)
          (if exists
              result
              (setf (gethash args cache)
                    (apply fn args)))))))

A função memoize é o mesmo que o dado no On Lisp reservar.

Este código não realmente dar qualquer aceleração em comparação com a versão não-memoized. Eu acredito que é devido às chamadas recursivas chamando a versão não-memoized da função, que tipo de derrotas a finalidade. Nesse caso, qual é a maneira correta de fazer o memoization aqui? Existe alguma maneira de ter todas as chamadas para a função original chamar a própria versão memoized, eliminando a necessidade do símbolo especial m-Collatz-passos?

EDIT: Corrigido o código para ter

(defvar m-collatz-steps (memoize #'collatz-steps))

que é o que eu tinha no meu código. Antes da edição que eu tinha erroneamente colocar:

(defvar collatz-steps (memoize #'collatz-steps))

Vendo que erro me deu uma outra idéia, e eu tentei usar esta última em si defvar e mudando as chamadas recursivas para

       (1+ (funcall collatz-steps (/ n 2)))
       (1+ (funcall collatz-steps (1+ (* 3 n))))

Este parece realizar a memoization (aceleração de cerca de 60 segundos para 1,5 segundos), mas exige a mudança da função original. Existe uma solução mais limpa que não envolve alterar a função original?

Answer 1

Eu suponho que você está usando Common-Lisp, que tem namespaces separados para nomes de variáveis ??e função. A fim de memoize a função nomeada por um símbolo, você precisa mudar a sua função de ligação, através do assessor `fdefinition ':

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

(defun p14 ()
  (let ((mx 0) (my 0))
    (loop for x from 1 to 1000000
          for y = (collatz-steps x)
          when (< my y) do (setf my y mx x))
    mx))

Answer 2

algo como isto:

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

IOW:. A sua função original (não-memoized) é anônimo, e só dê um nome para o resultado de memoizing it

Answer 3

Aqui está uma função memoize que religa a função de símbolo:

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

Você deve então fazer algo parecido com isto:

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

Eu vou deixá-la até que você faça uma função unmemoize.

Answer 4

Alterar a função "original" é necessário, porque, como você diz, não há outro caminho para a chamada recursiva (s) a ser atualizado para chamar a versão memoized.

Felizmente, o caminho lisp obras é encontrar a função pelo nome cada vez que precisa ser chamado. Isto significa que é suficiente para substituir a ligação com a versão memoized da função de função, para que as chamadas recursiva irá procurar automaticamente e reentrar através da memoization.

mostra o código de Huaiyuan o passo fundamental:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

Este truque também funciona em Perl. Em uma linguagem como C, no entanto, uma versão memoized de uma função devem ser codificadas separadamente.

Algumas implementações Lisp fornecer um sistema chamado "conselho", que fornece uma estrutura padronizada para substituir funções com versões melhoradas de si mesmos. Além de atualizações funcionais como memoization, isso pode ser extremamente útil na depuração através da inserção de depuração imprime (ou parar completamente e dando um prompt continuable) sem modificar o código original.

Answer 5

Observe algumas coisas:

(defun foo (bar)
   ... (foo 3) ...)

Acima é uma função que tem uma chamada para si.

Em Common Lisp o compilador arquivo pode assumir que FOO não muda. Ele não vai chamar um FOO atualizadas mais tarde. Se alterar a ligação do FOO função, então a chamada da função original ainda irá para a função de idade.

Então memoizing uma função recursiva auto não vai funcionar no caso geral. Especialmente se você estiver usando um bom compilador.

Você pode trabalhar em torno dele para ir sempre através do símbolo por exemplo: (funcall 'foo 3)

(DefVar ...) é uma forma de nível superior. Não usá-lo dentro de funções. Se você declarou uma variável, defina-o com SETQ ou SETF mais tarde.

Para o seu problema, eu tinha acabado de usar uma tabela hash para armazenar os resultados intermediários.

Answer 6

Esta função é exatamente o que Peter Norvig dá como exemplo de uma função que parece ser um bom candidato para memoization, mas que não é.

Veja a figura 3 (a função 'Granizo') do seu papel original na memoization ( "Usando Memoização automático como uma ferramenta de engenharia de software no mundo real Sistemas AI").

Então, eu estou supondo que, mesmo se você começar a mecânica de funcionamento memoization, não vai realmente acelerá-lo neste caso.

Answer 7

Um tempo atrás eu escrevi um pequeno rotina memoization de esquema que usou uma cadeia de encerramentos para acompanhar o estado memoized:

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

Isso precisa ser usado assim:

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

Eu tenho certeza de que isso pode ser portado para o seu sabor Lisp escopo léxico favorito com facilidade.

Answer 8

Eu provavelmente faria algo como:

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

Não é agradável e funcional, mas, então, não é muito incômodo e ela não funciona. Desvantagem é que você não obter uma versão unmemoized útil para teste com e limpar o cache é na fronteira com "muito difícil".