11

Lispを試してみたかったのですが、すぐに諦めました。もう一度やってみようと思いました。私はプロジェクトオイラーの問題2を見ています-400万未満のすべてのフィボナッチ数の合計を見つけています。

私は動作する次のコードを書きましたが、あらゆる種類の醜いです。それらの中で最も重要なのは、それが非常に遅いという事実です-それは常に素朴な再帰を行っているからです。

このプログラムをPythonで作成したとき、数値を計算したときにリストを作成しましたが、数値を再計算することはありませんでした。私はここで（どういうわけか）それができることを知っていますが、それはLispの精神、関数型プログラミングには当てはまらないようです。再帰の深さの制限に達して、再帰の代わりにループを使用するようにコードを書き直さなければならなかったとき、私は＃3の後で諦めました。

だから私の質問は次のとおりだと思います：

  1. この問題を解決するための「正しい、しなやかな方法」とは何ですか？
  2. 再帰と「すべてを計算するだけ」の概念を、すべてを計算する実際的な制限とどのように調和させますか？
  3. The LittleSchemerとProjectEuler以外にlispを学ぶための推奨事項はありますか？

そして、これが私のコードです：

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))
4

14 に答える 14

15

http://fare.tunes.org/files/fun/fibonacci.lispには、フィボナッチを解決するためのウォークスルーがあり、実装の時間とメモリのパフォーマンスが徐々に向上しています。

于 2009-03-09T18:15:28.910 に答える
9

メモ化は、結果を関数にキャッシュして、中間結果を何度も再計算しないようにする方法です。メモ化とは、基本的に、いくつかの引数を使用して関数を初めて呼び出し、回答を計算して返し、その回答をキャッシュすることを意味します。同じ引数を持つ関数への後続の呼び出しでは、キャッシュされた値を返すだけです。

Lispでは、高階関数とマクロを簡単に使用して、関数を透過的にメモ化できます。Clojureにはmemoize標準機能が含まれています。のCommonLisp実装については、OnLispの65ページも参照してくださいmemoize。これがClojureにあります：

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user>

大きな整数で呼び出すと、スタックオーバーフローが発生する可能性があります。(fib 10000)たとえば、スタックはまだ非常に深く（1回）再帰する必要があるため、すぐに実行するとスタックが吹き飛ばされます。ただし、最初にキャッシュをプライミングすると、キャッシュを深く再帰する必要がなくなり、これを回避できます。これを最初に行うだけです（Clojureで）：

(dorun (map fib-memo (range 1 10000)))

その後、問題なく実行できるようになります(fib 10000)。

（最近、フィボナッチ数の計算に関する特定の主題がClojureメーリングリストに掲載されました。ルーカス数に基づく解決策があります。これは、私には少しもわかりませんが、単純なアルゴリズムよりも40倍高速であると思われます。）

于 2009-03-09T19:48:07.423 に答える
7

ナイーブ再帰の代わりに末尾再帰を使用します。ほとんどのLisp実装は、末尾呼び出しの最適化を実行する必要があります。これ以上の再帰深度制限はありません。

それを超えて、リストとそれらのリストで実行できる抽象的な操作の観点から物事を考えてみてください。考慮すべき、より関連性の高い2つの操作：

その他のLispリソースについて：

更新：末尾再帰Schemefib関数：

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))
于 2009-03-09T18:14:43.810 に答える
4 
(let ((a 1) (b 1))
  (flet ((nextfib ()
           (prog1 a
             (psetf a b b (+ a b)))))
    (loop for fib = (nextfib)
          while (<= fib 4000000)
          when (evenp fib)
            sum fib)))

上記では、呼び出しごとに次のフィボナッチ数を生成する関数 NEXTFIB を定義しています。LOOP は、偶数の結果を 4000000 の制限まで合計します。

PROG1 は、その部分式の最初の値を返します。PSETF は a と b を「並列」に設定します。

よくあるパターンです。ジェネレータ関数があり、それを繰り返し呼び出し、結果をフィルタリングして結合します。

于 2009-03-09T20:57:04.713 に答える
3

これを解決する方法は、ボトムアップで作業し、各フィボナチ項を1つずつ生成し、それが偶数の場合は合計に加算し、400万のしきい値に達したら停止することです。私のLISPは錆びているので、ここでは疑似コードになっています。

one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
  if curr % 2 == 0
    sum = sum + curr
  two_prior = one_prior
  one_prior = curr
  curr = one_prior + two_prior
于 2009-03-09T18:20:10.550 に答える
2

すべての有用な答えに加えて、次の式はさらに効率を提供する可能性があります-O（2 ^ n）ではなくO（Log（n））でFnを計算します。これはメモ化と組み合わせる必要があり、問題を解決するための強固な基盤です。

F(2*n) = F(n)^2 + F(n-1)^2

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)
于 2009-03-17T13:58:23.997 に答える
2

danio の回答は、パフォーマンスに関する質問に大いに役立ちます。

