2012/8/17, Chris Cain <clc...@uncg.edu>: > > 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). >
I've been using my phone the last few days to check my emails and overlooked this message. I've never heard about std.container but this could indeed be a more efficient solution. I'm now storing a lot in bytes but that's still 8 times too much :) > Try this: > http://dpaste.dzfl.pl/23b1b6e2 Thank you very much, this makes everything more clearer. I'm not very familiar with binary operators so the comments help out a lot. Would you mind it if I shamelessly copy your solution of using shorts to store possibilities in? I'm also a bit confused. How come the int's you change from a square passed from squ are stilled referenced to the original array? I thought it lost that reference as soon as you did any operations (like concenating) on it? > Was that sarcasm? My own code only uses copying when it's working in the next > section of brute force, otherwise it's all referenced. No, that wasn't sarastic. If you look at my last code you see that I "compose" the squares using something like [....] ~ [.....] ~ [.....] Using a foreach loop and copying the values was 10 times faster... > I only use exceptions twice and both when it would be unable to find a > solution; I suppose I can try putting nothrow on everything and return a bool > if it had an error for solving, or when it had to, inside a structure. > Mmmm... I'll give it a try. Yes but when your solver reaches a solution that is wrong, you get a whole "branch" of numbers falling of, all throwing a "broken sudoku" exception. It will rarely be called once. > Not normal but it can be arranged. :p But I used it in my getRegion code where I do simple calculations on the contents of that array. It is slower there...
