Re: Resources on optimizing Clojure code
On Nov 4, 2010, at 1:32 PM, cej38 wrote: > It is wonderful that people are so willing to help with a specific > problem, and I encourage you to continue doing so, but I don't think > anyone has answered the real question. Is there material out there > that describes some of the mechanisms, tools, ideas, etc. that will > allow the average clojure user to optimize their code. Chapter 12 of Joy of Clojure is about performance (type hints, transience, chunked sequences, memoization, coercion). Arguably much of the book is also about what you describe broadly, since it is trying to teach and encourage efficient, idiomatic Clojure usage generally, AIUI. Gary -- 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: Resources on optimizing Clojure code
It is wonderful that people are so willing to help with a specific problem, and I encourage you to continue doing so, but I don't think anyone has answered the real question. Is there material out there that describes some of the mechanisms, tools, ideas, etc. that will allow the average clojure user to optimize their code. Yes, Yes, a good implementation is key, but you need to know the best practices in order to develop that implementation. Not that I have done this myself (yet!) but there are some that argue that reimplementing certain time critical components as macros will greatly speed up the code. See the link below: http://www.bestinclass.dk/index.clj/2010/03/functional-fluid-dynamics-in-clojure.html Optimization is a topic that I would like to see more on. On Nov 2, 1:32 pm, Dan Kefford wrote: > Hello fellow clojurians... > > I've been using Clojure now fairly regularly for the past two months > solving problems on Project Euler. I've been fairly successful solving > them but there are times where the performance of my code either > stinks (the answer may come back in 5-10 minutes) or not at all even > though I have effectively solved the problem (the code is correct and > will return the answer for n < 1000 but for n < 10^8... forget about > it.) > > My question is: are there any materials out there on how to optimize > performance of Clojure code? There doesn't seem to be a lot out there. > > Thanks in advance, > > dan kefford -- 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: Resources on optimizing Clojure code
If you're looking to generate all the numbers with exactly two prime factors (counting multiplicity), I have clojure code that generates the ones up to 10^8 in under two minutes: com.example.sbox=> (time (count (semiprimes-to 1))) "Elapsed time: 106157.33292 msecs" 41803068 It's single-threaded code running on a 2.5GHz machine, so I didn't achieve this through massive parallelism or running it on a Cray or anything. :) If anyone wants more details or the code itself I can post it or email it. -- 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: Resources on optimizing Clojure code
If you want to do this, you can do it simpler, without the loop and temp var: (defn twice-composite? [n] (->> (take-while #(< % n) prime-seq) (every #(or (divides? (* 2 %) n) (not (divides? % n but this is not what you want. See the hints I sent you off the list. On Wed, Nov 3, 2010 at 2:34 PM, Dan Kefford wrote: > One idea that I had was to inline the factoring logic into twice- > composite. Who cares about the factors? We just want to know if there > are two or not: > > (defn twice-composite? [n] > (loop [ps prime-seq > tmp n > p-count 0] > (if (< 2 p-count) > false > (if (= 1 tmp) > (= 2 p-count) > (let [p (first ps)] > (if (divides? tmp p) > (recur ps (quot tmp p) (inc p-count)) > (recur (rest ps) tmp p-count)) > ) > > But this lead to even slower code. > > On Nov 3, 2:15 pm, Mark Engelberg wrote: >> Your Clojure implementation of your particular approach is reasonable, >> but you need a cleverer approach. I'll send you a hint offline. > > -- > 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 -- Cheers, Leif -- 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: Resources on optimizing Clojure code
All the time spent factoring is wasted. You can *construct* and/or count the semiprimes far more efficiently than your method of factoring each number one a time in order to filter the semiprimes from the entire range of numbers up to 10^8. Your approach is fundamentally slow; this has nothing to do with Clojure. I sent you more hints privately. -- 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: Resources on optimizing Clojure code
One idea that I had was to inline the factoring logic into twice- composite. Who cares about the factors? We just want to know if there are two or not: (defn twice-composite? [n] (loop [ps prime-seq tmp n p-count 0] (if (< 2 p-count) false (if (= 1 tmp) (= 2 p-count) (let [p (first ps)] (if (divides? tmp p) (recur ps (quot tmp p) (inc p-count)) (recur (rest ps) tmp p-count)) ) But this lead to even slower code. On Nov 3, 2:15 pm, Mark Engelberg wrote: > Your Clojure implementation of your particular approach is reasonable, > but you need a cleverer approach. I'll send you a hint offline. -- 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: Resources on optimizing Clojure code
Your Clojure implementation of your particular approach is reasonable, but you need a cleverer approach. I'll send you a hint offline. -- 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: Resources on optimizing Clojure code
Sorry for the delayed response. OK... here's an example; my solution to problem 187: (defn divides? [n d] (zero? (rem n d)) ) (declare prime? prime-seq) (defn prime? [n] (if (< n 2) false (every? #(not (divides? n %)) (take-while #(<= (* % %) n) prime- seq))) ) (def prime? (memoize prime?)) (def prime-seq (lazy-seq (concat '(2 3 5 7) (filter #(prime? %) (map #(+ (* 2 %) 7) (iterate inc 1) ) (defn factorize [n] (loop [test-primes prime-seq tmp n retval '()] (if (= 1 tmp) retval (if (prime? tmp) (concat retval (list tmp)) (let [p (first test-primes)] (if (divides? tmp p) (recur test-primes (quot tmp p) (concat retval (list p))) (recur (rest test-primes) tmp retval)) ) (defn twice-composite? [n] (= 2 (count (factorize n))) ) (count (filter twice-composite? (range 1 30))) This appears to be correct, since I get the answer 10 for this one case. However, trying to run for n<10^6 takes 6-11 seconds, and for 10^7 at least three minutes, so running for 10^8 is like going to take on the order of hours. I know that my prime number generator is nowhere near optimal, and I know that in order to efficiently solve a lot of the Euler problems, you cannot simply brute force them; you need to choose your algorithm wisely. Anyway... any suggestions would be greatly appreciated. dan kefford On Nov 2, 4:52 pm, Alan wrote: > Usually it's more about the algorithm than the language. Java can > generally do things faster than clojure, simply because it has fewer > layers, but the speedup is a linear factor. If the java solution for > 1000 elements takes 5ms and your clojure code takes even a second, > it's likely that clojure isn't to blame. Maybe you could post one of > your solutions, or simply compare it to a java solution yourself? > > On Nov 2, 10:32 am, Dan Kefford wrote: > > > Hello fellow clojurians... > > > I've been using Clojure now fairly regularly for the past two months > > solving problems on Project Euler. I've been fairly successful solving > > them but there are times where the performance of my code either > > stinks (the answer may come back in 5-10 minutes) or not at all even > > though I have effectively solved the problem (the code is correct and > > will return the answer for n < 1000 but for n < 10^8... forget about > > it.) > > > My question is: are there any materials out there on how to optimize > > performance of Clojure code? There doesn't seem to be a lot out there. > > > Thanks in advance, > > > dan kefford -- 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: Resources on optimizing Clojure code
Yes, on the handful of Project Euler exercises I've attempted, my algorithm choice was frequently the source of poor performance. Are you familiar with the clojure-euler wiki at http://clojure-euler.wikispaces.com/ ? After I do an Euler exercise I compare my code and runtime with other Clojure submissions, and learn a lot from other people's code. -- 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: Resources on optimizing Clojure code
Usually it's more about the algorithm than the language. Java can generally do things faster than clojure, simply because it has fewer layers, but the speedup is a linear factor. If the java solution for 1000 elements takes 5ms and your clojure code takes even a second, it's likely that clojure isn't to blame. Maybe you could post one of your solutions, or simply compare it to a java solution yourself? On Nov 2, 10:32 am, Dan Kefford wrote: > Hello fellow clojurians... > > I've been using Clojure now fairly regularly for the past two months > solving problems on Project Euler. I've been fairly successful solving > them but there are times where the performance of my code either > stinks (the answer may come back in 5-10 minutes) or not at all even > though I have effectively solved the problem (the code is correct and > will return the answer for n < 1000 but for n < 10^8... forget about > it.) > > My question is: are there any materials out there on how to optimize > performance of Clojure code? There doesn't seem to be a lot out there. > > Thanks in advance, > > dan kefford -- 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
Resources on optimizing Clojure code
Hello fellow clojurians... I've been using Clojure now fairly regularly for the past two months solving problems on Project Euler. I've been fairly successful solving them but there are times where the performance of my code either stinks (the answer may come back in 5-10 minutes) or not at all even though I have effectively solved the problem (the code is correct and will return the answer for n < 1000 but for n < 10^8... forget about it.) My question is: are there any materials out there on how to optimize performance of Clojure code? There doesn't seem to be a lot out there. Thanks in advance, dan kefford -- 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
