Hello,
I would like to extend the examples section on clojure wiki with
parallel factorial example codes (one version is sligtly simpler, one
performs better).
Your feedback on the code is more than welcome, as I still consider
myself beginner on clojure (but coming up with the algorithm +
implementing it in clojure was a good exercise).
Both versions should be attached to this message (i did not include
them directly in e-mail as formatting gets usually messed up).
Kind regards,
Vladimir
--
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
; parallel version of factorial
; no any guarantees for this code - it is a toy implementation and
; could be incorrect
; idea is to apply * in parallel to a set of ranges
; (each of which represent the number n)
; n - calculate factorial of this number
; m - number of digits of n (used to partition the number)
; z - the whole part of n/m
; partitions number n which is long m decimal digits into ranges
; fixme: the m should be calculated from n but this way one can decide
; on the number of partitions by hand
; also, the partitioning is not optimal (large number take longer to multiply)
(defn part-num [n m]
(let [z (quot n m)
last-range (range (+ (* z m) 1) (+ n 1))
]
(cons (if last-range last-range '(1))
(for [x (range m)]
(range (+ (* x z) 1) (+ (* (+ x 1) z) 1))
)
)
)
)
; the same argumets as part-num
; e.g. call (pfactorial 100000 6); takes around 5 seconds on core 2 duo
(defn pfactorial [n m]
(let [agents (map agent (part-num n m))]
(doseq [a agents]
(send a #(apply * %)))
(apply await agents)
(let [result (apply * (map deref agents))]
(doseq [a agents]
(send a (fn [_] nil)))
result)
)
)
; parallel factorial - version 2
; this 2nd version multiplies the intermediate results also in parallel
; fixed to also work with clojure 1.1.0-alpha
; no any guarantees for this code - it is a toy implementation and
; could be incorrect
; idea is to apply * in parallel to a set of ranges
; (which represent the number n),
; after this, a set of agents is set up to multiply 2 intermediate results each
; n - calculate factorial of this number
; m - how many intervals the number n should be partitioned into
; z - the whole part of n/m
; partitions number n which to m ranges
; fixme: the m should be calculated from n but this way one can decide
; on the number of partitions by hand
; also, the partitioning is not optimal (large number take longer to multiply)
(defn part-num [n m]
(let [z (quot n m)
last-range (range (+ (* z m) 1) (+ n 1))
]
(cons (if (= last-range '()) '(1) last-range)
(for [x (range m)]
(range (+ (* x z) 1) (+ (* (+ x 1) z) 1))
)
)
)
)
; the same argumets as part-num
; e.g. call (pfactorial 1000000 500)
; for benchmarking: (time (def x (pfactorial 1000000 500)))
; the above takes around 315 seconds on core 2 duo, 2.66GHz, 64 bit linux
(defn pfactorial [n m]
(let [agents (map agent (part-num n m))] ; create agents containing ranges
(doseq [a agents]
(send a #(apply * %))) ; make each agent multiply numbers of it's range
(apply await agents) ; wait until all agents finish
; do multiplication of intermediate results in parallel
(loop [lon (map deref agents)] ; lon - list of numbers
; (println (count lon))
(if (= (count lon) 1) ; do we have a result?
(first lon)
(let [ags (map agent (partition 2 lon))] ; multiply 2 numbers in agent
(doseq [a ags]
(send a #(apply * %)))
(apply await ags)
(if (= (mod (count lon) 2) 0) ; even number of numbers in lon?
(recur (map deref ags))
(recur (cons (last lon) (map deref ags)))
)
)
)
)
)
)
