This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2015-07-30
Channels
- # admin-announcements (24)
- # beginners (27)
- # boot (32)
- # cider (9)
- # cljs-dev (2)
- # clojure (96)
- # clojure-berlin (33)
- # clojure-dev (2)
- # clojure-gamedev (2)
- # clojure-germany (1)
- # clojure-italy (8)
- # clojure-japan (2)
- # clojure-russia (21)
- # clojurescript (178)
- # clojutre (3)
- # code-reviews (4)
- # core-async (58)
- # core-logic (22)
- # core-matrix (4)
- # cursive (10)
- # datomic (131)
- # events (9)
- # ldnclj (31)
- # off-topic (57)
- # onyx (9)
- # reagent (23)
@meow: Criterium is the most commonly recommended library for benchmarking Clojure code. https://github.com/hugoduncan/criterium
In the interest of just doing some very basic timing of these functions to get a rough feel for the performance difference between composing transducers vs. my initial naive implementation I did the following:
(defn consume [max ch]
(dorun (repeatedly max #(<!! ch))))
(comment
(time (consume 2000 (chan-of-primes)))
(time (consume 2000 (chan-of-primes-x)))
)
I created a wiki page for this stuff if anyone would like to help with it: https://github.com/clojure/core.async/wiki/Sieve-of-Eratosthenes
Unfortunately, the better version of the code is causing a stack overflow for me when it gets to about 7000 primes.
2 things:
1. on every iteration, you’re creating a new function that is the composition of all previous iterations’ transducers. 2. at some point, when the function is actually executed, it becomes a giant call stack, which can overflow
it’s explained better here: http://stuartsierra.com/2015/04/26/clojure-donts-concat
at least, that’s what it looks like – i didn’t test this code or anything
@erik_price: aha, thank you!
I've read all of the @stuartsierra blog posts in that series and I think they are awesome. Didn't realize that I was creating this problem using comp
.
So now the question is how to comp transducers in a recursive loop without blowing the stack...
@meow: I'd probably use dotimes
for this. That shouldn't blow your stack. I don't think it's a problem with comp
but with repeatedly
rauh: why do you say that? by the 7000th iteration, cur-xf
looks like (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (filter #(not= 0 (mod (…) prime))) prime))) prime))) prime))) prime)))
@rauh: I'm not sure about repeatedly being a problem, but you might know better than me. But I do think comp
is a problem.
(not exactly, but effectively – there is actually an additional anonymous function introduced between each of those recursions)
@erik_price: I'm thinking that maybe it would be better to change the transducer to not be a comp
but instead make use of a collection of all the previous primes to do its filtering.
Major revisions to the wiki page - thanks to all who provided feedback: https://github.com/clojure/core.async/wiki/Sieve-of-Eratosthenes
@meow: Nice. I personally would create a transducer that you could potentially reuse. For instance by solving the more general problem.
Let me explain: I'd create a filter-divisible-previous
transducer that takes a sequence of anything that can filter all elements that are somehow divisble by the previously seen elements
Thus, you can use them with core.async
or really anything. Also you don't have to feed in 2,3,4...
but you also do 2,5,8,11,...
and get interesting results
The implementation looks scary but it's literally one form changed from the distinct
from core
I was also thinking of something along the lines of factor/factorize but between not being a mathematician and not fully groking the transducer code I'm at a loss right now...
@meow: Dive into transducers and make sure you understand partition-by
implementation. After that, everything about transducers is easy
It's not immediately apparent how to change chan-of-primes
to use your transducer and it's been a long day, but I'm hoping a flash of insight comes my way because I have a sense that what you are suggesting is very clever.
I know nothing about partition-by
and am quite new to transducers but this little Game of Primes has been a good learning experience.
That's the most important step. I'm sure you've learned tons of stuff with your core.async implementations.
Yes, as soon as I get something stateful I immediately go to partition-by
or distinct
. 90% of the time I can just use those with some adjustments
so if the transducer has state, it won't make sense for the chan-of-primes
function to also have that same state, right?