4

ここで聞くのはもったいないです。本当にそうです。悩みの答えを無駄に探すたびに、それが見えてきます。私を罵倒します。スタック オーバーフロー。

とにかく、地獄のような影響を受けて、ハノイの塔を解決しようとしました。あまりにも多くのディスクで実行するとメモリ エラーが発生したため、最初の解決策は不完全でした。

(define hanoi
  (lambda (n from to other)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       '())
      (else
       (append (hanoi (- n 1)
              from
              other
              to)
           `((,from ,to))
           (hanoi (- n 1)
              other
              to
              from))))))

継続渡しスタイルが問題を解決するということをどこかで読みました。ただし、これも役に立ちませんでした:

(define hanoi_cps
  (lambda (n from to other c)
    (cond ((< n 0)
       (error `(Error! Number of disks ,n cannot be less than 0!)))
      ((= n 0)
       (c '()))
      (else
       (hanoi_cps (- n 1)
              from
              other
              to
              (lambda (x)
            ((lambda (w)
               (w `((,from ,to))))
             (lambda (y)
               (hanoi_cps (- n 1)
                      other
                      to
                      from
                      (lambda (z)
                    (c (append x y z))))))))))))
4

2 に答える 2

14

継続渡しスタイルでは、再帰呼び出しでスタックスペースを拡張するのではなく、継続が実行される環境で再帰的に定義されたラムダを構築しています...つまり、メモリは行のどこかで使い果たされます。たとえば、単純な階乗アルゴリズムの場合、通常は次のように記述します。

(define (factorial x)
    (cond ((eq? x 0) 1))
          ((eq? x 1) 1))
          (else (* x (factorial (- x 1))))))

のこの再帰的定義ではfactorial、各再帰的関数呼び出しで実行される遅延乗算演算への引数を保持するために、スタック スペースが使用されます。同じ関数の継続渡しバージョンは次のようになります。

(define (factorial x cont)
    (cond ((eq? x 0) (cont 1))
          ((eq? x 1) (cont 1))
          (else (factorial (- x 1) (lambda (y) (cont (* x y)))))))

以前はスタック スペースを消費していたものが、匿名ラムダの環境によって使い果たされるようになりました。この場合のラムダの環境は、 の値を解決するために必要な値で埋められており、 のx再帰cont呼び出しごとに使用されていfactorialます。それcont自体が環境を持つラムダであるため、各ラムダ継続がその環境に factorial への前の呼び出しからのラムダを格納する必要があるため、メモリが最終的にどのように消費されるかを確認できます...これにより、再帰的に定義されたラムダ継続が作成されますには、基本的に の再帰呼び出しによって発生したすべての継続の再帰リストである環境がありますfactorial。

継続渡しスタイルを見る 1 つの方法は、基本的に関数呼び出しメカニズムを末尾再帰メソッドに変換した一方で、継続自体の実際の定義は本質的に再帰的であるため、再帰を実際に削除していないということです。 -アルゴリズム自体の性質...つまり、末尾再帰呼び出しで構築された継続を評価するには、その内部で再帰的に定義された継続を評価する必要があり、その内部には別の再帰的に定義された継続があります。ラムダ継続は、リストのリストのリストなどのように見えます。これらすべての再帰的定義をラムダ継続の環境に格納するにはメモリが必要です。通常の再帰呼び出し規則を介してスタックし、または、すべてのラムダ継続で再帰的に定義された環境を格納することでメモリ空間を消費します。どちらにしても、最終的にはスペースが不足します。

于 2011-07-25T19:43:54.497 に答える
3

CPS won't help you make things more memory-efficient, since by performing it, you're just replacing stack frames with anonymous functions. If you want your program to use less memory, try a backtracking search (but note that you have to be careful to avoid infinite move sequences).

于 2011-07-25T17:22:18.737 に答える