That's a very nice implementation. Great example of how making custom types can give you a really lovely combination of usability and performance. I may use this in some talks if you don't mind!
On Wed, Oct 21, 2015 at 7:08 PM, Jason Merrill <[email protected]> wrote: > I got interested in trying to optimize this problem even further. Here are > the results: > > https://gist.github.com/jwmerrill/5b364d1887f40f889142 > > I was able to get the benchmark down to a few microseconds (or ~100 > microseconds if you count the time to build a look up table). Either way, > it's a pretty good improvement over 1+ seconds :-) > > The main trick is to represent a set of digits 1-9 as a binary integer. > There are only 2^9=512 such sets, so you can pack any of them into an > Int16. Then you can precompute the sum of each set and store those in a > look up table, so that finding the ways to decompose a given number is just > a table lookup. > > I think this is a pretty nice example of how Julia's dispatch system let > you have complex views and operations over a very simple data structure (in > this case, a single integer), with essentially 0 overhead. > > On Monday, October 19, 2015 at 7:39:03 AM UTC-4, Patrick Useldinger wrote: >> >> Hello >> true but no summand may appear twice, and only numbers 1 to 9 may be >> used. For example, (10, 3) yields >> >> Array[Int16[2,3,5],Int16[1,4,5],Int16[1,3,6],Int16[1,2,7]] >> >> Regards, >> -Patrick >> >
