Re: Working with a huge graph - how can I make Clojure performant?

[Balint Erdi]

In fact I did. At first glance it seemed like it would have the same issues 
as my algorithm for really large graphs. However, there is no certainty 
without actually trying so I might give it a go with the huge graph.

Thank you for bringing it up.

On Thursday, March 28, 2013 3:29:01 PM UTC+1, Niels van Klaveren wrote:
>
> Perhaps for inspiration have a look at Christophe Grand's implementation 
> of Tarjan's 
> algorithm<http://clj-me.cgrand.net/2013/03/18/tarjans-strongly-connected-components-algorithm/>(which
>  is a more efficient version of Kosaraju's).
>
> On Thursday, March 28, 2013 12:06:45 PM UTC+1, Balint Erdi wrote:
>>
>> Yes, that's definitely a good idea. I tried a few other things (including 
>> that, I think) after I posted that but nothing really worked and it turned 
>> out that the tail-recursive version even had a bug.
>>
>> I couldn't find a way to really keep the amount of copying of the data 
>> structures (stack, finished above) very low and thus my algorithm was slow. 
>> I know that the data structures are persistent and share structure but it 
>> still was slow for that many elements.
>>
>> I finally solved the problem by implementing an imperative solution with 
>> Java arrays and type hints. It ran in ~20-30 seconds.
>>
>> On Thursday, March 28, 2013 2:22:44 AM UTC+1, Stephen Compall wrote:
>>>
>>> On Mon, 2013-03-11 at 10:37 -0700, Balint Erdi wrote: 
>>> >   (let [neighbors (persistent! 
>>> >(reduce 
>>> > (fn [c u] (if (explored u) c (conj! c u))) 
>>> > (transient []) 
>>> > (G v)))] 
>>>
>>> What happens if you do ^^^ *after* vvv? 
>>>
>>> >  (explored v) (recur vs explored lhalf rhalf (inc 
>>> iter-cnt)) 
>>>
>>> -- 
>>> Stephen Compall 
>>> "^aCollection allSatisfy: [:each | aCondition]": less is better than 
>>>
>>>
>>>

-- 
-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: Working with a huge graph - how can I make Clojure performant?

[Balint Erdi]

Yes, that's definitely a good idea. I tried a few other things (including 
that, I think) after I posted that but nothing really worked and it turned 
out that the tail-recursive version even had a bug.

I couldn't find a way to really keep the amount of copying of the data 
structures (stack, finished above) very low and thus my algorithm was slow. 
I know that the data structures are persistent and share structure but it 
still was slow for that many elements.

I finally solved the problem by implementing an imperative solution with 
Java arrays and type hints. It ran in ~20-30 seconds.

