SHOW:
|
|
- or go back to the newest paste.
1 | - | (declare fibo) |
1 | + | (declare fibo-m) |
2 | ||
3 | (defn fibo [n] | |
4 | (if (<= n 2) | |
5 | 1 | |
6 | (+ (fibo-m (- n 1)) (fibo-m (- n 2))))) | |
7 | ||
8 | (def fibo-m (memoize fibo)) | |
9 | ||
10 | ;; --------------------------------------------------------- | |
11 | ;; the (fibo-m 35) should NOT be slow, it has alreay been | |
12 | ;; calculated by the previous call to (fibo-m 36) | |
13 | ;; what would be the idiomatic clojure way to apply memoize | |
14 | ;; to fibo such as the recursives call inside fibo body get | |
15 | ;; memoized as-well ? | |
16 | ;; --------------------------------------------------------- | |
17 | ||
18 | ;; for comparaison i put the working equivalent in python: | |
19 | def memo(f, cache={}): | |
20 | def caching_func(n): | |
21 | if n not in cache: | |
22 | cache[n] = f(n) | |
23 | return cache[n] | |
24 | return caching_func | |
25 | ||
26 | @memo | |
27 | def fibo(n): | |
28 | """ | |
29 | i know it's not an efficient way to do fibo | |
30 | it's just made for example purpose | |
31 | """ | |
32 | if n <= 2: | |
33 | return 1 | |
34 | return fibo(n - 1) + fibo(n - 2) | |
35 | ||
36 | ###################### | |
37 | import time | |
38 | def time_it(f, *args): | |
39 | start = time.clock() | |
40 | print f(*args) | |
41 | return (time.clock() - start) | |
42 | ||
43 | print time_it(fibo, 500) | |
44 | # Elapsed time: 0.004 | |
45 | #= 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125 | |
46 | ||
47 | print time_it(fibo, 499) | |
48 | # Elapsed time: 0.0 | |
49 | #= 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501 |