tips:clojure:fibonacci
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
tips:clojure:fibonacci [2013/05/15 14:29] psk810 [lazy-seq을 이용한 피보나치] |
tips:clojure:fibonacci [2013/05/16 03:54] psk810 [lazy-seq을 이용한 피보나치] |
||
|---|---|---|---|
| Line 21: | Line 21: | ||
| ===== 기억화된 단순 버젼 ===== | ===== 기억화된 단순 버젼 ===== | ||
| - | memorize를 통해 한 번 계산한 것은 저장하여 쓰면, 계산 속도가 빨라진다. | + | 단순 버젼의 경우 아래와 같이 중복해서 계산하는 경우가 많다. |
| + | <code> | ||
| + | fib4 | ||
| + | / \ | ||
| + | fib3 fib2 | ||
| + | / \ / \ | ||
| + | fib2 fib1 fib1 fib0 | ||
| + | / \ | ||
| + | fib1 fib0 | ||
| + | </code> | ||
| + | |||
| + | fib4를 계산하기 위해서는 fib3, fib2, fib1, fib0을 각각 한 번만 계산하면 되는데, | ||
| + | 단순 버젼의 경우 위와 같이 fib2는 2번, fib1는 3번, fib0은 2번 계산하고 있다. | ||
| + | |||
| + | 따라서 중복 계산하지 않고, 한 번 계산한 결과를 사용한다면 좋을 것이다. | ||
| + | memoize는 한 번 계산한 함수의 결과를 저장하여 사용하기 때문에 속도가 빨라진다. | ||
| <code clojure> | <code clojure> | ||
| Line 68: | Line 84: | ||
| <code clojure> | <code clojure> | ||
| - | (defn fib1 [n] | + | (defn fib [n] |
| (nth ((fn f [a b] (cons a (lazy-seq (f b (+ b a))))) 0N 1N) n)) | (nth ((fn f [a b] (cons a (lazy-seq (f b (+ b a))))) 0N 1N) n)) | ||
| Line 80: | Line 96: | ||
| </code> | </code> | ||
| - | 완성! | + | lazy-seq은 해당 요소에 접근할 때만 한 번 계산 함수가 수행된 후 결과값이 기억화(memoization)된다. 여기서 계산 함수는 재귀호출 되지 않는다. 매 계산마다 fib(n) = fib(n-1) + fib(n-2)만이 수행될 뿐이다. |
| + | |||
tips/clojure/fibonacci.txt · Last modified: 2019/02/04 14:26 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
