Hi,
On Mar 9, 4:41 am, Eugen Dück <eu...@dueck.org> wrote:
> Good points! Testing array-map briefly led me to believe they can be
> used as the clojure equivalent of Java\s LinkedHashMaps.
>
> Here's a version that uses a vector to remember order of insertion - I
> guess I have to use refs and transactions now:
>
> (defn bounded-memoize
> [f bound]
> (let [mem (ref {})
> v (ref [])]
> (fn [& args]
> (if-let [e (find @mem args)]
> (val e)
> (let [ret (apply f args)]
> (dosync
> (when (= (count @v) bound)
> (alter mem dissoc (first @v))
> (alter v subvec 1))
> (alter mem assoc args ret)
> (alter v conj args))
> ret)))))
>
> Haven't looked at clojure's queues yet, they might make the code more
> concise, but by looking at that other post, they don't seem to be
> exposed in a clojurey way (using a java class name).
How about generalising memoize to allow different strategies?
(defn bound-cache-strategy
"Implements a bound cache strategy for memoize. At most bound number
of
argument lists are kept in the cache. They are dropped in order of
insertion."
[bound]
[find
(let [values (ref clojure.lang.PersistentQueue/EMPTY)]
(fn [cache args]
(alter values conj args)
(if (> (count @values) bound)
(do
(alter values pop)
(dissoc cache args))
cache)))])
(defn lru-cache-strategy
"Implements LRU cache strategy for memoize. At most bound number of
argument lists are kept in the cache. They are dropped in LRU
order."
[bound]
(let [values (ref {})]
[(fn lru-cache-strategy-lookup
[cache args]
(when-let [e (find cache args)]
(let [now (System/currentTimeMillis)]
(dosync (alter values assoc args now))
e)))
(fn lru-cache-strategy-update
[cache args]
(let [now (System/currentTimeMillis)
k (min-key @values (keys @values))]
(alter values dissoc k)
(alter values assoc args now)
(dissoc cache k)))]))
(defn most-used-cache-strategy
"Implements MU cache strategy for memoize. At most bound number of
argument lists are kept in the cache. They are dropped in LU order.
In case elements have the same usage count, the order of drop is
unspecified."
[bound]
(let [values (ref {})]
[(fn most-used-cache-strategy-lookup
[cache args]
(when-let [e (find cache args)]
(dosync (alter values update-in [args] inc))
e))
(fn most-used-cache-strategy-update
[cache args]
(let [k (min-key @values (keys @values))]
(alter values dissoc k)
(alter values assoc args 1)
(dissoc cache k)))]))
(defn memoize
"Returns a memoized version of a referentially transparent function.
The
memoized version of the function keeps a cache of the mapping from
arguments
to results and, when calls with the same arguments are repeated
often, has
higher performance at the expense of higher memory use.
Optionally a cache strategy might be supplied. A strategy is pair of
functions:
- one for accessing the cache, returns the map entry on success or
nil
(cf. find)
- one, which takes the cache and the argument vector and might
modify
the cache.
Possible implementation could be a bounded cache or a LRU strategy.
Default is a naive strategy keeping all encountered argument lists
forever.
The cache update function is called in a transaction, the cache
lookup
function not necessarily so."
([f] (memoize f [find (fn [c _] c)]))
([f [cache-lookup cache-update]]
(let [cache (ref {})]
(fn [& args]
(if-let [e (cache-lookup @cache args)]
(val e)
(dosync
(if-let [e (cache-lookup @cache args)]
(val e)
(let [result (apply f args)]
(alter cache assoc args result)
(alter cache cache-update args)
result))))))))
Usage Examples:
(memoize f)
(memoize f (bound-cache-strategy 5))
(memoize f (lru-cache-strategy 5))
(memoize f (most-used-cache-strategy 5))
(Note: I have no clue about whether lru is well implemented or mu
makes sense. Just some examples...)
Sincerely
Meikel
--
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
