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