On Thursday, March 28, 2013 2:22:44 AM UTC+1, Stephen Compall wrote:
>
> On Mon, 2013-03-11 at 10:37 -0700, Balint Erdi wrote: 
> >   (let [neighbors (persistent! 
> >(reduce 
> > (fn [c u] (if (explored u) c (conj! c u))) 
> > (transient []) 
> > (G v)))] 
>
> What happens if you do ^^^ *after* vvv? 
>
> >  (explored v) (recur vs explored lhalf rhalf (inc iter-cnt)) 
>
> -- 
> Stephen Compall 
> "^aCollection allSatisfy: [:each | aCondition]": less is better than 
>
>
>

-- 
-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Working with a huge graph - how can I make Clojure performant?

[Balint Erdi]

 

Hey,


I got an assignment to implement an algorithm to calculate strongly 
connected components in a graph (
http://en.wikipedia.org/wiki/Kosaraju's_algorithm). The graph is rather 
big, it has ~900.000 vertices.


In its first pass, it needs to do a depth-first search on the graph and 
calculate the finishing time for each node (the finishing time for a node 
is a number from 0…V-1 where V is the number of vertices). Potentially 
several depth-first search need to be launched (done in the finishing-times 
function below) to discover all components.


The version I pasted below is the most performant. It discovers ~600.000 
vertices (2/3 of all vertices). However, on subsequent 
dfs-by-finishing-times it becomes extremely slow (exploring a handful of 
additional nodes/second) and I'm not sure why.


Here are a few things I tried to speed up the algorithm:


* rewrite to a recursive function (not tail-recursive) and use lazy-seqs

* define dfs-by-finishing-times in finishing-times so that the whole graph 
(G) does not have to be passed at each call.

* use persistent data structures everywhere instead of transients (I know 
this would only slow things down but it did not hurt to try)

* use a profiler (VisualVM) to learn where the bottlenecks are. I'm not 
very proficient with profilers but I could not extract any valuable 
information


Here are the code snippets in question:

(I also pasted it 
here: https://www.refheap.com/paste/3840cc772cc3a5b1d9c4f1db3 for better 
readability)

(defn dfs-by-finishing-times

  ([G u]

 (dfs-by-finishing-times G u #{}))

  ([G u explored]

 (loop [[v & vs :as stack] (list u), explored (transient explored), 
lhalf [], rhalf [],  iter-cnt 0]

 (if (seq stack)

  (let [neighbors (persistent!

   (reduce

(fn [c u] (if (explored u) c (conj! c u)))

(transient [])

(G v)))]

(cond

 (explored v) (recur vs explored lhalf rhalf (inc iter-cnt))

 (empty? neighbors) (recur vs (conj! explored v) (conj lhalf v) 
rhalf (inc iter-cnt))

 :else (recur (reduce (fn [stack e] (cons e stack)) vs 
neighbors)

   (conj! explored v)

   lhalf

   (cons v rhalf)

   (inc iter-cnt

  (concat lhalf rhalf)))

 ))


(defn finishing-times [G vertices]

  "The first pass of Kosaraju's algorithm.

   Scan the transpose graph of G, and mark the finishing time for each.

   G should already be the transposed graph"

  (loop [[u & vs :as stack] (seq vertices)

  explored #{},

  finished []]

 (if (nil? u)

   finished

   (let [path (dfs-by-finishing-times G u explored)

 new-explored (into explored path)]

 (recur (remove new-explored vs)

new-explored

(into finished path))

Do you have any insights into what technique I could use to speed up my 
algorithm? I'm pretty sure I'm missing a key point but I'm not sure 
what. Presumably the whole algorithm runs under 10 seconds in C# on the 
same graph so this is rather embarrassing :)

Appreciate your help,

Balint

-- 
-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: how would you implement sending out a verification email?

[Balint Erdi]

Hey James,

That works as long as there is only one thing with side-effects. In the 
above example I could e.g have the sending of the email logged and so I can 
no longer use this method. What I'd like to see is whether the top-level 
construct -wrapping the sending of the email by an agent in a transaction 
that also updates the database record and potentially logs the fact- is the 
ideal one here or we can do better.

Thank you.

On Thursday, February 21, 2013 3:46:24 AM UTC+1, James Reichley wrote:
>
> I can't find the reference now, but either in a screencast or a discussion 
> I read it was mentioned that if you have a single thing that performs 
> side-effects, you can perform this function last in the transaction without 
> worrying about any issues. The reasoning here is that if anything before it 
> fails, the side-effect action was never attempted and if the side-effect 
> action itself fails then the transaction rolls back like always.
>
> On Wednesday, February 20, 2013 9:32:14 AM UTC-5, Balint Erdi wrote:
>>
>>  Hey, 
>>
>> So yesterday we discussed concurrency at our meetup (
>> http://www.meetup.com/Budapest-Clojure-User-Group/) and a question 
>> occurred to me.
>>
>> Suppose we have a classic web application. (I'm not currently building 
>> such a web app in Clojure, so that's a "theoretical" question).
>>
>> When the user signs up, a verification email has to be sent and the 
>> database entry related to the user has to be updated (or a new datom 
>> created ;) ) to reflect the fact that we've sent out the email to the user.
>>
>> First, we want this to be consistent so that the "verification_sent_out" 
>> db field reflects whether the email has really been sent out or not. 
>> Secondly, we also want the email to only be sent out once.
>>
>> My first idea was to use a transaction but if the transaction retries, 
>> the email could be sent out several times. A fellow Clojurian advised the 
>> sending of the email to be performed by an agent. The agent is "transaction 
>> aware" so if the wrapping transaction is retried several times it only 
>> sends out the email when the transaction successfully runs.
>>
>> Is this how this actually works? Is there another, simpler and/or more 
>> robust solution? In the languages I come from (e.g Ruby) I'd use a library 
>> that handles the queueing and consumption of tasks. Is this how you'd do it 
>> in Clojure or it's one of these cases where Clojure itself suffices where 
>> other languages are lacking?
>>
>> Thank you for your answer,
>> -- 
>> Balint
>>
>>

-- 
-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

how would you implement sending out a verification email?

[Balint Erdi]

Hey, 

So yesterday we discussed concurrency at our meetup 
(http://www.meetup.com/Budapest-Clojure-User-Group/) and a question occurred to 
me.

Suppose we have a classic web application. (I'm not currently building such a 
web app in Clojure, so that's a "theoretical" question).

When the user signs up, a verification email has to be sent and the database 
entry related to the user has to be updated (or a new datom created ;) ) to 
reflect the fact that we've sent out the email to the user.

First, we want this to be consistent so that the "verification_sent_out" db 
field reflects whether the email has really been sent out or not. Secondly, we 
also want the email to only be sent out once.

My first idea was to use a transaction but if the transaction retries, the 
email could be sent out several times. A fellow Clojurian advised the sending 
of the email to be performed by an agent. The agent is "transaction aware" so 
if the wrapping transaction is retried several times it only sends out the 
email when the transaction successfully runs.

Is this how this actually works? Is there another, simpler and/or more robust 
solution? In the languages I come from (e.g Ruby) I'd use a library that 
handles the queueing and consumption of tasks. Is this how you'd do it in 
Clojure or it's one of these cases where Clojure itself suffices where other 
languages are lacking? 

Thank you for your answer,-- 
Balint

-- 
-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: Clojure user group in Budapest just launched

[Balint Erdi]

Great, just sent the pull request. 


On Friday, January 11, 2013 at 4:03 PM, Michael Klishin wrote:

> 2013/1/11 Balint Erdi mailto:balint.e...@gmail.com)>
> > Delighted to announce that the Budapest Clojure Group has just launched:
> > 
> > http://www.meetup.com/Budapest-Clojure-User-Group/
> Balint,
> 
> Please consider adding it to the User Groups page on http://clojure-doc.org.
> All it takes is a pull request on GitHub that edits [1].
> 
> 1. 
> https://github.com/clojuredocs/cds/blob/master/articles/ecosystem/user_groups.md
>  
> -- 
> MK
> 
> http://github.com/michaelklishin
> http://twitter.com/michaelklishin
> -- 
> 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 
> (mailto: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 
> (mailto:clojure+unsubscr...@googlegroups.com)
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en 

-- 
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

Clojure user group in Budapest just launched

[Balint Erdi]

Hey,

Delighted to announce that the Budapest Clojure Group has just launched:

http://www.meetup.com/Budapest-Clojure-User-Group/

The official language is English so consider joining/attending if you're 
from a relatively close city but don't speak Hungarian (Bratislava & Vienna 
come to mind).

One city closer to world domination!

Balint
http://twitter.com/baaz

-- 
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: group-by vs. reducers?

[Balint Erdi]

Thank you, Christophe, that makes total sense.

Interestingly, on my machine, the reducers version is still slower:

Run # 0
"Elapsed time: 1105.586 msecs"
"Elapsed time: 685.8 msecs"
"Elapsed time: 549.969 msecs"
Run # 1
"Elapsed time: 497.831 msecs"
"Elapsed time: 489.932 msecs"
"Elapsed time: 520.38 msecs"
Run # 2
"Elapsed time: 363.873 msecs"
"Elapsed time: 489.529 msecs"
"Elapsed time: 556.117 msecs"
Run # 3
"Elapsed time: 357.822 msecs"
"Elapsed time: 429.894 msecs"
"Elapsed time: 540.975 msecs"
Run # 4
"Elapsed time: 425.276 msecs"
"Elapsed time: 431.819 msecs"
"Elapsed time: 528.8 msecs"

I guess the JVM finds some serious optimizations during the runs for the 
non-reducer versions. I saw the same difference when using criterium for 
benchmarking.

Balint

On Friday, December 7, 2012 1:44:58 PM UTC+1, Christophe Grand wrote:
>
> Absolutely
>
>
> On Fri, Dec 7, 2012 at 1:29 PM, László Török 
> > wrote:
>
>> Hi,
>>
>> shouldn't 
>>
>> (fn [groups a]
>>   (assoc groups (f a) (conj (get groups a []) a)))
>>
>> be 
>>
>> (fn [groups a]
>>   (let [k (f a)]
>> (assoc groups k (conj (get groups k []) a
>>
>> ?
>>
>> Las
>>
>> 2012/12/7 Christophe Grand >
>>
>>> Hi,
>>>
>>> There are indeed too much allocationfoing on in your r/map.
>>> You don't need the rmap,
>>>
>>> Start from a plain old reduce like your reduce-by-naive, replace reduce 
>>> by r/fold, remove the seed and add the combine-fn (which now provides the 
>>> seed):
>>>
>>> (defn group-by-red [f coll]
>>>   (r/fold
>>> (partial merge-with concat)
>>> (fn [groups a]
>>>   (assoc groups (f a) (conj (get groups a []) a)))
>>> coll))
>>>
>>>
>>> Crude benchmark;
>>>  (let [v (vec (range 100))] 
>>>   (dotimes [n 5]
>>> (println "Run" n)
>>> (time (group-by #(mod % 29) v))
>>> (time (group-by-naive #(mod % 29) v))
>>> (time (group-by-red #(mod % 29) v
>>> Run 0
>>> "Elapsed time: 938.878 msecs"
>>> "Elapsed time: 778.161 msecs"
>>> "Elapsed time: 1035.997 msecs"
>>> Run 1
>>> "Elapsed time: 715.352 msecs"
>>> "Elapsed time: 771.913 msecs"
>>> "Elapsed time: 840.264 msecs"
>>> Run 2
>>> "Elapsed time: 656.588 msecs"
>>> "Elapsed time: 700.114 msecs"
>>> "Elapsed time: 777.323 msecs"
>>> Run 3
>>> "Elapsed time: 731.781 msecs"
>>> "Elapsed time: 713.547 msecs"
>>> "Elapsed time: 875.801 msecs"
>>> Run 4
>>> "Elapsed time: 689.711 msecs"
>>> "Elapsed time: 710.728 msecs"
>>> "Elapsed time: 1112.609 msecs"
>>> nil
>>>
>>> Let's play with the granularity (defaults to 512)
>>> (defn group-by-red [f coll]
>>>   (r/fold 2048
>>> (partial merge-with concat)
>>> (fn [groups a]
>>>   (assoc groups (f a) (conj (get groups a []) a)))
>>> coll))
>>>
>>> Re-benchmark:
>>> Run 0
>>> "Elapsed time: 810.676 msecs"
>>> "Elapsed time: 736.764 msecs"
>>> "Elapsed time: 547.651 msecs"
>>> Run 1
>>> "Elapsed time: 681.249 msecs"
>>> "Elapsed time: 850.046 msecs"
>>> "Elapsed time: 521.27 msecs"
>>> Run 2
>>> "Elapsed time: 669.385 msecs"
>>> "Elapsed time: 712.15 msecs"
>>> "Elapsed time: 518.502 msecs"
>>> Run 3
>>> "Elapsed time: 673.108 msecs"
>>> "Elapsed time: 745.688 msecs"
>>> "Elapsed time: 542.837 msecs"
>>> Run 4
>>> "Elapsed time: 654.196 msecs"
>>> "Elapsed time: 723.074 msecs"
>>> "Elapsed time: 506.861 msecs"
>>>
>>> Note that you are not exactly comparing apples to apples since 
>>> group-by-red is returning maps whose values are unrealized lazy sequence 
>>> (concats of concats of ocncats of vactors) instead of vectors
>>>
>>> (defn group-by-red [f coll]
>>>   (r/fold 2048
>>> (partial merge-with into)
>>> (fn [g

Re: group-by vs. reducers?

[Balint Erdi]

BTW I understood the most about reducers (still not quite there yet, though 
:) ) from Rich Hickey's talk at EuroClojure:

https://vimeo.com/45561411

On Friday, December 7, 2012 10:21:59 AM UTC+1, Balint Erdi wrote:
>
> Hey,
>
> Reducers is fascinating and quite complex at the same time. I feel like 
> "best practices" around it has not quite solidified yet.
>
> Here is how I made your example work:
>
> (ns group-by-reducers.core
>   (:require [clojure.core.reducers :as r :only [fold reduce map]])
>   (:require [criterium.core :as c]))
>
> (defn group-by-naive [f coll]
>   (reduce
> (fn [groups a]
>   (assoc groups (f a) (conj (get groups a []) a)))
> {}
> coll))
>
> (defn group-by-red [f coll]
>   (letfn [(reduce-groups
> ([] {})
> ([g1 g2]
>   (merge-with concat g1 g2)))]
> (r/fold reduce-groups (r/map #(hash-map (f %) [%]) coll
>
> (defn -main
>   [& args]
>   (c/quick-bench (group-by #(mod % 29) (range 1)))
>   (c/quick-bench (group-by-naive #(mod % 29) (range 1)))
>   (c/quick-bench (group-by-red #(mod % 29) (range 1
>
> (available as a gist here: https://gist.github.com/4232044)
>
> The core and naive versions perform roughly equally (~4ms) while the 
> reducers version takes 10x as much time (~40ms) on my two-core laptop.
>
> I'm absolutely sure I'm doing something wrong (there is probably too much 
> memory allocated by the map function) and would like to hear the opinion of 
> someone more knowledgeable with reducers. I just did not want the subject 
> to be buried.
>
> Hope that still helps a bit,
> Balint
>
> ps. There are some tips and tricks in this post: 
> http://www.thebusby.com/2012/07/tips-tricks-with-clojure-reducers.html
>
> On Monday, December 3, 2012 5:04:17 PM UTC+1, Las wrote:
>>
>> Hi,
>>
>> As I was trying to wrap my head around the reducers library[1], I thought 
>> implementing group-by would be a good exercise to gain some insight.
>>
>> After spending a few hours with it, I'm still pretty much clueless, so 
>> hope to find someone here to help me out:
>>
>> So if I understood the reducer lingo introduced in [2],[3] and group-by 
>> correctly, it reduces the following reducing function on a collection
>>
>> (fn group-by-reducef [keyfn ret x]
>>  (let [k (keyfn x)]
>> (assoc ret k (conj (get ret k []) x
>>
>> where keyfn is provided by a partial function application.
>>
>> fold needs a combining function that takes two result maps that have 
>> already been grouped and merges them.
>> A naive implementation could look like
>>
>> (defn group-by-combinef
>>   ([] {})
>>   ([g1 g2]
>>  (persistent!
>>   (reduce (fn [res k v]
>> (assoc! res k (into (get res k []) v)))
>>   (transient g1) g2
>>
>> (defn group-by [f coll]
>>   (fold (partial gr-by-reducef f) gr-by-combinef coll))
>>
>> Now couple of questions:
>> 1) I expected fold to actually perform the operation, how can I force it 
>> to give me the result?
>> 2) Can somehow the actual reducing at the leaf nodes still take advantage 
>> of transient collections?
>> 3) I took a look at flatten as it seems the "closest" match. Again, if I 
>> call (flatten [[1 2] [2 4]]), I don't actually get the result. How do I get 
>> to the result?
>>
>>
>> Thanks!
>>
>> [1] 
>> https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj
>> [2] 
>> http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html
>> [3] http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html
>> -- 
>> László Török
>>
>> 

-- 
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: group-by vs. reducers?

[Balint Erdi]

Hey,

Reducers is fascinating and quite complex at the same time. I feel like 
"best practices" around it has not quite solidified yet.

Here is how I made your example work:

(ns group-by-reducers.core
  (:require [clojure.core.reducers :as r :only [fold reduce map]])
  (:require [criterium.core :as c]))

(defn group-by-naive [f coll]
  (reduce
(fn [groups a]
  (assoc groups (f a) (conj (get groups a []) a)))
{}
coll))

(defn group-by-red [f coll]
  (letfn [(reduce-groups
([] {})
([g1 g2]
  (merge-with concat g1 g2)))]
(r/fold reduce-groups (r/map #(hash-map (f %) [%]) coll

(defn -main
  [& args]
  (c/quick-bench (group-by #(mod % 29) (range 1)))
  (c/quick-bench (group-by-naive #(mod % 29) (range 1)))
  (c/quick-bench (group-by-red #(mod % 29) (range 1

(available as a gist here: https://gist.github.com/4232044)

The core and naive versions perform roughly equally (~4ms) while the 
reducers version takes 10x as much time (~40ms) on my two-core laptop.

I'm absolutely sure I'm doing something wrong (there is probably too much 
memory allocated by the map function) and would like to hear the opinion of 
someone more knowledgeable with reducers. I just did not want the subject 
to be buried.

Hope that still helps a bit,
Balint

ps. There are some tips and tricks in this 
post: http://www.thebusby.com/2012/07/tips-tricks-with-clojure-reducers.html

On Monday, December 3, 2012 5:04:17 PM UTC+1, Las wrote:
>
> Hi,
>
> As I was trying to wrap my head around the reducers library[1], I thought 
> implementing group-by would be a good exercise to gain some insight.
>
> After spending a few hours with it, I'm still pretty much clueless, so 
> hope to find someone here to help me out:
>
> So if I understood the reducer lingo introduced in [2],[3] and group-by 
> correctly, it reduces the following reducing function on a collection
>
> (fn group-by-reducef [keyfn ret x]
>  (let [k (keyfn x)]
> (assoc ret k (conj (get ret k []) x
>
> where keyfn is provided by a partial function application.
>
> fold needs a combining function that takes two result maps that have 
> already been grouped and merges them.
> A naive implementation could look like
>
> (defn group-by-combinef
>   ([] {})
>   ([g1 g2]
>  (persistent!
>   (reduce (fn [res k v]
> (assoc! res k (into (get res k []) v)))
>   (transient g1) g2
>
> (defn group-by [f coll]
>   (fold (partial gr-by-reducef f) gr-by-combinef coll))
>
> Now couple of questions:
> 1) I expected fold to actually perform the operation, how can I force it 
> to give me the result?
> 2) Can somehow the actual reducing at the leaf nodes still take advantage 
> of transient collections?
> 3) I took a look at flatten as it seems the "closest" match. Again, if I 
> call (flatten [[1 2] [2 4]]), I don't actually get the result. How do I get 
> to the result?
>
>
> Thanks!
>
> [1] 
> https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj
> [2] 
> http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html
> [3] http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html
> -- 
> László Török
>
> 

-- 
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: confused about the scope of variables, or is it something else? ClojureScript

[Balint Erdi]

As Sean suggested you should use doseq instead of for and map to force 
side-effects:
http://clojuredocs.org/clojure_core/clojure.core/doseq

Since doseq uses the exact same syntax as for, you should just write doseq 
in its place. map should be converted to doseq syntax, too.

Balint

On Monday, December 3, 2012 9:16:02 PM UTC+1, Arash Bizhan zadeh wrote:
>
> So what should I do? would using fmap helps? 
> I have used let initially, but I moved away to make it as close as 
> possible to my repl code/.
>
>
> On Sunday, December 2, 2012 8:31:55 PM UTC-5, Sean Corfield wrote:
>>
>> Part of it is laziness: map is lazy so it doesn't do anything unless you 
>> use the result. In the REPL, you print the result so map runs across the 
>> whole sequence. In the function, only the last expression (draggables) is 
>> returned so it is the only thing fully evaluated.
>>
>> Your code is very procedural tho'... you should not have 'def' anywhere 
>> except the top-level (since it always creates top-level definitions - 
>> globals). You probably want 'let' for local definitions. Since you want 
>> non-lazy behavior, you're not going to want 'for' or 'map' - look at 
>> 'doseq' instead.
>>
>> Hope that helps? 
>>
>>
>> On Sun, Dec 2, 2012 at 5:25 PM, Arash Bizhan zadeh wrote:
>>
>>> I am playing with clojurescript, and I have this code:
>>>
>>> (defn prepare [number]
>>>   (def targets (take 4 (drop (* 4 (- number 1)) (dom/getElementsByClass 
>>> "place-div"
>>>   (def target-objects (map #(make-target %) targets))
>>>   (for [drag draggables target target-objects]
>>> (.addTarget drag target))
>>>   (map #(.init %)  draggables)
>>>   (map #(.init %) target-objects)
>>>   draggables)
>>>
>>> It basically creates  a bunch of dragNdrop objects.
>>> This code doesn't work in this method - no error, just doesn't do the 
>>> job - 
>>> but if I execute the lines one at a time from repl, it works fine.
>>> Can someone please explain what the heck is going on ?
>>>
>>> much appreciated.
>>>
>>> -- 
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To post to this group, send email to clo...@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+u...@googlegroups.com
>>> For more options, visit this group at
>>> http://groups.google.com/group/clojure?hl=en
>>
>>
>>
>>
>> -- 
>> Sean A Corfield -- (904) 302-SEAN
>> An Architect's View -- http://corfield.org/
>> World Singles, LLC. -- http://worldsingles.com/
>>
>> "Perfection is the enemy of the good."
>> -- Gustave Flaubert, French realist novelist (1821-1880)
>>  
>

-- 
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

Starting a Clojure user group in Budapest

[Balint Erdi]

Hey,

I've grown extremely enthusiastic about Clojure (and still growing more and 
more :) ) and would like to spread the love around here in Budapest, 
Hungary.

This is to estimate how many people are interested in attending a monthly 
meetup where we'd have presentations, code dojos, etc, so please raise your 
hand if you are interested. Possibly also ask around at your 
workplace/friends so that I can get a fair estimate.

Thank you,
Balint

-- 
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: what is the simplest user auth system possible?

[Balint Erdi]

If you share your pc with your brother then using the classic one 
username/password per site you'd have to log out and back in on each site 
you want to use (or use another browser/incognito window, etc.)

With Persona you only have to do this once.

On Sunday, October 28, 2012 9:05:20 PM UTC+1, Simone Mosciatti wrote:
>
> I never really get Persona (means person in Italian that doesn't really 
> make a lot of sense, but whatever) what if I share my pc with my brother ?
> Maybe i miss something...
>
> If you are using mongodb I am using https://github.com/xavi/noir-auth-app 
> that 
> is using congomongo and since i am using monger i port it in 
> https://github.com/siscia/noir-auth-app ...
>
> It manage maybe too much for your need, email authentication, resend 
> email, change password and other fancy stuff, but the code is really clean 
> and full of comments, really good code imo... 
>
> If you have time you could port it to work with korma... it is not a lot 
> of work at all...
>
> On Sunday, October 28, 2012 8:07:02 PM UTC+1, larry google groups wrote:
>>
>> What happens if the Persona project closes down?
>>
>>
>> On Friday, October 26, 2012 7:06:48 AM UTC-4, Dave Sann wrote:
>>>
>>> For authorisation, I really like mozilla persona (previously browserid) 
>>> which I discovered from refheap. javascript lib plus an http request from 
>>> the server to validate. really simple.
>>>
>>> https://login.persona.org/
>>>
>>> Dave
>>>
>>>
>>>
>>> On Friday, 26 October 2012 01:35:53 UTC+11, Stephen Compall wrote:

 On Oct 25, 2012 9:04 AM, "larry google groups"  
 wrote:
 > For my next step, I need to come up with a user system. My needs are 
 minimal: I only need to know when someone is logged in, and I need to 
 associate them with some user id (the id will simply be the id from a user 
 table kept in MySql). 
 >
 > I am curious what is the absolutely easiest way to do this?

 The easiest auth system to write is the one that's already written.

 https://github.com/cemerick/friend

 --
 Stephen Compall
 If anyone in the MSA is online, you should watch this flythrough. 

>>>

-- 
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: "strange" pattern to implement comp, juxt and partial

[Balint Erdi]

Sorry, I was not precise enough. I meant why is this pattern not used in 
all of *clojure.core*.

Every function that takes a variable number of arguments could use it but I 
only saw it in the mentioned cases.

On Tuesday, October 2, 2012 10:29:15 PM UTC+2, Tamreen Khan (Scriptor) 
wrote:
>
> My guess is that it's useful in the core functions which are more 
> heavily used. Otherwise you're getting into premature optimization if 
> you use it in any of your own functions without profiling it first. 
>
> On Tue, Oct 2, 2012 at 4:18 PM, Balint Erdi > 
> wrote: 
> > Makes sense but why don't we have it in all possible places then? 
> > 
> > Thank you. 
> > 
> > 
> > On Tuesday, October 2, 2012 9:55:42 PM UTC+2, Herwig Hochleitner wrote: 
> >> 
> >> That is because dispatch on argument count is fast, while apply is 
> slow. 
> >> Especially so since it might have to create an intermediate seq. 
> >> It's a performance optimization. 
> >> 
> >> kind regards 
> > 
> > -- 
> > You received this message because you are subscribed to the Google 
> > Groups "Clojure" group. 
> > To post to this group, send email to clo...@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+u...@googlegroups.com  
> > For more options, visit this group at 
> > http://groups.google.com/group/clojure?hl=en 
>

-- 
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: "strange" pattern to implement comp, juxt and partial

[Balint Erdi]

Makes sense but why don't we have it in all possible places then?

Thank you.

On Tuesday, October 2, 2012 9:55:42 PM UTC+2, Herwig Hochleitner wrote:
>
> That is because dispatch on argument count is fast, while apply is slow. 
> Especially so since it might have to create an intermediate seq.
> It's a performance optimization.
>
> kind regards
>

-- 
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

"strange" pattern to implement comp, juxt and partial

[Balint Erdi]

Hey,

When browsing through clojure.core I noticed something peculiar in the 
implementation of comp, juxt and partial.  

All three share the same implementation pattern. They define separate methods 
for the arity of 0,1,2,3 and any.   

For example in juxt:
(defn juxt
   (…)
  ([f g]  
 (fn
   ([] [(f) (g)])
   ([x] [(f x) (g x)])
   ([x y] [(f x y) (g x y)])
   ([x y z] [(f x y z) (g x y z)])
   ([x y z & args] [(apply f x y z args) (apply g x y z args)])))
  ([f g h]  
 (fn
   ([] [(f) (g) (h)])
   ([x] [(f x) (g x) (h x)])
   ([x y] [(f x y) (g x y) (h x y)])
   ([x y z] [(f x y z) (g x y z) (h x y z)])
   ([x y z & args] [(apply f x y z args) (apply g x y z args) (apply h x y 
z args)])))
(…)

I'm sure there is a reason they are implemented like this but my curiosity 
needs to be sated: what is it?

Thank you,
--  
Bálint

-- 
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: The Value of Values

[Balint Erdi]

I'd like to read that thread, can you provide a url?

Thank you,
Balint

On Saturday, August 25, 2012 2:41:40 AM UTC+2, Bost wrote:
>
> See the thread "The Value of Values" started by Conrad Barski 
>

-- 
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: recursion question

[Balint Erdi]

This is the classic Subset sum problem 
(http://en.wikipedia.org/wiki/Subset_sum_problem) and is an NP one.

I've implemented the pseudo-polynomial dynamic programming solution found 
on the above Wikipedia page:
https://gist.github.com/3359504

It returns the indexes of the elements that give the desired sum but it can 
trivially be transformed to whether there is a solution or not.

Balint

On Wednesday, August 15, 2012 1:13:32 AM UTC+2, John Holland wrote:
>
> I've been doing some programming exercises in Clojure, I've run into one I 
> don't know how to approach. If anyone can just give me the strategy to use 
> on this that'd be great. Here is the problem statement:
>
> Given an array of ints, is it possible to choose a group of some of the 
> ints, such that the group sums to the given target? 
>
>
> sample calls would be like:
>
> (groupSum [2, 4, 8] 10) → true
> (groupSum [2, 4, 8] 14) → true
> (groupSum [2, 4, 8]  9) → false
>

-- 
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: ClojureScript instead of CoffeeScript for complete web app development?

[Balint Erdi]

That's right. So the reducers library in ClojureScript will probably also 
use less memory then working with sequential operations but it will not get 
any speed boost since in the Javascript VM it will not run in parallel. Is 
that right?

Balint

On Friday, July 6, 2012 2:31:21 PM UTC+2, Las wrote:
>
> Hi, 
>
> using the reducers library also eliminates the per-step allocation of 
> temporary results when the processing code is composed of multiple 
> functions, AFAIK.
>
> Las
>
> 2012/7/4 Balint Erdi 
>
>> Hey,
>>
>> AFAIK the clojure reducers library gains its performance boost since the 
>> underlying JVM can make use of multiple cores. I wonder how this changes 
>> with Javascript being the platform. Don't JS engines have a single 
>> execution thread?
>>
>> Balint
>>
>>
>> On Thursday, June 28, 2012 11:47:46 PM UTC+2, David Nolen wrote:
>>>
>>> reducers are already available - though further perf work needs to be 
>>> done to really deliver on the performance promises. Even so I wouldn't be 
>>> surprised if they already outperform many chained sequence operations.
>>>
>>> David
>>>
>>> On Thu, Jun 28, 2012 at 5:45 PM, Ben Mabey  wrote:
>>>
>>>> On 6/24/12 10:31 PM, Christian M. wrote:
>>>>
>>>>> I think the only problem (if it is a problem at all), which won't be 
>>>>> solved soon is ClojureScript's performance resulting from creating a lot 
>>>>> of 
>>>>> implicit objects in very high level computations. Something like (filter 
>>>>> (map (reduce ... ... (map ... can't be as fast and as 
>>>>> memory-efficient 
>>>>> for loops and in-place array operations of JS. In theory, the same holds 
>>>>> for Clojure and Java as well, however, in contrast to ClojureScript, I 
>>>>> never faced this problem on JVM yet.
>>>>>
>>>>>  
>>>> Does the new reducers library[1] work in ClojureScript?  One of its 
>>>> advantages is that it avoids the per-step allocation overhead that you are 
>>>> mentioning with the chain of filters/maps/reduce calls.
>>>>
>>>> -Ben
>>>>
>>>>
>>>> 1. http://clojure.com/blog/2012/**0**5/08/reducers-a-library-and-**mo**
>>>> del-for-collection-**processing.**html<http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html>
>>>>
>>>>
>>>> -- 
>>>> 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+unsubscribe@**googlegrou**ps.com
>>>> For more options, visit this group at
>>>> http://groups.google.com/**group**/clojure?hl=en<http://groups.google.com/group/clojure?hl=en>
>>>>
>>>
>>>  -- 
>> 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
>>
>
>
>
> -- 
> László Török
>
> 

-- 
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: ClojureScript instead of CoffeeScript for complete web app development?

[Balint Erdi]

Hey,

AFAIK the clojure reducers library gains its performance boost since the 
underlying JVM can make use of multiple cores. I wonder how this changes 
with Javascript being the platform. Don't JS engines have a single 
execution thread?

Balint

On Thursday, June 28, 2012 11:47:46 PM UTC+2, David Nolen wrote:
>
> reducers are already available - though further perf work needs to be done 
> to really deliver on the performance promises. Even so I wouldn't be 
> surprised if they already outperform many chained sequence operations.
>
> David
>
> On Thu, Jun 28, 2012 at 5:45 PM, Ben Mabey  wrote:
>
>> On 6/24/12 10:31 PM, Christian M. wrote:
>>
>>> I think the only problem (if it is a problem at all), which won't be 
>>> solved soon is ClojureScript's performance resulting from creating a lot of 
>>> implicit objects in very high level computations. Something like (filter 
>>> (map (reduce ... ... (map ... can't be as fast and as memory-efficient 
>>> for loops and in-place array operations of JS. In theory, the same holds 
>>> for Clojure and Java as well, however, in contrast to ClojureScript, I 
>>> never faced this problem on JVM yet.
>>>
>>>  
>> Does the new reducers library[1] work in ClojureScript?  One of its 
>> advantages is that it avoids the per-step allocation overhead that you are 
>> mentioning with the chain of filters/maps/reduce calls.
>>
>> -Ben
>>
>>
>> 1. http://clojure.com/blog/2012/**05/08/reducers-a-library-and-**
>> model-for-collection-**processing.html
>>
>>
>> -- 
>> 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+unsubscribe@**googlegroups.com
>> For more options, visit this group at
>> http://groups.google.com/**group/clojure?hl=en
>>
>
>

-- 
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