优化Lisp递归随机游走

该函数导致堆栈溢出超过大约2000步，有什么方法可以轻松优化它以使用更少的内存吗？优化Lisp递归随机游走

(defun randomwalk (steps state) 
(displaystate state) 
(if (equal steps 0) nil 
     (if (solved? state) t 
      (let ((nrmlstate (normalize state))) 
       (randomwalk (- steps 1) (applymove nrmlstate (nth (random 
(length (getallmoves nrmlstate))) (getallmoves nrmlstate)))) 
      ) 
     ) 
    ) 
)

来源

2017-10-20 Ross Griebenow

您可能希望通过更好的代码格式和可重复的测试用例来改善您的问题。看到这个Stackoverflow帮助：https://stackoverflow.com/help/mcve –

正如Rainer所说，你的代码的格式非常糟糕，很难看到它的作用（缺少一个测试用例也无济于事），但是在大多数实现中（但是*不*由语言保证）编译这个函数应该导致一个不消耗堆栈的进程。（有些实现可能不需要编译步骤，甚至是。） – tfb

它看起来像你只，这意味着你可以很容易地重写它不是在所有尾递归调用位置：

(defun randomwalk (steps state) 
    (loop :if (= steps 0)  
      :do (return nil) 
     :if (solved? state) 
      :do (return t) 
     :else 
      :do (let* ((nrmlstate (normalize state)) 
         (moves (getallmoves nrmlstate)) 
         (random-move (nth (random (length moves)) moves))) 
        (setf state (applymove nrmlstate random-move)) 
        (decf steps))))

因为我没有使用我的功能除了基本情况以外，未能对其进行测试。

来源

2017-10-20 20:58:43 Sylwester

我曾希望保持它纯粹的功能，但这是有效的！我与gnu clisp卡在一起，并且尽可能没有办法增加内存限制或使clisp执行尾递归优化。 –

@RossGriebenow我认为Clisp有tail调用优化功能，所以如果你编译这个函数，你将不会再得到堆栈溢出，但是由于Common Lisp标准并不需要实现这个功能，甚至可以考虑标准中的任何优化提示，他们在便携式应用程序。因此，在CL中进行函数式编程的惯用方式是通过线性更新。这样，只要界面有效，就可以在内部进行变异。 – Sylwester

@RossGriebenow BTW堆栈大小的增加取决于系统，但CLISP常见问题解答针对递归提供了[堆栈增加unix和windows的解决方案]（https://clisp.sourceforge.io/impnotes/faq.html#faq-stack）不能被编译或重写。 – Sylwester

优化Lisp递归随机游走

回答

相关问题