declare Fact LazyFact

%Regular factorial

fun {Fact N}

fun {Iter X A}

if X>0 then

{Iter X-1 X*A}

else A end

end

in

{Iter N 1}

end

%Lazy Factorial

local

fun lazy {LazyMul X Y}

X*Y

end

fun lazy {LazySubstract X Y}

X-Y

end

in

fun lazy {LazyFact N}

fun lazy {Iter X A}

if X>0 then

{Iter {LazySubstract X 1} {LazyMul X A}}

else A end

end

in

{Iter N 1}

end

end

%Use following code to find elasped time

for I in 1..5 do

N = 30000

R1 T1 T2 in

T1 = {Property.get 'time.total'}

% R1 = {Fact N} %COMMENT FOR LAZY FACT

% doing +/-1 to trigger the lazy fact, assuming it

% takes negligible time

R1 = {LazyFact N}+1-1 %COMMENT FOR REGULAR FACT

T2 = {Property.get 'time.total'}

{Show fact(n:N timeInMs:(T2-T1))}

end

Results with N=20000, 25000, 30000:

Regular Fact:

fact(n:20000 timeInMs:2038)

fact(n:20000 timeInMs:763)

fact(n:20000 timeInMs:1914)

fact(n:20000 timeInMs:919)

fact(n:20000 timeInMs:1976)

fact(n:25000 timeInMs:1976)

fact(n:25000 timeInMs:2553)

fact(n:25000 timeInMs:2459)

fact(n:25000 timeInMs:2505)

fact(n:25000 timeInMs:2522)

fact(n:30000 timeInMs:4373)

fact(n:30000 timeInMs:3160)

fact(n:30000 timeInMs:3066)

fact(n:30000 timeInMs:3922)

fact(n:30000 timeInMs:3034)

Lazy Fact:

fact(n:20000 timeInMs:2879)

fact(n:20000 timeInMs:1105)

fact(n:20000 timeInMs:2148)

fact(n:20000 timeInMs:2521)

fact(n:20000 timeInMs:2692)

fact(n:25000 timeInMs:3455)

fact(n:25000 timeInMs:2801)

fact(n:25000 timeInMs:3986)

fact(n:25000 timeInMs:3334)

fact(n:25000 timeInMs:3380)

fact(n:30000 timeInMs:5577)

fact(n:30000 timeInMs:5468)

fact(n:30000 timeInMs:5343)

fact(n:30000 timeInMs:5592)

fact(n:30000 timeInMs:5001)

Conclusion:

Lazy version is usually slow due to the thread overhead caused by implementation of laziness.

## No comments:

## Post a Comment