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

Question

Я новичок в Лиспе. Я пытаюсь запомнить рекурсивную функцию для вычисления количества членов в последовательности Коллатца (для задачи 14 в Project Euler ). Мой код на данный момент:

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

Функция памятки та же, что и в книге на Лиспе .

Этот код фактически не дает никакого ускорения по сравнению с незаписанной версией. Я полагаю, что это происходит из-за рекурсивных вызовов, вызывающих незарегистрированную версию функции, что в некоторой степени противоречит цели. В таком случае, как правильно сделать памятку здесь? Есть ли способ, чтобы все вызовы исходной функции вызывали саму запомненную версию, устраняя необходимость в специальном символе m-collatz-steps?

РЕДАКТИРОВАТЬ: исправил код, чтобы иметь

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

что и было в моем коде. Перед правкой я ошибочно поставил:

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

Увидев эту ошибку, у меня появилась другая идея, и я попытался использовать этот последний дефвар и изменить рекурсивные вызовы на

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

Похоже, что это выполняет запоминание (ускорение от 60 секунд до 1,5 секунд), но требует изменения исходной функции. Есть ли более чистое решение, которое не предполагает изменения первоначальной функции?

Answer 1

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

как то так:

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

Answer 3

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

См. Рисунок 3 (функция «Град») его оригинальной статьи о запоминании («Использование автоматической запоминания как инструмента разработки программного обеспечения в реальных системах ИИ»).

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

Необходимо изменить «оригинальную» функцию, потому что, как вы говорите, рекурсивный вызов (вызовы) не может быть обновлен для вызова запомненной версии.

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

Код Хуайюаня показывает ключевой шаг:

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

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

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