On Mar 13, 4:51 pm, Christophe Grand <christo...@cgrand.net> wrote:
> My variations on memoize use a single atom: your bounded-memoize id roughly
> equivalent to my memoize2 + fifo-strategy,
> seehttp://gist.github.com/330644#LID19.
I finally found the time to fully read your gist, and I see you are
indeed doing the same there. It's just a little less obvious due to
the indirection introduced by strategies.
> Two quick notes:
> * a PersistentQueue is a better fit there (conj at one end, pop/peek at the
> other) than a vector,
> * by padding it to the desired length (capacity) with dummy items, you are
> sure that the queue (or the vector) is always full, so you always have to
> remove an item: no more need for the (> (count v) capacity) test.
Agree, this simplifies the code a bit, and once we reach full
capacity, the "if" will always be true anyway.
> That's why Meikel tests twice if the value is already in the cache (the
> first time outside of a transactio, the second time inside) and why I
> introduce hit-or-assoc in memoize4/memoize5.
Still, with bad luck or just enough concurrency, simultaneous calls to
memoize6 with the same args can result in multiple computations, as
the computation (apply f args) is done outside of the swap:
(let [ret (if-let [e (find (cached @mem) args)] (val e) (apply f
args))
m (swap! mem hit-or-assoc args ret)]
This gap shrinks when using memoize7 thanks to the use of delays, but
it is not completely closed and can still lead to multiple delays of
the same computation. If we want to get rid off this gap and make it
truely atomic, we have to make the decision whether or not to compute
inside the swap! block.
My memoizer with the hard-coded fifo strategy thus turns into
something like this:
(defn bounded-memoize
[f capacity]
(let [mem (atom [{} []])]
(fn [& args]
(deref ((first
(swap! mem #(if (contains? (first %) args)
%
(let [new-cache (assoc (first %) args (delay
(apply f args)))
new-v (conj (second %) args)]
(if (> (count new-v) capacity)
[(dissoc new-cache (first new-v)) (subvec
new-v 1)]
[new-cache new-v])))))
args)))))
Using a padded queue (and getting rid of the anonymous % param names),
it can be (slightly) simplified to:
(defn bounded-memoize
[f capacity]
(let [mem (atom [{} (into clojure.lang.PersistentQueue/EMPTY (repeat
capacity :dummy))])]
(fn [& args]
(deref ((first
(swap! mem (fn [[m q :as cache]]
(if (contains? m args)
cache
[(dissoc (assoc m args (delay (apply f args)))
(peek q))
(-> q pop (conj args))]))))
args)))))
--
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
