Mercurial > rlm

annotate src/rlm/function_utils.clj @ 3:c8e35134bf8e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
working on qotd.
author Robert McIntyre <rlm@mit.edu>
date Wed, 18 Jan 2012 05:18:57 -0700
parents 78a630e650d2
children 12d1367cf1aa
rev   line source
rlm@0 1 ;; Various Operators on Pure Functions
rlm@0 2 ;;
rlm@0 3 ;; Open source Liscence and all that
rlm@0 4 (ns
rlm@0 5 rlm.function-utils
rlm@0 6 "Collection of Operators on Pure Functions"
rlm@0 7 {:author "Robert McIntyre"}
rlm@0 8 (:use [clojure.contrib.profile]))
rlm@0 9
rlm@0 10 (def void ::void)
rlm@0 11
rlm@0 12 (comment
rlm@0 13
rlm@0 14 "Please help me out here. I'm trying to make a higher order function that takes
rlm@0 15 pure functions that are mathmaticaly the same but have different times and returns another
rlm@0 16 function that runs them both and returns the resut of the one that finishes first."
rlm@0 17
rlm@0 18
rlm@0 19 "here's a repl session:
rlm@0 20
rlm@0 21 mobius> " (time (dotimes [_ 500]((mix-futures + +) 40 3 3 3 3 3))) "
rlm@0 22 Elapsed time: 85.792995 msecs
rlm@0 23 nil
rlm@0 24 mobius> " (time (dotimes [_ 500](+ 40 3 3 3 3 3))) "
rlm@0 25 Elapsed time: 6.956338 msecs
rlm@0 26 nil
rlm@0 27 mobius> " (time (dotimes [_ 500]((mix-threads + +) 40 3 3 3 3 3))) "
rlm@0 28 Elapsed time: 706.227065 msecs
rlm@0 29 nil
rlm@0 30
rlm@0 31
rlm@0 32 mobius> " (defn fast-five [& args] 5) "
rlm@0 33 #'mobius/fast-five
rlm@0 34
rlm@0 35 mobius> " (defn slow-five [& args] (Thread/sleep 5000) (println "Oh YEAH!!!!") 5) "
rlm@0 36 #'mobius/slow-five
rlm@0 37
rlm@0 38 mobius> " (profile (time (dotimes [_ 5000] (thread-five)))) "
rlm@0 39 \"Elapsed time: 12187.981587 msecs\"
rlm@0 40 Name mean min max count sum
rlm@0 41 create-atom 9621 2025 4433928 5000 48106830
rlm@0 42 create-threads 5156 2724 2880268 5000 25783796
rlm@0 43 kill-threads 91313 27866 11175718 5000 456567066
rlm@0 44 loop 2124249 38482 18470781 5000 10621249899
rlm@0 45 return 1242 838 5309 5000 6212626
rlm@0 46 start-threads 252985 110348 12272835 5000 1264927953
rlm@0 47 nil
rlm@0 48
rlm@0 49 mobius> " (profile (time (dotimes [_ 5000] (future-five)))) "
rlm@0 50 \"Elapsed time: 607.266671 msecs\"
rlm@0 51 Name mean min max count sum
rlm@0 52 create-atom 1472 1047 31708 5000 7363139
rlm@0 53 create-futures 30539 2514 1330660 5000 152697998
rlm@0 54 kill-threads 54158 2444 3938833 5000 270792897
rlm@0 55 loop 81117 8800 6083059 5000 405587516
rlm@0 56 return 1215 838 618782 5000 6078146
rlm@0 57 nil
rlm@0 58
rlm@0 59
rlm@0 60
rlm@0 61 What can I improve here, and why is the future version sooo much faster than the
rlm@0 62 thread version? Is there a better way than using loop?
rlm@0 63 "
rlm@0 64
rlm@0 65 )
rlm@0 66
rlm@0 67
rlm@0 68 (defn mix
rlm@0 69 "Takes any number of mathematically equal functions with
rlm@0 70 possibly different run-times and returns a function that
rlm@0 71 runs each in a separate thread, returns the result from
rlm@0 72 the first thread which finishes, and cancels the other threads."
rlm@0 73 {:author "Robert McIntyre"}
rlm@0 74 ([& functions]
rlm@0 75 (fn [& args]
rlm@0 76 (let [result (promise)
rlm@0 77 futures (doall (for [fun functions]
rlm@0 78 (future (deliver result (apply fun args)))))
rlm@0 79 answer @result]
rlm@0 80 (dorun (map future-cancel futures))
rlm@0 81 answer))))
rlm@0 82
rlm@3 83 (defn mix-pred
rlm@3 84 "Takes any number of mathematically equal functions with
rlm@3 85 possibly different run-times and returns a function that
rlm@3 86 runs each in a separate thread, returns the result from
rlm@3 87 the first thread which finishes, and cancels the other threads."
rlm@3 88 {:author "Robert McIntyre"}
rlm@3 89 ([pred & functions]
rlm@3 90 (fn [& args]
rlm@3 91 (let [result (promise)
rlm@3 92 futures (doall (for [fun functions]
rlm@3 93 (let [answer (apply fun args)]
rlm@3 94 (if (pred answer)
rlm@3 95 (future (deliver result (apply fun args)))))))
rlm@3 96 answer @result]
rlm@3 97 (dorun (map future-cancel futures))
rlm@3 98 answer))))
rlm@0 99
rlm@0 100
rlm@0 101
rlm@0 102 (defn mix-threads
rlm@0 103 " Takes any number of pure functions that take the same arguments and
rlm@0 104 compute the same value and returns a function that runs each in a separate
rlm@0 105 thread, returns the result from the first thread which finshes, and cancels
rlm@0 106 the other threads. Explicitly uses nasty Threads.
rlm@0 107
rlm@0 108 For example:
rlm@0 109 (do
rlm@0 110 (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 111 (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 112 (time ((mix fun1 fun2))))
rlm@0 113
rlm@0 114 Returns:
rlm@0 115 | Elapsed time: 5000.66214 msecs
rlm@0 116 5"
rlm@0 117 [& functions]
rlm@0 118 (fn [& args]
rlm@0 119 (let [result (prof :create-atom (atom void))
rlm@0 120 threads
rlm@0 121 (prof :create-threads (map
rlm@0 122 (fn [fun]
rlm@0 123 (Thread.
rlm@0 124 (fn []
rlm@0 125 (try (let [answer (apply fun args)]
rlm@0 126 (reset! result answer))
rlm@0 127 (catch Exception _ nil)))))
rlm@0 128 functions))]
rlm@0 129
rlm@0 130 (prof :start-threads (dorun (map #(.start %) threads)))
rlm@0 131 (prof :loop (loop []
rlm@0 132 (if (= (deref result) void)
rlm@0 133 (recur)
rlm@0 134 (do (prof :kill-threads (dorun (map #(.stop %) threads)))
rlm@0 135 (prof :return (deref result)))
rlm@0 136 ))))))
rlm@0 137
rlm@0 138 (defmacro defmix
rlm@0 139 " Defines a function from any number of pure functions that take the same
rlm@0 140 arguments and compute the same value which:
rlm@0 141
rlm@0 142 Runs each in a separate thread.
rlm@0 143 Returns the result from the first thread which finshes.
rlm@0 144 Cancels the other threads.
rlm@0 145
rlm@0 146 Use this whenever you want to combine two pure functions that
rlm@0 147 compute the same thing, but use different algorithms with different
rlm@0 148 run times for various inputs.
rlm@0 149
rlm@0 150 For example:
rlm@0 151 (do
rlm@0 152 (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 153 (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 154 (defmix fun3 \"combination of fun1 and fun2\" fun1 fun2)
rlm@0 155 (time (fun3))
rlm@0 156
rlm@0 157 Returns:
rlm@0 158 | Elapsed time: 5000.66214 msecs
rlm@0 159 5"
rlm@0 160
rlm@0 161 {:arglists '([name doc-string? functions*])}
rlm@0 162
rlm@0 163 [name & functions]
rlm@0 164 (let [doc-string (if (string? (first functions)) (first functions) "")
rlm@0 165 functions (if (string? (first functions)) (rest functions) functions)
rlm@0 166 arglists (:arglists (meta (resolve (eval `(quote ~(first functions))))))
rlm@0 167 name (with-meta name (assoc (meta name) :arglists `(quote ~arglists) :doc doc-string))]
rlm@0 168 `(def ~name (mix ~@functions))))
rlm@0 169
rlm@0 170
rlm@0 171 (defn runonce
rlm@0 172 "Decorator. returns a function which will run only once. Inspired
rlm@0 173 by Halloway's version from lancet."
rlm@0 174 {:author "Robert McIntyre"}
rlm@0 175 [function]
rlm@0 176 (let [sentinel (Object.)
rlm@0 177 result (atom sentinel)]
rlm@0 178 (fn [& args]
rlm@0 179 (locking sentinel
rlm@0 180 (if (= @result sentinel)
rlm@0 181 (reset! result (apply function args))
rlm@0 182 @result)))))
rlm@0 183
rlm@0 184
rlm@0 185
rlm@0 186 ;I'm thinking this will be the docstring for mix eventually.
rlm@0 187
rlm@0 188 ;; " Takes any number of pure functions that take the same arguments and
rlm@0 189 ;; compute the same value and returns a function that runs each in a separate
rlm@0 190 ;; thread, returns the result from the first thread which finshes, and cancels
rlm@0 191 ;; the other threads.
rlm@0 192
rlm@0 193 ;; For example:
rlm@0 194 ;; (do
rlm@0 195 ;; (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 196 ;; (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 197 ;; (time ((mix fun1 fun2))))
rlm@0 198
rlm@0 199 ;; Returns:
rlm@0 200 ;; | Elapsed time: 5000.66214 msecs
rlm@0 201 ;; 5"