優化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遞歸隨機遊走

回答

相關問題