[Haskell-cafe] Hugs - evaluation statistics

[Dusan Kolar]

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

--