[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:

          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. :-)


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