Thanks! Definitely feel free to use this wherever you like. On Wed, Oct 21, 2015 at 7:13 PM Stefan Karpinski <[email protected]> wrote:
> 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 >>> >> >
