"Elapsed time: 1155.723592 msecs" I implemented the changes Amith and Steven suggested on my multithreaded version. I think we can safely say that, with a modest effort, Clojure can compare favorably to C#. :)
https://gist.github.com/leifp/a864bca941ecdacb5840 Cheers, Leif On Tuesday, May 19, 2015 at 5:18:24 AM UTC-4, Amith George wrote: > > 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.
