On Thursday, 16 August 2012 at 23:13:56 UTC, maarten van damme
wrote:
great, going to play around with it tomorrow.
Caching the possibilities is going to look really ugly but
you're
right, it's going to give quiet a boost in performance.
I'm also going to format your source code a bit more and see if
I can
follow it's logic as it seems to be way more efficient.
(although
compilation is failing here, I'm running dmd 2.059 and it gives
"can't
stride on chunks!(short))
would using short or bytes increase performance compared to
integers?
if so, why did you use shorts instead of bytes?
Gonna chime in a bit here:
There's a lot of factors at play when deciding to use shorts vs
bytes vs native-sized ints. The best way to decide is to time all
of them and see which works best overall.
With caching on a larger problem, I'd guess that the smaller you
go, the better. The reason is that you run the risk of your data
getting large enough that it can't all fit in the L2 cache and
waiting for information to come from memory takes forever
(comparatively speaking).
Also, I just looked at your solution (not Mr. Gehr's solution),
but it looks like you could approach this much more efficiently.
It seems like you're storing a lot of information in arrays of
ints. At least some of that could be stored in a bitmap/bitset
(http://en.wikipedia.org/wiki/Bit_array) and give you
significantly better memory efficiency. Array!bool in
std.container will actually do the correct thing and store things
like a bitset, so you don't necessarily have to implement your
own (however, I think that it stores it in an int when you could
use a short to hold 1-9 ... but it's not enough to really worry
about).
