Hum, oddly, these actually slow things down. While the new size brought the sudoku17 time from ~570s down to ~490s, the new findMinIndex/findMaxIndex increased the time to ~515s, although hardly used. Why?
Cheers, Daniel Am Sonntag, 9. April 2006 00:54 schrieb Robert Dockins: > On Apr 8, 2006, at 1:58 PM, David F. Place wrote: > > Thanks Bulat and Robert. I implemented Bulat's idea as the > > following. It tests faster than Roberts. I use Robert's to > > compute the table. The performance seems satisfactory now. > > > > size :: Set a -> Int > > size (Set w) = countBits w > > where > > countBits w > > > > | w == 0 = 0 > > | otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&. 0xFF) > > > > bitsTable :: Array Word Int > > bitsTable = array (0,255) $ [(i,bitcount i) | i <- [0..255]] > > > > bitcount :: Word -> Int > > bitcount 0 = 0 > > bitcount x = 1 + bitcount (x .&. (x-1)) > > There's a couple of other nice bit-twiddily things you can do: > > countBits :: Word -> Int > countBits w > > | w == 0 = 0 > | otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&. 0xFF) > > bitsTable :: Array Word Int > bitsTable = array (0,255) $ [(i,bitcount i) | i <- [0..255]] > > bitcount :: Word -> Int > bitcount 0 = 0 > bitcount x = 1 + bitcount (x .&. (x-1)) > > lsb :: Word -> Int > lsb x = countBits ((x-1) .&. (complement x)) > > -- stolen from http://aggregate.org/MAGIC/ > msb :: Word -> Int > msb x0 = let > x1 = x0 .|. (x0 `shiftR` 1) > x2 = x1 .|. (x1 `shiftR` 2) > x3 = x2 .|. (x2 `shiftR` 4) > x4 = x3 .|. (x3 `shiftR` 8) > x5 = x4 .|. (x4 `shiftR` 16) > in countBits x5 - 1 > > > findMinIndex :: Word -> Int > findMinIndex 0 = > error "EnumSet.findMin: empty set has no minimal element" > findMinIndex w = lsb w > > findMaxIndex :: Word -> Int > findMaxIndex 0 = > error "EnumSet.findMax: empty set has no maximal element" > findMaxIndex w = msb w > > > > Which should make all access to the greatest or least element O(1). > I guess, come to think of it, all operations on EnumSet are O(1) by > virtue of the set size being upper-bounded. At any rate this turns > recursion into unboxable straight-line code and I think it does less > allocations. > > > > Rob Dockins > > Speak softly and drive a Sherman tank. > Laugh hard; it's a long way to the bank. > -- TMBG > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
