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: [EMAIL PROTECTED]
Brno 612 66
Czech Republic

--

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to