gistfile1.clj

;; this code requires a Clojure built from https://github.com/cgrand/clojure/tree/fold+transients
;;
;; currently (with master) frequencies can't be written with both fold and transients
;; with my branch you can.
;; however the contract for the combinef function evolves:
;; O arg -> init value for reduce
;; 1 arg -> "clean" the return value of reduce (was undefined) -- in general case, it's the identity
;; 2 args -> combine the two values
;;
;; it follows that the true zero of a monoid is now returned by (m (m)) but this affects only people implementing coll-fold.

(require '[clojure.core.reducers :as r])

(defn freqs
  "Returns a map from distinct items in coll to the number of times
  they appear."
  [coll]
  (r/fold (r/monoid #(merge-with + %1 %2)
                    #(transient {})
                    persistent!)
          (fn [counts x]
             (assoc! counts x (inc (get counts x 0))))
          coll))

(def v (vec (range 1e6)))

user=> (dotimes [_ 5] (time (frequencies (r/map #(mod % 4) v))))
"Elapsed time: 492.985 msecs"
"Elapsed time: 475.717 msecs"
"Elapsed time: 497.596 msecs"
"Elapsed time: 487.6 msecs"
"Elapsed time: 494.925 msecs"
nil
user=> (dotimes [_ 5] (time (freqs (r/map #(mod % 4) v))))
"Elapsed time: 278.794 msecs"
"Elapsed time: 297.867 msecs"
"Elapsed time: 269.598 msecs"
"Elapsed time: 270.54 msecs"
"Elapsed time: 253.276 msecs"
nil