3

次の関数は、末尾再帰と 2 乗によってフィボナッチ数列を計算します。

(defun fib1 (n &optional (a 1) (b 0) (p 0) (q 1))
  (cond ((zerop n) b)
    ((evenp n) 
     (fib1 (/ n 2) 
          a 
          b 
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q))))
    (t 
     (fib1 (1- n)
          (+ (* b q) (* a (+ p q)))
          (+ (* b p) (* a q))
          p
          q))))

基本的に、すべての奇数入力を偶数入力に減らし、すべての偶数入力を半分に減らします。例えば、

F(21)
    = F(21 1 0 0 1) 
    = F(20 1 1 0 1) 
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3)
    = F(4 8 5 2 3) 
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 610 987)
    = 10946

これを見たとき、偶数と奇数を組み合わせたほうがいいのではないかと思ったので（奇数マイナス1 =偶数なので）、

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (zerop n) b
     (fib2 (ash n -1) 
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))

上記の方程式が次のようになるため、これにより高速になることを願っています

F(21)
    = F(21 1 0 0 1)
    = F(10 1 1 1 1) 
    = F(5 1 1 2 3)
    = F(2 8 5 13 21) 
    = F(1 8 5 610 987) 
    = F(0 17711 10946 1346269 2178309)
    = 10946

ただし、次のコードで Fib(1000000) に必要な時間を確認すると、はるかに遅いことが判明しました (Clozure CL、CLisp、Lispworks などでは約 50% 時間がかかります)。画面を数字でいっぱいにしたい。)

(time (progn (fib1 1000000)()))
(time (progn (fib2 1000000)()))

fib2 が fib1 よりも多くの eventp を実行する可能性があることしかわかりませんが、なぜそれほど遅いのでしょうか?

編集: nm は正しいと思います。数式の 2 番目のグループを編集しました。たとえば、上記の F(21) の例では、fib2 は実際には p と q で F(31) と F(32) を計算しますが、これは使用されません。したがって、F(1000000) では、fib2 は F(1048575) と F(1048576) を計算します。

遅延評価は揺るぎません。これは非常に良い点です。Common Lisp では、"and" や "or" などの一部のマクロだけが遅延評価されるのでしょうか?

次の変更された fib2 (n>0 に対して定義) は、実際にはより高速に実行されます。

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (= n 1) (+ (* b p) (* a q))
     (fib2 (ash n -1) 
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))
4

2 に答える 2

3

中間結果の印刷を挿入します。計算の終わりに注意してpください。q

が最後のステップでとのfib2値をはるかに大きく計算していることに気付くでしょう。これら 2 つの値は、すべてのパフォーマンスの違いを説明しています。pq

皮肉なことに、これらの高価な値は使用されていません。これが、Haskell がこのパフォーマンスの問題に悩まされない理由です。未使用の値は実際には計算されません。

于 2012-08-06T15:37:08.650 に答える
0

他に何もなければ、 fib2 にはより多くの条件があります (引数の計算中)。これにより、コード フローの実行方法が変わる可能性があります。条件分岐はジャンプを意味し、パイプラインのストールを意味します。

生成されたコードを確認することはおそらく有益でしょう (試し(disassemble #'fib1)てみて(disassemble #'fib2)、あからさまな違いがあるかどうかを確認してください)。最適化設定を変更することも価値があるかもしれません。通常、速度のために大幅な最適化を要求しない限り、実行されない最適化がかなりあります。

于 2012-08-06T10:19:15.527 に答える