Caching expensive table calculation on strings between separate function calls in Lua

Question

I have a number of functions operating on strings to extract interesting properties from those strings. One particular function which is called by many of those functions is very expensive and ultimately generates a table of values:

local function expensive(s)
  local t = nil
  return function()
    if not t then
      t = {}
      -- some expensive operations with s which add items to t
    end
    return t
  end
end

local function fn1(s)
  local t = expensive(s)
  -- some other fast operations using t and s
end

local function fn2(s)
  local t = expensive(s)
  -- some other fast operations using t and s
end

local s1, s2 = 'a', 'b'
fn1(s1) -- should create the 't' table for s1
fn1(s2) -- should create the 't' table for s2
fn2(s1) -- should not create the 't' table again for s1
fn1(s2) -- should also not create the 't' table again for s2

How can I make it so that the expensive function creates the table exactly once per string, returning the table in either case? I would rather not have the table exposed to the global environment. I think this could probably be accomplished by some clever use of closures, but I don't know the construct well enough.

score 4 · Answer 1 · answered May 18 '17 at 16:44

4

local cache = {}

local function expensive(s)
  local t = cache[s]
  if not t then
    t = {}
    -- some expensive operations with s which add items to t
    cache[s] = t
  end
  return t
end

answered May 18 '17 at 16:44

Egor Skriptunoff

23,359
2
34
64

This is the solution I initially developed, but the cache is exposed to the script environment which isn't ideal. Jack's answer offers two solutions around this. – ruser9575ba6f May 19 '17 at 13:54
1

`cache` is not in global environment – Egor Skriptunoff May 19 '17 at 13:58
Fair enough. I mean the script's environment. – ruser9575ba6f May 19 '17 at 13:59
1

That is "lexical scope" – Egor Skriptunoff May 19 '17 at 14:00

Jack Taylor · Accepted Answer · 2017-05-19T23:26:52.250

Egor's answer will do the job, but the cache table is accessible by the whole file. To hide it, you have a couple of options. The first is a simple do/end block.

local expensive
do
    local cache = {}
    expensive = function (s)
      local t = cache[s]
      if not t then
        t = {}
        -- some expensive operations with s which add items to t
        cache[s] = t
      end
      return t
    end
end

The other is a self-executing function.

local expensive = (function ()
    local cache = {}
    return function (s)
      local t = cache[s]
      if not t then
        t = {}
        -- some expensive operations with s which add items to t
        cache[s] = t
      end
      return t
    end
end)()

The self-executing function has the advantage that you only have to define the expensive function name once, but the disadvantage that it is a little harder to read than the do/end block. Otherwise they are pretty much the same.

The do ... end block is clever! They have a similar example in the lua reference manual but I hadn't thought of using it in this case. — ruser9575ba6f, May 19 '17 at 13:58

score 2 · Answer 3 · edited May 23 '17 at 11:33

2

You can use "memoization" to cache the values returned by the function depending on the parameters. You can read a chapter on it in Programming in Lua and use one of the memoization modules that do the work for you, for example, memoize.

See also this SO answer for related interesting solutions.

edited May 23 '17 at 11:33

Community

1
1

answered May 19 '17 at 05:04

Paul Kulchenko

25,884
3
38
56

Caching expensive table calculation on strings between separate function calls in Lua

3 Answers3