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

18

Я начинающий Лисп. Я пытаюсь memoize рекурсивную функцию для вычисления количества терминов в последовательности Collatz (для проблемы 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)))))))

Функция memoize такая же, как и в на Lisp .

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

EDIT: Исправлен код для

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

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

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

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

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

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

задан sundar 02.11.2008 в 05:35
источник

8 ответов

10

Я предполагаю, что вы используете 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))
    
ответ дан huaiyuan 02.11.2008 в 20:11
  • Это будет работать, если вы вызвали setf после определения функции –  Eric Normand 03.11.2008 в 20:37
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.

    
ответ дан Javier 02.11.2008 в 06:18
  • Да, это делает его более ясным, но я думаю, что вы должны использовать defun macro: (defun collatz-steps (n) (memoize # '(лямбда (x) и т. д.) n)) –  Svante 02.11.2008 в 20:41
1

Вот функция 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.

    
ответ дан Eric Normand 03.11.2008 в 20:46
  • проблема: рекурсивный вызов обычно не изменяется путем установки символьной функции. –  Rainer Joswig 16.08.2010 в 20:04
  • В вашем коде есть следующие проблемы: 1. неопределенная переменная: FN 2. missing ')' –  dknight 15.03.2014 в 11:35
  • Этот код не работает (fn несвязано). С удовольствием вернемся к +1, если это исправлено, конечно. –  Clément 26.01.2017 в 17:16
1

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

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

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

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

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

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

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

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

    
ответ дан Rainer Joswig 06.03.2010 в 19:36
1

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

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

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

    
ответ дан user421879 16.08.2010 в 17:19
0

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

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

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

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

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

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

    
ответ дан jonrock 21.11.2008 в 05:58
  • Нет, Common Lisp не находит функцию по имени каждый раз. Хороший компилятор будет генерировать код, который вызывает функцию напрямую. Это также описано в стандарте ANSI CL. –  Rainer Joswig 06.03.2010 в 19:39
0

Некоторое время назад я написал небольшую процедуру 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.

    
ответ дан Kyle Cronin 21.11.2008 в 06:13
0

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

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

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

    
ответ дан Vatine 06.03.2010 в 18:33