On Jul 9, 8:58 am, Christian Marks <[email protected]> wrote:
> The clojure code below applies the constant space algorithm ... of C. J. Gower
... to the computation of the order of a permutation [Knuth, D. E.,
“Selected Papers on Analysis of
> Algorithms,” CSLI Lecture Notes Number 102, CSLI Publications, (2000),p 4]
...
> I'm using recur, however some clojure programmers inform me that recur
> "should" be eliminated in favor of doseq or fold. I see nothing wrong
> with recur myself--am I missing
> something?
>
Not much. If you replace your
> (defn order-perm [perm]
> (let [n (count perm)]
> (loop [i 0 order 1]
> (if (= i n)
> order
> (recur (inc i)
> (if (= i (next-cycle-leader perm i))
> (math/lcm (cycle-length
> perm i) order)
> order))))))
with the more compact
(defn order-permo [perm]
(reduce (fn [order i] (if (= i (next-cycle-leader perm i))
(math/lcm (cycle-length perm i)
order)
order))
1 perm))
you'll be rewarded with better performance with permutations of size
<= 100000,
and slightly worse performance with larger permutations:
knuth=> (load "knuth")
nil
knuth=> (ns knuth)
nil
knuth=> (def p (random-perm 100000))
#'knuth/p
knuth=> (time (order-perm p))
"Elapsed time: 958.706617 msecs"
8124696972786944584881000
knuth=> (time (order-permo p))
"Elapsed time: 908.262712 msecs"
8124696972786944584881000
knuth=> (def p (random-perm 1000000))
#'knuth/p
knuth=> (time (order-perm p))
"Elapsed time: 14699.019199 msecs"
121656328493888810917835084160
knuth=> (time (order-permo p))
"Elapsed time: 15338.770595 msecs"
121656328493888810917835084160
knuth=>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