以下は、あなたのスタイルに対する短い批評です。

 (defun fib(i)
   (if (= i 1) ;//Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2)))
     )
   )
 )

ネストされた IF を COND にリファクタリングします。

括弧を単独で行に入れないでください。

(defun solve(i)
   (let ((f (fib i))) ;//結果をローカル変数に格納
     (print f) ;//デバッグ用
     （もしも （


ZEROP を使用するとより明確になります。



         (+ f (解 (+ i 1))) ;//数値を追加
         (解決 (+ i 1)) ;//しないでください




なぜそれらを // 入れるのですか? セミコロンとそれに続くスペースで十分です。



       )
     )
   )
 )
 (印刷 (解決 1))

あなたの最後の PRINT ステートメントは、私を少し疑わしくさせます。このプログラムをファイルまたは REPL から実行していますか? 前者を行う場合は、後者を検討する必要があります。後者の場合は、(1 を解く) と言うだけで結果が得られます。

于 2009-03-09T20:45:11.543 に答える
1

Danioの答えを拡張するために、http：//fare.tunes.org/files/fun/fibonacci.lispの記事では、コードをより高速に実行する2つの方法を紹介しています。ストレート再帰（末尾呼び出しまたはなし）の使用はO（2 ^ n）であり、非常に低速です。難しいのは、各値が何度も計算されることです。あなたは物事を違ったやり方でしなければなりません。2つの推奨事項は次のとおりです。

  1. 反復的なアプローチを使用します。
(defun bubble-fib (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (check-type n fixnum)
  (loop repeat n
  with p = 0 with q = 1
  do (psetq p q
        q (+ p q))
  finally (return p)))
  1. メモ化を使用します。これは、値を再計算するのではなく、前に表示された値を記憶し、それらを想起することを意味します。この記事では、これを実行するCLパッケージと、それを自分で実行するためのコードを提供しています。
于 2009-03-09T19:50:21.083 に答える
1

フィボナッチ数のリストを作成する簡単で効率的な方法：

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

（shiftf）は任意の数の場所を取り、最後に値を取ります。各場所は次の変数の値に設定され、最後の変数はその後の値を取ります。そもそも値を返します。つまり、すべての値を1つ左にシフトします。

ただし、完全なリストは必要ありません（偶数のみが必要です）。また、リストはまったく必要ありません（合計のみが必要です）。したがって、これを関数に直接組み込むことができます。3つおきのフィボナッチ数は偶数なので...

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))
于 2009-03-18T20:28:04.183 に答える
1

「Lisp の精神」についての私の理解は、Lisp の精神の固定された、独断的で行き詰まった考えから自分自身を切り離し、問題を解決するために必要な計算の構造を最もよく反映する Lisp 構造を使用することです。例えば、

(defun euler2 (&optional (n 4000000))
  (do ((i 1 j)
       (j 2 (+ i j))
       (k 0))
      ((<= n i) k)
    (when (evenp i) (incf k i))))

再帰を主張する場合は、別の方法があります。

(defun euler2 (&optional (n 4000000))
  (labels ((fn (i j k) 
             (if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
    (fn 1 2 0)))
于 2009-03-09T19:54:18.157 に答える
0 
(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))
于 2009-03-11T14:30:09.260 に答える
0

http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/にあるビデオとテキストの両方を参照してください。

于 2009-03-09T18:41:53.837 に答える
0

こちらはメモバージョン。この場合、400 万を超えるフィボナッチ数が見つかるまで各フィボナッチ数を計算する必要があるため、閉じた形式の解を使用してもあまり効果がありません。

letこのアプローチは、 ;を介してレキシカル環境を作成します。その環境で辞書fib-table と関数fib-memoedを作成します。これの最終製品fib-tableはアクセス可能ですが、他の場所からはアクセスfib-memoedできません。

キッカー:fibある条件が満たされるまで連続した値を計算する必要があるため、 でソルバーを開始しfib 1ます。これ以降、次の fib 数を計算するには、最大で 2 回の辞書検索と 1 回の追加が必要です: O(1)BOOM!

;; memoised fib function: make a hash table, then create                                      
;; the fib function in the lexical scope of the hash table                                    
(let ((fib-table (make-hash-table)))
  (setf (gethash 0 fib-table) 1)
  (setf (gethash 1 fib-table) 1)
  (defun fib-memoed (n)
    (let ((x (gethash n fib-table)))
      (cond ((not (null x))
             x)
            (t
             (let ((y (+ (fib-memoed (- n 1))
                         (fib-memoed (- n 2)))))
               (setf (gethash n fib-table) y)
               y))))))

(defun solve ()
  (let ((maxval 4000000))
    (labels ((aux (i acc)
               (let ((x (fib-memoed i)))
                 (cond ((> x maxval) acc)
                       ((evenp x)
                        (aux (1+ i) (+ x acc)))
                       (t (aux (1+ i) acc))))))
      (aux 1 0))))
于 2019-03-01T06:26:45.730 に答える