[Haskell-beginners] Improving Performance
Robert Heumüller
mailing at heum.de
Sun Jul 1 12:38:14 CEST 2012
Hi again,
hoping to further increase performance i've decided to calculate
the distances between all points ahead of time and store the distance
values in a map of maps. Because of the symmetry of the matrix this
should work in O(0.5*n^2). Could you please take a look at the code and
tell me if this would be the way to go? I fear that i might actually
loose performance due to the lookuptime of the treemap compared to
recalculating the distance between two points?
Thank you very much :)
import qualified Data.Map as Map
data Point a = Pt a a deriving (Show, Eq, Ord)
manhattan (Pt x y) (Pt x' y') = abs (x' - x) + abs (y' - y)
dist' :: Num a => Point a -> [Point a] -> [(Point a, a)]
dist' p [] = []
dist' p l = zip l (map (manhattan p) l)
dist :: (Num a, Ord a) => Point a -> [Point a] -> Map.Map (Point a) a
dist p l = Map.fromList (dist' p l)
distmatrix :: (Num a, Ord a) =>
[Point a] -> Map.Map (Point a) (Map.Map (Point a) a)
distmatrix (p:[]) = Map.empty
distmatrix (p:ps) = Map.insert p (dist p ps) (distmatrix ps)
getdist' ::
(Num a, Ord a) =>
Point a -> Point a -> Map.Map (Point a) (Map.Map (Point a) a)
-> a getdist' p1 p2 dm = (dm Map.! p1) Map.! p2
getdist ::
(Num a, Ord a) =>
Point a -> Point a -> Map.Map (Point a) (Map.Map (Point a) a)
-> a getdist p1 p2 dm
| Map.member p1 dm = getdist p1 p2 dm
| otherwise = getdist' p2 p1 dm
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120701/43715685/attachment.pgp>
More information about the Beginners
mailing list