Sunday, February 1, 2009

Ch4, Ex15

I'm putting a regular and a complete lazy version of iterative factorial.
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