• Announcement: Lua.org now officially recommends this forum as a meeting place for the Lua community

Lua and the space/time duality (1 Viewer)

Functions f(x) use a fixed amount of space and who knows how much time, whereas tables t[x] use a fixed amount of time and who knows how much space. The traditional speed-up, trading space for time, is called memoization:
Code:
memoize = function (f)
             local t = { }
             return function (x)
                local a = t[x]
                if not a then
                   a = f(x)
                   t[x] = a
                end -- if
                return a
                end -- function
           end -- function
For example, the traditional Fibonacci function:
Code:
fib = function (n)
         if n < 2 then return n end -- if
         return f(n-1) + f(n-2)
         end -- function
is hopelessly inefficient, but memoize (fib) is much better.
But Lua, uniquely I suspect, lets us trade in the other direction, delaying the filling of a table:
Code:
local t = setmetatable ( { 0, 1}, {
   __index = function (f,x)
             local a = f[x-1] + f[x-2]
             f[x] = a
             return a
             end -- function
      })
newfib = function (x) return t[x] end -- function
The function newfib is better still. Are there other languages that make this space/time duality so explicit?
 

gaurami

Newcomer
Joined
Nov 12, 2020
Messages
2
Reaction score
0
I had to make a correction in the third example:

local t = setmetatable ( { 1, 1}, {
...

to make it produce the same results as the first two examples, but I can't figure out why it works much faster than the "memorized" Fibonacci. Could somebody explain it in the plain Beginnerish?
 
Last edited:

GavinW

Newcomer
Creator of RiscLua
Joined
Oct 21, 2020
Messages
41
Reaction score
17
Age
82
Location
UK
Website
www.wra1th.plus.com
Thanks for the correction. Why is newfib faster? I think it is because table-lookup is faster than function-calling. The point of memoization is to obey the adage "never calculate the same value twice". Ask yourself how many Lua function calls does it take to calculate the n-th Fibonacci number, using these methods? Table-lookup obviously involves a C-function, as does addition, but these are the only operations after the first call to newfib, which calls a Lua function only once. On the other hand memoize(fib) needs to call n Lua-functions, one for each of the numbers less than its argument. Is that any help?
 

gaurami

Newcomer
Joined
Nov 12, 2020
Messages
2
Reaction score
0
Thanks! It's getting clearer: newfib delegates almost all work to C-functions (O( n ) calls of the lookup and the addition functions), while memoize(fib) does almost the same but calling repeatedly Lua functions - correct?
 

GavinW

Newcomer
Creator of RiscLua
Joined
Oct 21, 2020
Messages
41
Reaction score
17
Age
82
Location
UK
Website
www.wra1th.plus.com
Yes. From the mathematical point of view f(x) and f[x] are the same, but computationally they are different. Lua's meta(tables/methods) are very interesting, I think. On the face of it, they seem only to be about tweaking notation, but in fact they give the programmer more flexibility with evaluation strategies. That was really the point I was trying to get across. But meta-magic is an aspect of Lua that is probably fairly frightening for newcomers to the language. It took a while to evolve to its present generality, and I do not know of any other languages with anything similar.
 
Top