Hello Daniel,
Regarding your solution, can I apply {-# SPECIALISE ... #-} statements to
datatypes I define?
And if so, I am not able to import the datatypes to the module where
binarySearch is.
The problem is that if I import them a circular dependency is detected and
the compiler gives an error.
Is there a way of importing a datatype from another module do avoid this
circular dependency?
Thank you,
Arnoldo
On Thu, Mar 18, 2010 at 10:48 PM, Daniel Fischer
Am Donnerstag 18 März 2010 21:57:34 schrieb Daniel Fischer:
Contrary to my expectations, however, using unboxed arrays is slower than straight arrays (in my tests).
However, a few {-# SPECIALISE #-} pragmas set the record straight. Specialising speeds up both, boxed and unboxed arrays, significantly, but now, for the specialised types, unboxed arrays are faster (note, however, that when the code for the binary search is in the same module as it is used, with optimisations, GHC will probably specialise it itself. If binarySearch is not exported, AFAIK, you can delete "probably".).
{-# LANGUAGE BangPatterns #-} module SATBinSearch (binarySearch) where
import Data.Array.IArray import Data.Array.Base (unsafeAt) import Data.Bits
{-# SPECIALISE binarySearch :: Double -> Array Int Double -> Int #-} {-# SPECIALISE binarySearch :: Int -> Array Int Int -> Int #-} {-# SPECIALISE binarySearch :: Bool -> Array Int Bool -> Int #-} {-# SPECIALISE binarySearch :: Char -> Array Int Char -> Int #-} {-# SPECIALISE binarySearch :: Float -> Array Int Float -> Int #-} binarySearch :: Ord a => a -> Array Int a -> Int binarySearch q a = go l h where (l,h) = bounds a go !lo !hi | hi < lo = -(lo+1) | otherwise = case compare mv q of LT -> go (m+1) hi EQ -> m GT -> go lo (m-1) where -- m = lo + (hi-lo) `quot` 2 m = (lo .&. hi) + (lo `xor` hi) `shiftR` 1 mv = a `unsafeAt` m
Use Data.Array.Unboxed and UArray if possible. Now the bit-fiddling instead of arithmetics makes a serious difference, about 20% for unboxed arrays, 17% for boxed arrays (Double), so I'd recommend that.