CODEWITHSUNDEEP
recursionclojurememoization
MichaelBVaughn
MichaelBVaughn

Reputation: 25

Unexpectedly slow memoized function in Clojure

While practicing Clojure, I was working on recursively counting walks that can only travel right or down on a graph (from Project Euler). It's a trivial problem, but I wanted to experiment with different ways of solving the problem.

(defn path-count [x y] (cond
                     (or (< y 0) (< x 0)) 0
                     (= y 0) 1
                     :else (+ (path-count x (- y 1))
                              (path-count (- x 1) y))))

(def path-count-memoized (memoize path-count))

(defn cartesian-range [min max]
(for [y (range min max)
      x (range min max)]
     [x y]))

(map 
  (fn [pair] 
    (path-count-memoized 
      (nth pair 0) 
      (nth pair 1))) 
  (cartesian-range 0 20))

Looking at it, it looks like it should perform asymptotically similarly to an iterative solution starting with (0,0) that uses a 20x20 array. However, it's extremely slow. I'm not sure where I'm going wrong. I'm thinking I'm misunderstanding how the memoization cache works [or hitting a size limit - that seems ridiculous though], or I'm misunderstanding the order in which map evaluates terms of a lazy sequence.

Upvotes: 1

Views: 249

Answers (1)

Alex Miller
Alex Miller

Reputation: 70201

path-count is not calling the path-count-memoize inside itself, so you're not actually getting much memoization. Setting that up is kind of tricky and there are a couple techniques to be found here:

How do I generate memoized recursive functions in Clojure?

Upvotes: 2

Related Questions