[Haskell-cafe] Efficiency Question
daniel.is.fischer at web.de
Fri Jan 14 15:57:25 EST 2005
toying a bit with splitAt and take, I have met yet another thing, I don't
In the Hugs Prelude, splitAt is defined
splitAt n xs | n <= 0 = ( ,xs)
splitAt _  = (,)
splitAt n (x:xs) = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs
whereas in the report it is described as (take n xs,drop n xs) -- I have no
problem with that, since the report explicitely states that the functions
need not be implemented as given there --, let's call that function bSplit (b
was chosen for 'bad').
Now, as expected, splitAt takes fewer reductions than bSplit, splitAt (n+1)
takes 18 reductions more than splitAt n, bSplit (n+1) takes 32 more than
bSplit n (24 for take, 8 for drop).
So far so good, now changing to ghci and testing that on a long list
([1 .. 1000000], [1 .. 500000]), splitting at half, then printing the two
middle numbers. The first surprise was that there bSplit was faster than
splitAt (roughly twice as fast).
Does anybody know how that can be??
The second surprise was the variation of time needed.
For the longer list, splitAt usually took 0.45 - 0.48 secs, occasionally about
0.9 secs (I think that will be due to gc),
bSplit usually took 0.22 - 0.25 secs, occasionally about 0.7 secs (gc,
For the shorter list, splitAt took 0.22 - 0.28 secs (0.7 with gc), bSplit took
0.10 - 0.20 secs (0.6 with gc).
Now, what's the explanation for that?
Differences of, say, 0.03 secs or so I happily attribute to an occasional
interrupt or something, but the difference between 0.10 and 0.20 I would like
an explanation for.
Another thing, while toying, I found out that a comparison (n <= 0) takes
three reductions more than (n < 1) according to my hugs, so changing the
definition of splitAt thus, we require (3*n) reductions less. But the number
of reductions and speed are different things, as witnessed by the above, so
would it be an improvement to replace "n <= Integerliteral"-queries by
"n < Integerliteral"-queries or doesn't that make any difference at all in
Finally, in several contexts I needed to cons an element to one of a pair of
lists, so I defined
infixr 5 &,§
(&) :: a -> ([a],[b]) -> ([a],[b])
x & (xs,ys) = (x:xs,ys)
(§) :: b -> ([a],[b]) -> ([a],[b])
y § (xs,ys) = (xs,y:ys).
I find them useful (though I don't like the symbols, if you have any better
ideas, thx) and for splitAt, (&) saves another reduction per step.
Now, I would like to have such operators supplied by the language, so is there
space for them in the Prelude or in List, or does hardly anyone besides me
ever need them?
Have a wonderful weekend ye all,
More information about the Haskell-Cafe