Как мне заменить рекурсивную функцию в Lisp?

Ответ 1

Я предполагаю, что вы используете Common- Lisp, у которого есть отдельные пространства имен для имен переменных и функций. Чтобы memoize функцию, названную символом, вам необходимо изменить ее привязку к функциям с помощью функции 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))

Ответ 2

что-то вроде этого:

(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: ваша оригинальная (не memoized) функция анонимна, и вы даете только имя для его memoizing.

Ответ 3

Вот функция memoize, которая возвращает функцию символа:

(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)))))))

Затем вы сделали бы что-то вроде этого:

(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)

Я оставлю это для вас, чтобы сделать функцию unmemoize.

Ответ 4

Обратите внимание на несколько вещей:

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

Выше - это функция, которая имеет вызов для себя.

В Common Lisp компилятор файлов может предположить, что FOO не изменяется. Он НЕ будет вызывать обновленный FOO позже. Если вы измените привязку функции FOO, тогда вызов исходной функции по-прежнему будет идти к старой функции.

Так что память в саморекурсивной функции НЕ будет работать в общем случае. Особенно если вы используете хороший компилятор.

Вы можете обойти это, чтобы всегда проходить через символ: (funcall 'foo 3)

(DEFVAR...) - форма верхнего уровня. Не используйте его внутри функций. Если вы объявили переменную, установите ее позже с помощью SETQ или SETF.

Для вашей проблемы я бы просто использовал хеш-таблицу для хранения промежуточных результатов.

Ответ 5

Эта функция точно соответствует тому, что Питер Норвиг дает в качестве примера функцию, которая кажется хорошим кандидатом на мемонирование, но это не так.

См. рисунок 3 (функция "Hailstone" ) его оригинальной статьи по мемуаризации ( "Использование автоматической напоминания в качестве инструмента разработки программного обеспечения в реальных системах AI" ).

Итак, я предполагаю, что даже если вы заработаете механику работы с memoization, в этом случае это не ускорит ее.

Ответ 6

Изменение "оригинальной" функции необходимо, потому что, как вы говорите, нет другого способа для рекурсивного вызова (-ов), чтобы быть обновленным для вызова memoized версии.

К счастью, способ lisp заключается в том, чтобы найти функцию по имени каждый раз, когда ее нужно вызвать. Это означает, что достаточно заменить привязку функции memoized версией функции, так что рекурсивные вызовы будут автоматически искать и возвращаться через memoization.

huaiyuan code показывает ключевой шаг:

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

Этот трюк также работает в Perl. Однако на языке, подобном C, memoized версия функции должна быть закодирована отдельно.

Некоторые реализации lisp предоставляют систему под названием "совет", которая предоставляет стандартизованную структуру для замены функций с помощью расширенных версий. В дополнение к функциональным обновлениям, таким как memoization, это может быть чрезвычайно полезно при отладке, вставляя отладочные отпечатки (или полностью останавливаясь и предоставляя продолжение) без изменения исходного кода.

Ответ 7

Некоторое время назад я написал небольшую процедуру memoization для Схемы, которая использовала цепочку замыканий для отслеживания сохраненного состояния:

(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))))))

Это нужно использовать так:

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

Я уверен, что это можно с легкостью портировать на ваш любимый лексически ограниченный Lisp вкус.

Ответ 8

Я бы, наверное, сделал что-то вроде:

(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)))))))))

Это нехорошо и функционально, но тогда это не так много хлопот, и это действительно работает. Недостатком является то, что вы не получаете удобную версию без исправления для проверки и очистки кеша, граничащего с "очень сложным".