Optimization Problem
I am trying to make an algorithm which solves Smallest circle problem(http://en.wikipedia.org/wiki/Smallest_circle_problem).
My code takes ~3.2 sec to solve ~500 data sets of 2000 points apiece. I need it to be done in less than 1 sec.
After profiling it seems that ~1.76 (55%) sec goes to the inDisc function and ~1 (32%) sec goes into gcnts. So I am trying
to optimize these parts of the code.
-- is the point p2 is inside disc?
inDisc :: Disc -> Point -> Bool
inDisc (Disc r p1 _) p2 = (distance p1 p2) <= r
-- gives the double values in one line
gcnts :: IO [Double]
gcnts = do
line <- getLine
return (map read (words line))
And data and point are
-- (x, y)
type Point = (Double, Double)
- radius, center, know points in the disc
data Disc = Disc Double Point [Point]
deriving (Show)
The relevant profiler part:
COST CENTRE MODULE %time %alloc
inDisc Main 55.0 0.0
gcnts Main 32.5 58.1
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
inDisc Main 247 1237577 35.6 0.0 35.6 0.0
inDisc Main 244 527216 11.9 0.0 11.9 0.0
inDisc Main 241 214076 7.5 0.0 7.5 0.0
gcnts Main 235 8043 31.3 58.1 31.3 58.1
gcnts Main 233 10 1.3 0.0 1.3 0.0
gcnts Main 231 1 0.0 0.0 0.0 0.0
I have attached my code and profiler output.
BSRK Aditya.