Excellent. I will – with attribution, of course! On Wed, Oct 21, 2015 at 7:26 PM, Jason Merrill <[email protected]> wrote:
> 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 >>>> >>> >>
