Search code examples
clojure

Memoize doesn't work for fibonacci example

(time (fib 30))
;; "Elapsed time: 8179.04028 msecs"

;; Fibonacci number with recursion and memoize.
(def m-fib
  (memoize (fn [n]
             (condp = n
               0 1
               1 1
               (+ (m-fib (dec n)) (m-fib (- n 2)))))))

(time (m-fib 30))
;; "Elapsed time: 1.282557 msecs"

This the example code from https://clojuredocs.org/clojure.core/memoize, but when I run it on my browser, the time doesn't change at all. I am wondering why it is? enter image description here

Solution

  • I don't know what browser-based REPL you're using, but the left-hand column shows the result of the function call, not the time, which is why both values are the same. Both functions compute the same Fibonacci number.

    The time macro is designed to wrap arbitrary expressions without having to change the structure of the code, so it returns the same value that's returned by the wrapped expression and prints the execution time to standard out. Essentially, the expression (time (m-fib 30)) is expanded to

    (let [start (. System (nanoTime))
      ret (m-fib 30)]
  (println (str "Elapsed time: " (/ (double (- (. System (nanoTime)) start)) 1000000.0) " msecs"))
  ret)

    So to see the execution time in your REPL, you'll need to see the printed output of an expression.