Hi, Thank you for taking the time. That is a rather smart algo. The code and the changes were easy to understand.
I didn't implement the parallelized version as my aim was to understand why the clojure version was so slow compared to the equivalent C# version. (Btw, you have access to a 12 core machine! :O) Ok. Two versions of the code - https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/2655a83f7fcf51e4fedae164d7d17386a0c8854f/src/rdp/214_intermediate_leifp.clj lein run -m rdp.214-intermediate-leifp 1 ;; took around 100s https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/2655a83f7fcf51e4fedae164d7d17386a0c8854f/src/rdp/214_intermediate_arr_leifp.clj lein run -m rdp.214-intermediate-arr-leifp 1 true ;; took around 70s The first file (214_intermediate_leifp.clj) is similar to what you had after point 1. The second file (214_intermediate_arr_leifp.clj) is your algo combined with the tips provided in the posts above - mainly - using type hints; native arrays, two argument arity of `<=` etc. It also uses a record `Paper` instead of a map. However the record values are accessed by the keyword instead of direct field access. Applying those tips to my algo, reduced the time taken from 500s to 250s. For your algo, those tips only reduced the time taken by 1/4th. Which makes sense as your algo performs far less operations, so there are lesser number of operations that can get a speed bump... That said, I am none the wiser on how to write to fast single threaded clojure :( On Tuesday, 19 May 2015 05:34:21 UTC+5:30, Leif wrote: > > Summary: With a new algorithm + parallelism, I reduced it from 528s to > 11s. > > This sounded fun, so I took a crack at it, starting with your solution. > Description and patch files here: > https://gist.github.com/leifp/a864bca941ecdacb5840 > > Starting with your solution, I: > > 1. Divided the canvas into 100 blocks, created an index of {blockindex > -> papers that intersect that block}. The reasoning is that if we > calculate > which block a pixel is in, we only need to check the papers that intersect > that block. In the extreme case, certain blocks only intersected one > paper > (the background). In the original code we would have had to check all 100 > papers for each pixel in that block; now we just check one. (5x average > speedup) > 2. Changed the code to calculate color areas for a block at a time; > after that, it was a simple 2-line change to parallelize the work using > pmap. > (8x speedup on 12-core machine) > 3. Make paper a record; use direct field access (this resulted in a > modest ~10% improvement, but maybe not worth it). > > So clojure was helpful in trying out algorithm ideas and parallelizing the > code. The final program would no doubt also be faster in C#, but my goal > is "fast enough." > > Further idea (which I don't think I'll implement): Index the papers using > an data structure built for geometrical indexing, like an R-tree or > variation, to get a near-optimal index without tuning. > > I hope my solution is interesting to you. Questions / comments welcome. > Leif > > P.S. I apologize for the messy, repetitive, stream-of-consciousness 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 --- 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/d/optout.
