lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On 21-Sep-06, at 8:50 PM, Luis Carvalho wrote:

Fib = Memoise(function(n)
  return Fib(n-1) + Fib(n-2)
Fib[1] = 1
Fib[2] = 1

= Fib[200]

The definition of Memoise I use has been left abandoned on the Lua Wiki
at since January 17, 2003 :) so I
won't bother repeating it here.

By the way, the above example won't work with values larger than
200 unless you recompile Lua with a larger C recursion limit
(LUAI_MAXCCALLS in luaconf.h)

You could also avoid the C recursion limit by having a memoization scheme that
does not use functables:

Sure. My original point was simply that Lua is capable of expressing patterns, albeit with a limitation (increasing LUAI_MAXCCALLS is perfectly fine on most systems, in fact.)

Actually, the fibonacci recursion can be written so as to use neither the Lua nor the C stack:

local function fibaux(k, a, b)
  if k == 1 then return a
  else return fibaux(k-1, a+b, a)
function fib(k) return fibaux(k, 1, 0) end

Memoizing is mostly of use when the range of the function is not large and values either occupy space or are difficult to compute (or both). A simple example is this function which could be used to replace string.rep for constant strings:

indent = Memoise(function(n) return indent[(n - n%2) / 2]..indent[(n + n%2) / 2] end)
indent[0] = ""
indent[1] = "  "

(Did I mention how useful an integer division operator would be :) )

Of course, that's just showing off because in a typical application, the range of arguments to indent would be rather small, and a more naive recursion would be just as good. As written, it's capable of handling fairly large arguments without coming close to exceeding the c stack limit, although it might exceed the heap in such cases.

Even though string.rep is very fast, the memoised version is significantly faster in what might be a common profile:

function time(n, fn)
local was = os.clock(); for i = 1, n do fn() end; print (os.clock() - was)
> time(1e5, function() local a = ("  "):rep(math.random(1, 32)) end)
> time(1e5, function() local a = indent[math.random(1, 32)] end)

As another example, consider the higher-order function 'partial' which takes a function f and some arguments, and returns a new function f' with initial arguments "filled in". This is tricky, and I don't claim this to be the best solution:

function partial(f, ...)
  local a = {n = select('#', ...), ...}
  return function(...)
    local b = {n = select('#', ...), ...}
    local c = {}
    for i = 1, a.n do c[i] = a[i] end
    for i = 1, b.n do c[a.n + i] = b[i] end
    return f(unpack(c, 1, a.n+b.n))

> p = partial(print, 1, nil, 4)
> p(2, nil, nil, 5)
1       nil     4       2       nil     nil     5

Ok, so that works, at least, but it's hardly a speed demon.

On the other hand, it's trivial to write partial for any known number of arguments:

function partial3(f, a1, a2, a3)
  return function(...)
    return f(a1, a2, a3, ...)

Unsurprisingly, this is much faster, like a factor of 25:

> function I(...) return ... end
> p = partial(I, 1, nil, 4)
> return p(2, nil, nil, 5)
1       nil     4       2       nil     nil     5
> p3 = partial3(I, 1, nil, 4)
> return p3(2, nil, nil, 5)
1       nil     4       2       nil     nil     5
> time(1e5, function() p(2, nil, nil, 5) end)
> time(1e5, function() p3(2, nil, nil, 5) end)

-- Almost exactly 25 times as fast
> time(25e5, function() p3(2, nil, nil, 5) end)

Ok, so how do we get the speed of partial3 with the flexibility of partial? One solution is to generate the code for each partialk, and compile it. That's a clear case where memoisation is going to be a big win:

Arglist = Memoise(
  function(i) return Arglist[i-1]..", a"..i end
Arglist[0] = ""
Arglist[1] = "a1"

Partial = Memoise(
    return loadstring(
      [[return function(f, ]]..Arglist[i]..[[)
         return function(...) return f(]]..Arglist[i]..[[, ...) end
    ) ()

-- Special case for no arguments, also saves worrying about commas
Partial[0] = function(f) return f end

function memo_partial(f, ...)
  return Partial[select("#", ...)](f, ...)

memo_p3 = memo_partial(I, 1, nil, 4)
-- This is exactly the same function as p3
time(25e5, function() memo_p3(2, nil, nil, 5) end)