Skip to content

Instantly share code, notes, and snippets.

Last active April 17, 2019 10:17
Show Gist options
  • Save cgrand/4722914 to your computer and use it in GitHub Desktop.
Save cgrand/4722914 to your computer and use it in GitHub Desktop.
(ns net.cgrand.decay
"Exponentially decaying lists. See
for background and for documentation")
;; PRNG, formulas straight from java.util.Random javadoc
(defn- seed ^long [^long n]
(bit-and (unchecked-multiply n 0x5DEECE66D)
(unchecked-dec (bit-shift-left 1 48))))
(defn- next-seed ^long [^long seed]
(bit-and (unchecked-add (unchecked-multiply seed 0x5DEECE66D) 0xB)
(unchecked-dec (bit-shift-left 1 48))))
(defn- take-bits ^long [^long n ^long cnt]
(bit-shift-right n (- 48 cnt)))
(defn- next-double ^double [^long s1 ^long s2]
(/ (+ (bit-shift-left (take-bits s1 26) 27) (take-bits s2 27))
(unchecked-double (bit-shift-left 1 53))))
(defn- geometric ^long [^double r ^double lambda]
(unchecked-long (/ (Math/log (- 1.0 r)) lambda)))
(defn- decay-split [l ^long n]
(let [left (doto (object-array (inc n)) (aset n (first l)))]
(loop [right (next l) n n]
(if (pos? n)
(let [n (dec n)]
(aset left n (first right))
(recur (next right) n))
[(seq left) right]))))
(defprotocol DecayingCollection
(decay-loc [coll]
"returns nil or [left right], a split view of the collection where the next
collapse is going to happen. (first left) and (first right) are the items
being collapsed." )
(state [coll]))
(deftype DecayingList [lambda ^clojure.lang.ISeq l ^long seed collapse
^:volatile-mutable ^long nnseed ^:volatile-mutable split
state0 state plus minus capacity]
(decay-loc [coll]
(or split
(let [nseed (next-seed seed)
d (next-double seed nseed)
n (min (geometric d lambda) (- capacity 2))]
(set! nnseed (next-seed nseed))
(when (> (count l) (inc n))
(decay-split l n)))))
(state [coll] state)
(count [this] (.count l))
(cons [this x]
(let [state (plus state x)
[state l]
(if-let [[[left :as lefts] [right :as rights]](set! split (decay-loc this))]
(let [mid (collapse this)
state (cond
(= mid left) (minus state right)
(= mid right) (minus state left)
:else (-> state (minus left) (minus right) (plus mid)))]
[state (-> (next rights) (conj mid) (into (next lefts)))])
[state l])
dl (DecayingList. lambda (conj l x) nnseed collapse 0 nil
state0 state plus minus capacity)]
(set! split nil) ; clearing the cache
(empty [this] (DecayingList. lambda () seed collapse 0 nil
state0 state0 plus minus capacity))
(equiv [this that] (.equiv l that))
(seq [this] (.seq l))
(hasheq [this] (.hasheq ^clojure.lang.IHashEq l))
(hashCode [this] (.hashCode l))
(equals [this that] (.equals this that)))
(defn keep-latest
"Returns the most recent of the two candidates to decay."
[coll] (ffirst (decay-loc coll)))
(defn pass-first [x y] x)
(defn decaying-list
"Returns a new decaying list with specified half-life (10 by default.
Supported options are:
* :capacity specifies the maximum length of the list (unlimited by default),
* :collapse a function taking the decaying list to be decayed and returning
one item to be inserted in lieu of the two candidates to decay (keep-latest
by default),
* :state a state maintained after each update (insertion and decay) with :plus
and :minus,
* :plus and :minus functions taking the state and one item and returning the
updated state; :plus is called when an item is added to the list (conj and
return value of :collapse) and :minus when one is removed (decay)."
([] (decaying-list 10))
([half-life & {:keys [collapse state minus plus capacity]
:or {collapse keep-latest
state nil
minus pass-first
plus pass-first
capacity Long/MAX_VALUE}}]
(DecayingList. (- (/ (Math/log 2) half-life)) ()
(seed (System/currentTimeMillis)) collapse
0 nil
state state plus minus capacity)))
;; example
(defn decaying-memoize [f half-life]
(let [cache (atom (decaying-list half-life
:state {}
:plus (fn [m [args r]]
(if-let [[r n] (m args)]
(assoc m args [r (inc n)])
(assoc m args [r 1])))
:minus (fn [m [args r]]
(let [[r n] (m args)
n (dec n)]
(if (zero? n)
(dissoc m args)
(assoc m args [r n]))))))]
(fn [& args]
(let [m (doto (state @cache) (-> count prn))
r (m args)
r (if r (first r) (apply f args))]
(swap! cache conj [args r])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment