On Sun, Sep 22, 2013 at 8:54 PM, Mark Engelberg <mark.engelb...@gmail.com>wrote:
> When you're doing memoization and you have a lot of "holes" in the inputs,
> one option is to have two phases to your function. The first phase takes
> the initial input and then computes a collection of all the inputs that are
> dependencies and need to be computed ahead of time. Then in phase two, you
> can "prime the pump" with that particular sequence of inputs. If you need
> help on this, I can give you a concrete example of how to do this.
>
OK, here's a concrete example. Let's say you have a recursive function f
that, for every n>5, is dependent on (f (- n 5)) and (f (quot n 2)). We'll
assume that the formula is not recursive for inputs in (range 5) and that
these are the base cases.
It's not obvious how to prime the pump here, so we need to compute it.
First, we express the dependencies:
(defn dependencies [n]
(if (< n 5) [] [(- n 5) (quot n 2)]))
Next, we do a tail-recursive breadth-first search:
(defn all-dependencies [n]
(loop [stack ()
unprocessed (conj clojure.lang.PersistentQueue/EMPTY n)
processed #{}]
(if (empty? unprocessed) stack
(let [i (peek unprocessed)]
(if (processed i)
(recur stack (pop unprocessed) processed)
(recur (conj stack i)
(into unprocessed (dependencies i))
(conj processed i)))))))
Now, we can run all-dependencies to get back the list of inputs to prime
the pump:
=> (all-dependencies 20)
(0 3 2 5 7 10 15 20)
=> (all-dependencies 30)
(0 1 3 2 5 6 7 10 12 20 15 25 30)
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
