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. On Thursday, May 14, 2015 at 4:02:42 AM UTC-4, Amith George wrote: > > I wrote the following code to solve this challenge - > https://www.reddit.com/r/dailyprogrammer/comments/35s2ds/20150513_challenge_214_intermediate_pile_of_paper/ > . > > Code - > https://github.com/amithgeorge/reddit-dailyprogrammer-clojure/blob/56ce1dbb6a08e96150dc85934caecfeb68108a53/src/rdp/214_intermediate.clj > > I executed the -main function using `lein run 1`. > > Output > > ;; lein run 1 > > 0 12605919 > 1 3578145 > 2 15356894 > 3 19134293 > 4 2394558 > 5 15030409 > 6 6424953 > 7 14893444 > 8 1592254 > 9 1914025 > 10 7075106 > "Elapsed time: 501168.972435 msecs" > > The code originally used an immutable hashmap, but I lost patience waiting > for the computation to end. With mutable hashmap, it still takes around 8 > mins. > > I wrote a C# version of the above code - > https://gist.github.com/amithgeorge/766b8220f39d48221e58. It finishes > under 40secs. The C# exe was built under Release mode and executed directly > from the commandline. I expected the Clojure version to perform similarly. > > Any tips on what I am doing wrong? > > ----- > Explanation of the code - Create a vector of all paper sheets, such that > the sheet placed last is the first element of the vector and the last > element is the canvas. To compute the frequency of each visible color - for > each point in the canvas find the first sheet in the vector that covers the > point. Store/increment its count in the hashmap. I understand there might > be better more efficient ways to solve this, but currently I am interested > in why the Clojure versions is so slow vis-a-vis the C# version. > > -- 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.
