Am Freitag, 7. April 2006 22:57 schrieb David F. Place:
After reading Daniel Fischer's message about trying to use EnumSet in his Sudoku.hs and finding that it was slower when processing a large data set, I decided to do some profiling. I rewrote his solver to use EnumSets and profiled it. The culprit turns out to be the
The main & evil culprit, methinks now, was DiffArray and the small allocation area. Care to re-profile with my SudokuSet.hs ? Unless I overlooked something, I use foldBits only via size (though that's used a lot).
following function which is responsible for 22% of the allocating in the run. Is there a more efficient way to write this function?
foldBits :: Bits c => (a -> Int -> a) -> a -> c -> a foldbits _ z 0 = z foldBits f z bs = foldBits' f 0 bs z
foldBits' :: Bits c => (a -> Int -> a) -> Int -> c -> a -> a foldBits' f i bs z
| bs == 0 = z | otherwise = z' `seq` foldBits' f i' bs' z'
where z' | 1 == bs .&. 1 = f z i ^^^^^^^^^^^^^^^^^ testbit bs 0 ? and foldbits(') is only used for c = Word, so why the polymorphism?
| otherwise = z
i' = i + 1 bs' = bs `shiftR` 1
ps. I was impressed with how hairy DF's algorithm is and I am not
Now there are comments, I hope they explain what I do.
really enough interested in Sudoku to spend the time needed to grok it. So, I decided to try an experiment to see if I could restructure it without understanding it very deeply.
Step 1. comment out all the type signatures. Step 2. find the main place that I wanted to change from [Int] to (Set Int) Step 3. compile; make obvious edits; repeat until 0 errors
I had it running in a few minutes. I can't imagine doing that in any other programming environment!
Great! Triple Cheer for Haskell!!! I wonder how different your translation is to mine (I've no experience with bit-twiddling, but I tried to be as cheap as possible)
Cheers, David
Cheers, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton