Re: Question on eliminating recur
On Jul 13, 1:16 am, Christian Marks 9fv...@gmail.com wrote: Thank you. Based on this I've simplified the code further. You could combine the test for a cycle leader with the cycle length count--but your original code, which calculates cycle lengths only if a cycle leader is identified, is more efficient! (ns knuth (:require [clojure.contrib.math :as math])) (defn random-perm [n] (shuffle (range n))) (defn cycle-leader-length [perm i] (loop [cycle 1 j (nth perm i)] (cond ( j i) 1 (= j i) cycle :else (recur (inc cycle) (nth perm j) (defn order-perm [perm] (reduce (fn [order i] (math/lcm (cycle- leader-length perm i) order)) 1 perm)) -- 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
Re: Question on eliminating recur
On Jul 10, 10:16 pm, FL florian.leng...@gmail.com wrote: \ If you replace your ... (defn order-perm [perm] (let [n (count perm)] ... 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 = 10, Thank you. Based on this I've simplified the code further. The (new) predicate (cycle-leader? perm i) is true if and only if i is the least element of the unique cycle containing i in the permutation perm. This is more readable, though the extra test compared with the original adds to execution time. (ns knuth (:require [clojure.contrib.math :as math])) (defn random-perm [n] (shuffle (range n))) (defn cycle-leader? [perm i] (loop [j (nth perm i)] (cond ( j i) false (= j i) true :else (recur (nth perm j) (defn cycle-length [perm i] (loop [cycle 1 j (nth perm i)] (if (= i j) cycle (recur (inc cycle) (nth perm j) (defn order-perm [perm] (reduce (fn [order i] (if (cycle-leader? perm i) (math/lcm (cycle-length perm i) order) order)) 1 perm)) -- 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
Re: Question on eliminating recur
On Jul 10, 7:15 am, Michael Gardner gardne...@gmail.com wrote: I think Christian wanted to know *why* one should eliminate recur. I can't think of a reason to avoid it myself, though I also don't recall hearing any recommendations against using recur. Just my two cents, but the main reason to consider map/doseq/reduce/ filter etc in favor of loop/recur is that if your algorithm matches one of the former, you'll need a little less boiler-plate code (sometimes), makes it easier to use/create lazy sequences and (most importantly) using map/doseq etc when appropriate conveys a lot of information about the structure of the algorithm and its input/output expectations to the human reader. -- 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
Re: Question on eliminating recur
On Jul 9, 8:58 am, Christian Marks 9fv...@gmail.com 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 = 10, and slightly worse performance with larger permutations: knuth= (load knuth) nil knuth= (ns knuth) nil knuth= (def p (random-perm 10)) #'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 100)) #'knuth/p knuth= (time (order-perm p)) Elapsed time: 14699.019199 msecs 12165632849310917835084160 knuth= (time (order-permo p)) Elapsed time: 15338.770595 msecs 12165632849310917835084160 knuth= -- 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
Question on eliminating recur
The clojure code below applies the constant space algorithm to apply a permutation to an array 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]. The order of a permutation is the least common multiple of its cycle lengths; the function order-perm below makes use of the associativity of the least common multiple. 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? (ns knuth (:require [clojure.contrib.math :as math])) (defn random-perm [n] (shuffle (range n))) (defn next-cycle-leader [perm i] (loop [j (nth perm i)] (if (= j i) j (recur (nth perm j) (defn cycle-length [perm i] (loop [cycle 1 j (nth perm i)] (if (= i j) cycle (recur (inc cycle) (nth perm j) (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)) -- 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
Re: Question on eliminating recur
On Sat, Jul 9, 2011 at 8:58 AM, Christian Marks 9fv...@gmail.com wrote: 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? If there is an obvious way to rewrite the code using doseq or fold (or reduce or map or etc), then yes- you should do it. However, if this way to rewrite the code isn't obvious in 10 seconds of thought, don't worry about it. Use loop/recur. The goal is clear, concise code- not blind obedience to aphorisms. Brian -- 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
Re: Question on eliminating recur
On Jul 9, 2011, at 8:47 AM, Brian Hurt wrote: If there is an obvious way to rewrite the code using doseq or fold (or reduce or map or etc), then yes- you should do it. However, if this way to rewrite the code isn't obvious in 10 seconds of thought, don't worry about it. Use loop/recur. The goal is clear, concise code- not blind obedience to aphorisms. I think Christian wanted to know *why* one should eliminate recur. I can't think of a reason to avoid it myself, though I also don't recall hearing any recommendations against using recur. -- 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
