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/15 14:29]
psk810 [lazy-seq을 이용한 피보나치]
tips:clojure:fibonacci [2019/02/04 14:26] (current)
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.1368628181.txt.gz · Last modified: 2019/02/04 14:26 (external edit)