вторник, 9 марта 2010 г.

Нерекурсивная реализация функции Аккермана

Тут возник вопрос как вычислить функцию Аккермана. Проблема в том, что непосредственная рекурсивная реализация данной функции очень активно потребляет стэк и вычислить её для каких-нибудь чуть более интересных числе (например m=3, n=15) не получается, так как CLisp или даже SBCL потребляют весь стэк и дело заканчивается плачевно. Рецепт лечения очевиден: необходимо переписать функцию без использования рекурсии. Что-то меня в этой задаче зацепило и я это родил (особо впечатлительным не смотреть):
 (defvar *akk-cache* nil)

(defun akk (x y)
(let ((*akk-cache* (or *akk-cache*
(make-hash-table :test 'equal)))
(stack `((,x ,y))))
(flet ((akk-cache (m n)
(gethash `(,m ,n) *akk-cache*))
(new-value (value)
(setf (gethash (car stack) *akk-cache*)
value)
(cond
((not stack) t)
((not (second stack))
(pop stack))
((second (second stack))
(pop stack))
(t (let ((m (first (car stack)))
(n (second (car stack)))
(i (first (second stack))))
(pop stack)
(pop stack)
(push (list i (gethash `(,m ,n) *akk-cache*))
stack))))))
(loop
while stack
do (let ((m (first (car stack)))
(n (second (car stack))))
(if (akk-cache m n)
(pop stack)
(cond ((= m 0)
(new-value (1+ n)))
((and (= n 0)
(akk-cache (1- m) 1))
(new-value (akk-cache (1- m) 1)))
((= n 0)
(push (list (1- m) 1)
stack))
((and (akk-cache m (1- n))
(akk-cache (1- m)
(akk-cache m (1- n))))
(new-value (akk-cache (1- m)
(akk-cache m (1- n)))))
((akk-cache m (1- n))
(push (list (1- m)
(akk-cache m (1- n)))
stack))
(t (push (list (1- m))
stack)
(push (list m (1- n))
stack))))))
(akk-cache x y))))
Выглядит страшновато, но работает :)

8 комментариев:

  1. А что, рекурсивный вариант даже в случае "хвостовой" рекурсии кушает стек? O_o

    ОтветитьУдалить
  2. Хм, сейчас посмотрел собственно функцию (да-да, по ссылке сначало не прошел :))... интересно, а ее в хвостовую рекурсию-то завернуть вообще можно... (ушел думать...)

    ОтветитьУдалить
  3. Нельзя, конечно, никакие TCO здесь не помогут.

    ОтветитьУдалить
  4. Интересно, что на это скажут Хаскеллисты?

    ОтветитьУдалить
  5. > Интересно, что на это скажут Хаскеллисты?

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

    ОтветитьУдалить
  6. можно, например, переписать ее в CPS стиле
    let ack_cps m n =
    let rec impl m n k =
    if m = 0I then k (n + 1I)
    else if m > 0I && n = 0I then impl (m - 1I) 1I k
    else impl m (n - 1I) (fun r ->
    impl (m - 1I) r k
    )
    impl m n id

    ОтветитьУдалить
  7. Я автор той темы на lisper.ru.
    Препод никогда еще не видел настолько заинтересованных студентов, которые вычисляли аккермана до 3 14 и 4 1. Теперь чуть больше - 3 15 еще получилось, а 3 16 - уже нет (2 ГБ ram).

    Еще раз спасибо archimag за помощь.

    ОтветитьУдалить
  8. > Теперь чуть больше - 3 15 еще получилось,
    > а 3 16 - уже нет

    Можно модифицировать данную реализацию, время от времени очищая стэк. Считать можно будет больше :)

    ОтветитьУдалить