tips:clojure:fibonacci
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
tips:clojure:fibonacci [2013/05/15 14:00] psk810 새로 만듦 |
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 56: | Line 72: | ||
| (def fib (memoize fib)) | (def fib (memoize fib)) | ||
| - | (fib 100) | + | (time (fib 100)) |
| + | ;>> "Elapsed time: 0.08705 msecs" | ||
| ;=> 354224848179261915075N | ;=> 354224848179261915075N | ||
| Line 64: | Line 81: | ||
| 스택 오버플로우가 발생한다. | 스택 오버플로우가 발생한다. | ||
| - | |||
| ===== lazy-seq을 이용한 피보나치 ===== | ===== lazy-seq을 이용한 피보나치 ===== | ||
| <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)) | ||
| - | (fib 1000) | + | (time (fib 1000)) |
| + | ;>> "Elapsed time: 1.200634 msecs" | ||
| ;=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875N | ;=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875N | ||
| + | |||
| + | (time (fib 10000)) | ||
| + | ;>>"Elapsed time: 19.487308 msecs" | ||
| + | ;=>> 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875N | ||
| </code> | </code> | ||
| - | 완성! | + | lazy-seq은 해당 요소에 접근할 때만 한 번 계산 함수가 수행된 후 결과값이 기억화(memoization)된다. 여기서 계산 함수는 재귀호출 되지 않는다. 매 계산마다 fib(n) = fib(n-1) + fib(n-2)만이 수행될 뿐이다. |
tips/clojure/fibonacci.1368626438.txt.gz · 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
