I totally agree, having different eviction strategies would be great
and having memoizers with max capacities in clojure.contrib would
probably be useful to a lot of developers.
Also, a memory sensitive memoizer (using soft references?) would be
nice. :)
On Mar 9, 4:51 pm, Meikel Brandmeyer <m...@kotka.de> wrote:
> 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
