Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Improving Performance (Robert Heum?ller)
2. Re: Improving Performance (Brent Yorgey)
3. Re: FRP and a set of pairwise interacting (colliding)
objects (Ertugrul S?ylemez)
----------------------------------------------------------------------
Message: 1
Date: Sun, 1 Jul 2012 12:38:14 +0200
From: Robert Heum?ller <[email protected]>
Subject: Re: [Haskell-beginners] Improving Performance
To: [email protected]
Message-ID: <20120701123814.52a32e99@thor>
Content-Type: text/plain; charset="us-ascii"
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-0001.pgp>
------------------------------
Message: 2
Date: Sun, 1 Jul 2012 12:09:38 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Improving Performance
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
On Sun, Jul 01, 2012 at 12:38:14PM +0200, Robert Heum?ller wrote:
> 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?
Indeed, since calculating the distance between two points is so simple
(just a few arithmetic operations) I really doubt you will get much
speedup by caching the distances, especially if you have a lot of
points. But, as always, it's really impossible to predict for
sure---you'll have to do some profiling.
-Brent
------------------------------
Message: 3
Date: Mon, 2 Jul 2012 10:51:00 +0200
From: Ertugrul S?ylemez <[email protected]>
Subject: Re: [Haskell-beginners] FRP and a set of pairwise interacting
(colliding) objects
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Nathan H?sken <[email protected]> wrote:
> So I would have a main arrow like this (leaving out the Map for which
> I have to lookup the syntax):
>
> main = proc in -> do
> planet1 <- planets initPlanet1 -< allPlanets
> planet2 <- ...
> ...
> allPlanets <- delay [] -< [planet1,planet2 ...]
>
> (I would probably have some arrow managing all planets instead of
> listing them separately)
> Correct?
Yes, that's the basic idea. Just drop in a 'rec' somewhere for the
feedback to work.
> Yes, that makes sense. There is still a little overhead. Assuming
> collisions are symmetric, the OOP approach would only test every pair
> of planets once ... not in the way I wrote it down, but it could
> easily be changed so that it does.
> But here they have to tested twice.
> Thats only factor 2 and probably acceptable. Still, is it avoidable?
Yes, it is. You can write a managing wire transformer (along the lines
of the ones from Control.Wire.Trans.Combine) specifically for colliding
objects. It's really much easier than it sounds. Just have a look into
the source code of that module.
Greets,
Ertugrul
--
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120702/eae5ad16/attachment-0001.pgp>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 49, Issue 2
****************************************
