Как мне запомнить рекурсивную функцию в Лиспе?
https://stackoverflow.com/questions/256507
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я новичок в Лиспе. Я пытаюсь запомнить рекурсивную функцию для вычисления количества терминов в последовательности Коллатца (для проблема 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)))))))
Решение
Я предполагаю, что вы используете 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))
Другие советы
что-то вроде этого:
(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: ваша оригинальная (незапамятная) функция является анонимной, и вы даете имя только результату ее запоминания.
Вот функция памятки, которая связывает функцию символа:
(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.
Изменение " оригинала " функция необходима, потому что, как вы говорите, рекурсивный вызов (вызовы) не может быть обновлен для вызова запомненной версии.
К счастью, lisp работает так, чтобы каждый раз вызывать функцию по имени . Это означает, что достаточно заменить привязку функции запомненной версией функции, чтобы рекурсивные вызовы автоматически просматривали и повторно вводили памятку.
код huaiyuan показывает ключевой шаг:
(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))
Этот трюк также работает в Perl. Однако на языке, подобном C, запомненная версия функции должна кодироваться отдельно.
Некоторые реализации lisp предоставляют систему под названием "advice", которая предоставляет стандартизированную структуру для замены функций улучшенными версиями самих себя. В дополнение к функциональным обновлениям, таким как запоминание, это может быть чрезвычайно полезно при отладке, вставляя отладочные отпечатки (или полностью останавливая и давая непрерывное приглашение) без изменения исходного кода.
Обратите внимание на несколько вещей:
(defun foo (bar)
... (foo 3) ...)
Выше приведена функция, которая вызывает сама себя.
В Common Lisp файловый компилятор может предполагать, что FOO не изменяется. Это не вызовет обновленный FOO позже. Если вы измените привязку функции FOO, то вызов исходной функции все равно перейдет к старой функции.
Таким образом, запоминание саморекурсивной функции НЕ будет работать в общем случае. Особенно если вы используете хороший компилятор.
Вы можете обойти это, чтобы всегда проходить через символ, например: (funcall 'foo 3)
(DEFVAR ...) - это форма верхнего уровня. Не используйте его внутри функций. Если вы объявили переменную, установите ее позже с помощью SETQ или SETF.
Для вашей проблемы я бы просто использовал хеш-таблицу для хранения промежуточных результатов.
Эта функция - именно то, что дает Питер Норвиг в качестве примера функции, которая кажется хорошим кандидатом на запоминание, но это не так.
См. рис. 3 (функция 'Hailstone') его оригинальной статьи о запоминании ("Использование автоматической запоминания как инструмента разработки программного обеспечения в реальных системах ИИ").
Так что я предполагаю, что даже если вы запустите механику запоминания, это в действительности не ускорит это.
Некоторое время назад я написал небольшую процедуру запоминания для 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.
Я бы, наверное, сделал что-то вроде:
(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)))))))))
Это не Ницца и Функционально, но, тем не менее, это не очень хлопотно, и это работает. Недостатком является то, что у вас нет удобной неметозированной версии для тестирования, а очистка кэша граничит с «очень трудно».
