Am Donnerstag 18 März 2010 19:59:33 schrieb Arnoldo Muller:
Hello!
I am trying to implement a binary search function that returns the index of an exact or the (index + 1) where the item should be inserted in an array if the item to be searched is not found (I am not trying to insert data in the array) .
Right now, the bottleneck of my program is in binarySearch', the function must be called a few billion times.
If it's called often, and the arrays are 0-based and Int-indexed, import Data.Array.Base (unsafeAt) and replacing ! with `unsafeAt` should give a speed-up, though probably not terribly much. If you don't need the polymorphism and your array elements are unboxable, using UArray from Data.Array.Unboxed should be significantly faster.
Do you have any ideas on how to improve the performance of this function?
import Data.Array.IArray
type IntArray a = Array Int a
-- The array must be 0 indexed. binarySearch :: Ord a => a -> IntArray a -> Int binarySearch query array = let (low, high) = bounds array in binarySearch' query array low high
binarySearch' :: Ord a => a -> IntArray a -> Int -> Int -> Int binarySearch' query array !low !high
| low <= high = let ! mid = low + ((high - low) `div` 2)
! midVal = array ! mid in next mid midVal
| otherwise = -(low + 1)
where next mid midVal
| midVal < query = binarySearch' query array (mid + 1) | high midVal > query = binarySearch' query array low | (mid - 1) otherwise = mid
No obvious performance killers, maybe the 'next' function costs a little and let ... in case compare midVal query of LT -> binarySearch' query array (mid+1) high EQ -> mid GT -> binarySearch' query array low (mid-1) would be faster. Or moving binarySearch' from the top-level into binarySearch and eliminating the two static arguments may improve performance (I seem to remember that a static argument-transform for less than three or four non-function arguments can speed the code up or slow it down, so you'd have to test; for many arguments or function arguments it's pretty certain to give a speed-up, IIRC). binarySearch query array = go low high where (low,high) = bounds array go !l !h | h < l = -(l+1) | mv < query = go l (m-1) | mv == query = m | otherwise = go (m+1) h where m = l + (h-l) `quot` 2 mv = array `unsafeAt` m
Thank you!
Arnoldo Muller