Mercurial > rlm

annotate src/rlm/function_utils.clj @ 4:12d1367cf1aa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updating various utilities
author Robert McIntyre <rlm@mit.edu>
date Thu, 01 Mar 2012 05:47:23 -0700
parents c8e35134bf8e
children b8bbb0dbda7b
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@4 68 (defn race
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@4 83 (defn race-pred
rlm@4 84 "Takes any number of mathematically equal functions with possibly
rlm@4 85 different run-times and returns a function that runs each in a
rlm@4 86 separate thread, and returns the first available result x for
rlm@4 87 which (pred x) returns true (or not-valid, if (pred x) returns
rlm@4 88 false on all the results). Cancels the other threads upon
rlm@4 89 returning early."
rlm@3 90 {:author "Robert McIntyre"}
rlm@4 91 ([pred not-valid & functions]
rlm@3 92 (fn [& args]
rlm@3 93 (let [result (promise)
rlm@4 94 latch (java.util.concurrent.CountDownLatch.
rlm@4 95 (count functions))
rlm@4 96 failure-case (future (.await latch)
rlm@4 97 (deliver result not-valid))
rlm@4 98 futures
rlm@4 99 (doall
rlm@4 100 (cons failure-case
rlm@4 101 (for [fun functions]
rlm@4 102 (future
rlm@4 103 (let [answer? (apply fun args)]
rlm@4 104 (if (pred answer?)
rlm@4 105 (deliver result answer?)
rlm@4 106 (.countDown latch)))))))
rlm@3 107 answer @result]
rlm@3 108 (dorun (map future-cancel futures))
rlm@3 109 answer))))
rlm@0 110
rlm@0 111
rlm@0 112
rlm@0 113 (defn mix-threads
rlm@0 114 " Takes any number of pure functions that take the same arguments and
rlm@0 115 compute the same value and returns a function that runs each in a separate
rlm@0 116 thread, returns the result from the first thread which finshes, and cancels
rlm@0 117 the other threads. Explicitly uses nasty Threads.
rlm@0 118
rlm@0 119 For example:
rlm@0 120 (do
rlm@0 121 (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 122 (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 123 (time ((mix fun1 fun2))))
rlm@0 124
rlm@0 125 Returns:
rlm@0 126 | Elapsed time: 5000.66214 msecs
rlm@0 127 5"
rlm@0 128 [& functions]
rlm@0 129 (fn [& args]
rlm@0 130 (let [result (prof :create-atom (atom void))
rlm@0 131 threads
rlm@0 132 (prof :create-threads (map
rlm@0 133 (fn [fun]
rlm@0 134 (Thread.
rlm@0 135 (fn []
rlm@0 136 (try (let [answer (apply fun args)]
rlm@0 137 (reset! result answer))
rlm@0 138 (catch Exception _ nil)))))
rlm@0 139 functions))]
rlm@0 140
rlm@0 141 (prof :start-threads (dorun (map #(.start %) threads)))
rlm@0 142 (prof :loop (loop []
rlm@0 143 (if (= (deref result) void)
rlm@0 144 (recur)
rlm@0 145 (do (prof :kill-threads (dorun (map #(.stop %) threads)))
rlm@0 146 (prof :return (deref result)))
rlm@0 147 ))))))
rlm@0 148
rlm@0 149 (defmacro defmix
rlm@0 150 " Defines a function from any number of pure functions that take the same
rlm@0 151 arguments and compute the same value which:
rlm@0 152
rlm@0 153 Runs each in a separate thread.
rlm@0 154 Returns the result from the first thread which finshes.
rlm@0 155 Cancels the other threads.
rlm@0 156
rlm@0 157 Use this whenever you want to combine two pure functions that
rlm@0 158 compute the same thing, but use different algorithms with different
rlm@0 159 run times for various inputs.
rlm@0 160
rlm@0 161 For example:
rlm@0 162 (do
rlm@0 163 (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 164 (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 165 (defmix fun3 \"combination of fun1 and fun2\" fun1 fun2)
rlm@0 166 (time (fun3))
rlm@0 167
rlm@0 168 Returns:
rlm@0 169 | Elapsed time: 5000.66214 msecs
rlm@0 170 5"
rlm@0 171
rlm@0 172 {:arglists '([name doc-string? functions*])}
rlm@0 173
rlm@0 174 [name & functions]
rlm@0 175 (let [doc-string (if (string? (first functions)) (first functions) "")
rlm@0 176 functions (if (string? (first functions)) (rest functions) functions)
rlm@0 177 arglists (:arglists (meta (resolve (eval `(quote ~(first functions))))))
rlm@0 178 name (with-meta name (assoc (meta name) :arglists `(quote ~arglists) :doc doc-string))]
rlm@0 179 `(def ~name (mix ~@functions))))
rlm@0 180
rlm@0 181
rlm@0 182 (defn runonce
rlm@0 183 "Decorator. returns a function which will run only once. Inspired
rlm@0 184 by Halloway's version from lancet."
rlm@0 185 {:author "Robert McIntyre"}
rlm@0 186 [function]
rlm@0 187 (let [sentinel (Object.)
rlm@0 188 result (atom sentinel)]
rlm@0 189 (fn [& args]
rlm@0 190 (locking sentinel
rlm@0 191 (if (= @result sentinel)
rlm@0 192 (reset! result (apply function args))
rlm@0 193 @result)))))
rlm@0 194
rlm@0 195
rlm@0 196
rlm@0 197 ;I'm thinking this will be the docstring for mix eventually.
rlm@0 198
rlm@0 199 ;; " Takes any number of pure functions that take the same arguments and
rlm@0 200 ;; compute the same value and returns a function that runs each in a separate
rlm@0 201 ;; thread, returns the result from the first thread which finshes, and cancels
rlm@0 202 ;; the other threads.
rlm@0 203
rlm@0 204 ;; For example:
rlm@0 205 ;; (do
rlm@0 206 ;; (defn fun1 [] (Thread/sleep 5000) 5)
rlm@0 207 ;; (defn fun2 [] (Thread/sleep 700000) 5)
rlm@0 208 ;; (time ((mix fun1 fun2))))
rlm@0 209
rlm@0 210 ;; Returns:
rlm@0 211 ;; | Elapsed time: 5000.66214 msecs
rlm@0 212 ;; 5"