8

Common Lisp 関数のパフォーマンスを理解するのに問題があります (私はまだ初心者です)。この関数には 2 つのバージョンがあり、指定された までのすべての整数の合計を単純に計算しますn。

非末尾再帰バージョン:

(defun addup3 (n) 
  (if (= n 0)
    0   
    (+ n (addup (- n 1)))))

末尾再帰バージョン:

(defun addup2 (n) 
  (labels ((f (acc k)
              (if (= k 0)
                   acc 
                   (f (+ acc k) (- k 1)))))
  (f 0 n)))

入力を使用して CLISP でこれらの関数を実行しようとしていますn = 1000000。これが結果です

[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)

*** - Program stack overflow. RESET

どちらも SBCL で正常に実行できますが、非末尾再帰の方が高速です (少しだけですが、私には奇妙に思えます)。Stackoverflow の質問で回答を探しましたが、似たようなものが見つかりませんでした。末尾再帰関数はすべての再帰関数呼び出しをスタックに置かないように設計されているのに、スタック オーバーフローが発生するのはなぜですか? 末尾呼び出しを最適化するようにインタープリター/コンパイラーに指示する必要がありますか? （デバッグレベルを設定し、トレース機能を犠牲にして最適化するようなものを読み(proclaim '(optimize (debug 1))ましたが、これが何をするのかわかりません）。たぶん答えは明白で、コードはでたらめですが、私はそれを理解できません。助けていただければ幸いです。

編集: danlei がタイプミスを指摘しましたaddup3。これは最初の関数での呼び出しである必要があるため、再帰的です。修正された場合、両方のバージョンがオーバーフローしますが、彼のバージョンはオーバーフローしません

(defun addup (n) 
         "Adds up the first N integers"
         (do ((i 0 (+ i 1)) 
              (sum 0 (+ sum i)))
             ((> i n) sum)))

より典型的な方法かもしれませんが、末尾再帰が常に最適化されているとは限らないのは奇妙だと思います。

4

4 に答える 4

9

Common Lisp の実装がテール コールの最適化を行う必要はありません。ただし、ほとんどの場合はそうです (Java 仮想マシンの制限により、ABCL はそうではないと思います)。

実装のドキュメントには、TCO を実現するために選択すべき最適化設定が記載されています (利用可能な場合)。

Common Lisp コードでは、ループ構造の 1 つを使用する方が慣用的です。

(loop :for i :upto n
      :sum i)

(let ((sum 0))
  (dotimes (i n)
    (incf sum (1+ i))))

(do ((i 0 (1+ i))
     (sum 0 (+ sum i)))
    ((> i n) sum))

この場合、もちろん、「小さなガウス」を使用することをお勧めします。

(/ (* n (1+ n)) 2)
于 2013-05-18T20:50:06.853 に答える
6

まあ、あなたaddup3はまったく再帰的ではありません。

(defun addup3 (n) 
  (if (= n 0)
    0   
    (+ n (addup (- n 1))))) ; <--

それは何でも呼び出しますaddup。SBCL で修正版を試す:

CL-USER> (defun addup3 (n) 
           (if (= n 0)
               0   
               (+ n (addup3 (- n 1)))))
ADDUP3
CL-USER> (addup3 100000)
Control stack guard page temporarily disabled: proceed with caution
;  ..
; Evaluation aborted on #<SB-SYS:MEMORY-FAULT-ERROR {C2F19B1}>.

ご想像のとおり。

于 2013-05-19T05:34:14.217 に答える
1

GNU CommonLisp、GCL 2.6.12 を使用してコンパイルaddup2すると、テール コールが最適化されます。

>(compile 'addup2)                                                                     

Compiling /tmp/gazonk_3012_0.lsp.
End of Pass 1.  

;; Note: Tail-recursive call of F was replaced by iteration.
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /tmp/gazonk_3012_0.lsp.
Loading /tmp/gazonk_3012_0.o
start address -T 0x9556e8 Finished loading /tmp/gazonk_3012_0.o
#<compiled-function ADDUP2>
NIL
NIL

>>(addup2 1000000)                                                                                                                                            

500000500000
>(addup3 1000000)

Error: ERROR "Invocation history stack overflow."
Fast links are on: do (si::use-fast-links nil) for debugging
Signalled by IF.
ERROR "Invocation history stack overflow."

Broken at +.  Type :H for Help.
    1  Return to top level. 

>>(compile 'addup3)                                                                                                                                           

Compiling /tmp/gazonk_3012_0.lsp.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling /tmp/gazonk_3012_0.lsp.
Loading /tmp/gazonk_3012_0.o
start address -T 0x955a00 Finished loading /tmp/gazonk_3012_0.o
#<compiled-function ADDUP3>
NIL
NIL
>>(addup3 1000000)                                                                                                                                            

Error: ERROR "Value stack overflow."

それが役に立てば幸い。

于 2016-07-04T07:31:56.357 に答える
0

SBCLユーザーマニュアル:

コンパイラは「適切に末尾再帰的」です。[...] 末尾再帰フレームの削除は、末尾再帰最適化を無効にすることで防ぐことができます。これは、デバッグ最適化品質が 2 より大きい場合に発生します。

そして、新しいイメージの REPL でそのまま機能します。

(defun sum-no-tail (n)
  (if (zerop n)
      0
      (+ n (sum-no-tail (- n 1)))))

(defun sum-tail (n &key (acc 0))
  (if (zerop n)
      acc
      (sum-tail (- n 1) :acc (+ n acc))))

CL-USER> (sum-no-tail 10000)
50005000 (26 bits, #x2FB0408)
CL-USER> (sum-no-tail 100000)
Control stack guard page temporarily disabled: proceed with caution
; Debugger entered on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
[1] CL-USER> 
; Evaluation aborted on #<SB-KERNEL::CONTROL-STACK-EXHAUSTED {10026620A3}>
CL-USER> (sum-tail 100000)
5000050000 (33 bits, #x12A06B550)
CL-USER> (sum-tail 1000000)
500000500000 (39 bits, #x746A5A2920)
CL-USER> (sum-tail 10000000)
50000005000000 (46 bits, #x2D7988896B40)

SBCLで役立つことを願っています。

于 2021-09-16T15:58:27.723 に答える