Odd Performance
Garner, Robin
Robin.Garner@crsrehab.gov.au
Wed, 30 Oct 2002 11:55:51 +1100
This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.
------_=_NextPart_001_01C27FAF.17946240
Content-Type: text/plain;
charset="iso-8859-1"
You may also like to compare this definition.
> import List
>
> primes = unfoldr sieve [2..]
> sieve (x:xs) = Just (x,filter (x `notDivisor`) xs)
> x `notDivisor` y = y `mod` x /= 0
Slower, but (IMO) cuter.
Cheers,
-----Original Message-----
From: Tim Otten [mailto:tim@cap.american.edu]
Sent: Wednesday, 23 October 2002 15:10
To: haskell-cafe@haskell.org
Cc: scasey@cap.american.edu
Subject: Re: Odd Performance
Tom Pledger writes:
> Probably. Try replacing this
> (\z -> z <= (intsqrt x))
> with this
> (\z -> z^2 <= x)
Yes! This is significantly nicer. Taking 4000 primes, this is about twice
as fast as the original (loose) algorithm, and it appears that it gets
better as n grows. (Call this version #3).
> or moving the O(sqrt(n)) step[1] into a let expression
This does help -- the implementation with this adjustment seems to hover
around 1.1 times the speed of the loose algorithm. (Call this version #4)
> Only if the predicate function (the p in takeWhile p xs) is
> significantly more expensive than a constant-cost piece of arithmetic
> and pattern-matching.
This makes sense and explains the results above: squaring z is easier than
square-rooting x. In fact, the way intsqrt is written, #4's takeWhile
indirectly tests (z*z > x) once for each [z | 1<=z<=sqrt(x)]. #3's
takeWhile expression will only evaluate (z^2 < x) once for each [ z | z <-
primes, z<=sqrt(x) ]. Moreover, #4's takeWhile will do additional tests (z
<= sqrt) for each [z | z <- primes, z <= sqrt(x)]. In retrospect, the
intsqrt-approach seems rather silly. :)
Thank you,
Tim
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
------_=_NextPart_001_01C27FAF.17946240
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
5.5.2653.12">
<TITLE>RE: Odd Performance</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=3D2>You may also like to compare this definition.</FONT>
</P>
<P><FONT SIZE=3D2>> import List</FONT>
<BR><FONT SIZE=3D2>> </FONT>
<BR><FONT SIZE=3D2>> primes =3D unfoldr sieve [2..]</FONT>
<BR><FONT SIZE=3D2>> sieve (x:xs) =3D Just (x,filter (x =
`notDivisor`) xs)</FONT>
<BR><FONT SIZE=3D2>> x `notDivisor` y =3D y `mod` x /=3D 0</FONT>
</P>
<P><FONT SIZE=3D2>Slower, but (IMO) cuter.</FONT>
</P>
<P><FONT SIZE=3D2>Cheers,</FONT>
</P>
<P><FONT SIZE=3D2>-----Original Message-----</FONT>
<BR><FONT SIZE=3D2>From: Tim Otten [<A =
HREF=3D"mailto:tim@cap.american.edu">mailto:tim@cap.american.edu</A>]</F=
ONT>
<BR><FONT SIZE=3D2>Sent: Wednesday, 23 October 2002 15:10</FONT>
<BR><FONT SIZE=3D2>To: haskell-cafe@haskell.org</FONT>
<BR><FONT SIZE=3D2>Cc: scasey@cap.american.edu</FONT>
<BR><FONT SIZE=3D2>Subject: Re: Odd Performance</FONT>
</P>
<BR>
<P><FONT SIZE=3D2>Tom Pledger writes:</FONT>
</P>
<P><FONT SIZE=3D2>> Probably. Try replacing this</FONT>
<BR><FONT SIZE=3D2>> (\z -> z <=3D (intsqrt =
x))</FONT>
<BR><FONT SIZE=3D2>> with this</FONT>
<BR><FONT SIZE=3D2>> (\z -> z^2 <=3D =
x)</FONT>
</P>
<P><FONT SIZE=3D2>Yes! This is significantly nicer. Taking 4000 primes, =
this is about twice</FONT>
<BR><FONT SIZE=3D2>as fast as the original (loose) algorithm, and it =
appears that it gets</FONT>
<BR><FONT SIZE=3D2>better as n grows. (Call this version #3).</FONT>
</P>
<P><FONT SIZE=3D2>> or moving the O(sqrt(n)) step[1] into a let =
expression</FONT>
</P>
<P><FONT SIZE=3D2>This does help -- the implementation with this =
adjustment seems to hover</FONT>
<BR><FONT SIZE=3D2>around 1.1 times the speed of the loose algorithm. =
(Call this version #4)</FONT>
</P>
<P><FONT SIZE=3D2>> Only if the predicate function (the p in =
takeWhile p xs) is</FONT>
<BR><FONT SIZE=3D2>> significantly more expensive than a =
constant-cost piece of arithmetic</FONT>
<BR><FONT SIZE=3D2>> and pattern-matching.</FONT>
</P>
<P><FONT SIZE=3D2>This makes sense and explains the results above: =
squaring z is easier than</FONT>
<BR><FONT SIZE=3D2>square-rooting x. In fact, the way intsqrt is =
written, #4's takeWhile</FONT>
<BR><FONT SIZE=3D2>indirectly tests (z*z > x) once for each [z | =
1<=3Dz<=3Dsqrt(x)]. #3's</FONT>
<BR><FONT SIZE=3D2>takeWhile expression will only evaluate (z^2 < x) =
once for each [ z | z <-</FONT>
<BR><FONT SIZE=3D2>primes, z<=3Dsqrt(x) ]. Moreover, #4's takeWhile =
will do additional tests (z</FONT>
<BR><FONT SIZE=3D2><=3D sqrt) for each [z | z <- primes, z =
<=3D sqrt(x)]. In retrospect, the</FONT>
<BR><FONT SIZE=3D2>intsqrt-approach seems rather silly. :)</FONT>
</P>
<P><FONT SIZE=3D2>Thank you,</FONT>
<BR><FONT SIZE=3D2>Tim</FONT>
</P>
<BR>
<BR>
<P><FONT =
SIZE=3D2>_______________________________________________</FONT>
<BR><FONT SIZE=3D2>Haskell-Cafe mailing list</FONT>
<BR><FONT SIZE=3D2>Haskell-Cafe@haskell.org</FONT>
<BR><FONT SIZE=3D2><A =
HREF=3D"http://www.haskell.org/mailman/listinfo/haskell-cafe" =
TARGET=3D"_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</=
A></FONT>
</P>
</BODY>
</HTML>
------_=_NextPart_001_01C27FAF.17946240--