-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Dec 19, 2008, at 7:40 AM, Daniel Kraft wrote:
data Fraction = Fraction Int Int
to hold rational numbers (maybe there's already some built-in type
for this in Haskell, much like for instance Scheme has a rational
type?),
There is one. It is called Rational. :)
and then I compute a list of pairs of those numbers, that is
[(Fraction, Fraction)]. Fraction is declared an instance of Ord.
This list has up to 3 million elements. If I do
main = print $ length $ points
then the program prints out the length fine and takes around 6s to
finish (compiled with GHC -O3). Ok, but I acknowledge that length
isn't quite an expensive function, as I can imagine that Haskell
does not compute and hold the entire list for this but instead each
element at once and discards it afterwards.
Unless something has changed since I last checked, there is little
difference between ghc -O2 and ghc -O3, and the latter can even be
slower much of the time. It may depend on the situation, but I'm just
letting you know.
In this case, the runtime should not actually be computing _any_ of
the elements of the list since it doesn't care what their values are.
You are only counting them, not using them, so it really only computes
the spine of the list.
Doing
main = print $ length $ map (\(x, _) -> x == Fraction 1 2) points
instead, gives a slightly longer runtime (6.6s), but in this case
I'm sure that at least each element is computed; right?
No. The elements' values are still not actually used, so you are still
only evaluating the spine of the list.
main = print $ length $ reverse points
gives 11.9s, and here I guess (?) that for this to work, the entire
list is computed and hold in memory.
This is beginning to sound like you think Haskell lists are arrays.
They aren't. They are actually linked lists. In order to reverse a
linked list, you have to travel all the way to the end and then
reconstruct it from there. This explains the time increase. It doesn't
really have anything to do with computing the elements or holding
anything in memory.
However, trying to do
import List
main = print $ length $ sort points
makes memory usage go up and the program does not finish in 15m,
also spending most time waiting for swapped out memory. What am I
doing wrong, why is sort this expensive in this case? I would
assume that computing and holding the whole list does not take too
much memory, given its size and data type; doing the very same
calculation in C should be straight forward. And sort should be O(n
* log n) for time and also not much more expensive in memory, right?
This is actually the first time you really evaluated any of the
elements of the list, hence a massive increase in memory use.
- - Jake
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (Darwin)
iEYEARECAAYFAklLsaoACgkQye5hVyvIUKlJYgCfYtwPv/neOnl3+wIu8VhIqfoA
lXMAn3EmANZbSRyYeOiXtOdGl7hxCj34
=NJwT
-----END PGP SIGNATURE-----
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
