User Tools

Site Tools


tips:clojure:fibonacci

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
tips:clojure:fibonacci [2013/05/16 02:23]
psk810 [기억화된 단순 버젼]
tips:clojure:fibonacci [2019/02/04 14:26] (current)
Line 23: Line 23:
 단순 버젼의 경우 아래와 같이 중복해서 계산하는 경우가 많다. 단순 버젼의 경우 아래와 같이 중복해서 계산하는 경우가 많다.
 <​code>​ <​code>​
-          ​fib4 +               fib4 
-       ​/        \ +            /        \ 
-    fib3        fib2      +         ​fib3        fib2      
-    /  \        /  \ +         ​/  \        /  \ 
- ​fib2 ​ fib1  fib1  fib0+      fib2  fib1  ​fib1  fib0 
 +      /  \ 
 +   fib1  fib0
 </​code>​ </​code>​
  
 fib4를 계산하기 위해서는 fib3, fib2, fib1, fib0을 각각 한 번만 계산하면 되는데, fib4를 계산하기 위해서는 fib3, fib2, fib1, fib0을 각각 한 번만 계산하면 되는데,
-단순 버젼의 경우 위와 같이 fib2와 fib1을 각각 ​2번 계산하고 있다.+단순 버젼의 경우 위와 같이 fib2는 2번, fib1는 3번, fib0은 ​2번 계산하고 있다.
  
 +따라서 중복 계산하지 않고, 한 번 계산한 결과를 사용한다면 좋을 것이다.
 +memoize는 한 번 계산한 함수의 결과를 저장하여 사용하기 때문에 속도가 빨라진다.
  
- 
-memorize를 통해 한 번 계산한 것은 저장하여 쓰면, 계산 속도가 빨라진다. 
  
 <code clojure> <code clojure>
Line 82: 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 94: Line 96:
 </​code>​ </​code>​
  
-완성!+lazy-seq은 해당 요소에 접근할 때만 한 번 계산 함수가 수행된 후 결과값이 기억화(memoization)된다. 여기서 계산 함수는 재귀호출 되지 않는다. 매 계산마다 fib(n) = fib(n-1) + fib(n-2)만이 수행될 뿐이다. 
 + 
tips/clojure/fibonacci.1368671007.txt.gz · Last modified: 2019/02/04 14:26 (external edit)