[Haskell-cafe] Hugs - evaluation statistics
Dusan Kolar
kolar at fit.vutbr.cz
Mon Aug 29 10:04:58 EDT 2005
Well, I know I cannot calculate exact time statistics, but I cen get
information about the aproximate behavior - like the algorithm
is Theta(n), Theta(n*log(n)), etc. It's quite sufficient, I think.
According to your example - I don' know what you want to show,
both algorithms are linear in time consumption:
[reductions]
length length2
l(10) 91 28
l(100) 721 73
l(1000) 7021 523
l(5000) 35021 2523
For length we get: 7*n+21
For length2 we get: 1/2*n+23
Thus, for both length and length' we get: Theta(n)
And in my first e-mail, I wrote I knew it's not exact. But, if I expect
behavior like Theta(n^2) and I can't fit it then I'm asking
why - now I know answer even for that question (in my case) -
I can provide only too small input to test (otherwise out of memory)
and thus the curve is not "curve-enough" and is much closer to
line. But new settings for hugs compilation should allowed much
higher memory usage and I should get to more usable numbers. :-)
Dusan
Bulat Ziganshin wrote:
>Hello Dusan,
>
>Monday, August 29, 2005, 9:55:56 AM, you wrote:
>
>
>
>>Nevertheless, for the other algorithm the expected time complexity (
>>quite well known in general :-) ) and measured values do no fit together.
>>
>>
>
>number of reductions is not exact time statistics. try the following
>alternative length definition ;)
>
>length2 (_:_:_:_:_:_:_:_:_:_:xs) = (length2 xs)+10
>length2 (_:xs) = (length2 xs)+1
>length2 _ = 0
>
>and compare number of reductions for:
>
>length [1..5000]
>length2 [1..5000]
>
>
>
>
--
Dusan Kolar tel: +420 54 114 1238
UIFS FIT VUT Brno fax: +420 54 114 1270
Bozetechova 2 e-mail: kolar at fit.vutbr.cz
Brno 612 66
Czech Republic
--
More information about the Haskell-Cafe
mailing list