Posted by
| David Haley
USA (3,881 posts) bio
|
Message
| Incidentally, Twisol, your tail-recursive function is actually slower than the non-tail-recursive function...
$ cat test.lua
do
local memofac ={[0]=1}
local function inner_factorial (x)
local result = memofac[x]
if not result then
result = x * inner_factorial(x-1)
memofac[x] = result
end
return result
end
function factorial (x)
assert(type(x) == 'number' and x>=0, "X must be a non-negative integer.")
return inner_factorial(x)
end
end
print(os.time())
for i = 1, 10000000 do
local x = factorial(i)
end
print(os.time())
do
local memofac = {[0] = 1}
local inner_factorial
inner_factorial = function(x, acc, last)
acc = acc * x
memofac[x] = acc
if x == last then
return acc
else
return inner_factorial(x+1, acc, last)
end
end
factorial = function(x)
assert(x >= 0, "X must be greater than or equal to 0.")
if x <= #memofac then
return memofac[x]
end
return inner_factorial(#memofac+1, memofac[#memofac], x)
end
end
for i = 1, 10000000 do
local x = factorial(i)
end
print(os.time())
$ lua test.lua
1283549016
1283549025
1283549037
so not slower by much, but basically this shows that seeking tail recursion is not always a goal in and of itself. Sometimes the extra overhead you introduce by tracking stuff in other ways outweighs the problem of tail recursion.
Now it turns out that the iterative code WillFa wrote is slower yet:
$ cat test2.lua
do
local memofac = {[0] = 1}
local function build_memoized(x)
while #memofac < x do
local newkey = #memofac+1
memofac[newkey] = memofac[#memofac] * (newkey)
end
return memofac[x]
end
function factorial(x)
assert(type(x) == 'number' and x>=0, "X must be a non-negative integer.")
return memofac[x] or build_memoized(x)
end
end
for i = 1, 10000000 do
x = factorial(i)
end
$ time lua test2.lua
lua test2.lua 17.46s user 0.26s system 98% cpu 17.915 total
$
However, this test happens to be pathological for the iterative code as it has to set up the loop structure each time for just a single increment.
Consider this version, which does things in the other order, and adds a few optimizations:
$ cat test3.lua
require 'os'
do
local memofac = {[0] = 1}
function factorial(x)
assert(type(x) == 'number' and x>=0, "X must be a non-negative integer.")
if memofac[x] then
return memofac[x]
end
for y = #memofac, x-1 do
memofac[y+1] = memofac[y] * (y+1)
end
return memofac[x]
end
end
print (os.time())
for i = 10000000, 1, -1 do
x = factorial(i)
end
print (os.time())
$ time lua test3.lua
1283552603
1283552611
lua test3.lua 8.02s user 0.23s system 98% cpu 8.383 total
$
I suspect that were you to run this with JIT, you'd get even better relative performance for the iterative version.
Incidentally, if I take test3.lua and make it compute going forward, we get:
$ time lua test3.lua
1283552677
1283552688
lua test3.lua 11.10s user 0.21s system 98% cpu 11.478 total
$
which is 6 seconds faster than WillFa's. |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | top |
|