Map and filter without intermediate tables

test_map_and_filter.lua

-- Testing map and filter without intermediate tables
-- So far it's slower and more complicated than with those 'wasteful'
-- intermediate tables

-- If you're comparing PUC lua and luajit, note that the tests to 10 times
-- more iterations for luajit.

local TABLE_SIZE          = 100
local ITERATIONS          = jit and 1000000 or 100000


-- pairs compatibility ---------------------------------------------------------

local pairs, ipairs = pairs, ipairs

if not table.unpack then
  local rawipairs, rawpairs = ipairs, pairs

  local function getmetamethod(obj, methodname)
    local mt = getmetatable(obj)
    return mt and mt[methodname]
  end


  pairs = function(t)
    local f = getmetamethod(t, "__pairs")
    if f then
      return f(t)
    else
      return rawpairs(t)
    end
  end


  ipairs = function(t)
    local f = getmetamethod(t, "__ipairs")
    if f then
      return f(t)
    else
      return rawipairs(t)
    end
  end
end


-- map and filter with metatables ----------------------------------------------

local map_helper_mt =
{
  __pairs = function(h) return h, h[3], h[4] end,
  __ipairs = function(h) return h, h[3], h[4] end,
  __call = function(h, state, k)
      local v
      k, v = h[1](state, k)
      return k, k and h[2](v)
    end,
}
-- map in pairs order with no intermediate table
local function map(t, f)
  local iterator, state, initial = pairs(t)
  return setmetatable({iterator, f, state, initial}, map_helper_mt), state, initial
end
-- map in ipairs order with no intermediate table
local function imap(t, f)
  local iterator, state, initial = ipairs(t)
  return setmetatable({iterator, f, state, initial}, map_helper_mt), state, initial
end


-- filter in pairs order with no intermediate table
local filter_helper_mt =
{
  __pairs = function(h) return h, h[3], h[4] end,
  __call = function(h, state, k)
      local v
      repeat
        k, v = h[1](state, k)
      until k == nil or h[2](k, v)
      return k, v
    end,
}
local function filter(t, f)
  local iterator, state, initial = pairs(t)
  return setmetatable({iterator, f, state, initial}, filter_helper_mt), state, initial
end


-- filter in ipairs order with no intermediate table.
-- We have to muck around to get the output indices right
local ifilter_helper_mt =
{
  __ipairs = function(h) return h, h[3], h[4] end,
  __call = function(h, state, k)
      local j, v
      repeat
        j, v = h[1](state, h[5])
        if not j then return end
        h[5] = j
      until h[2](j, v)
      return k+1, v
    end,
}
local function ifilter(t, f)
  local iterator, state, initial = ipairs(t)
  return setmetatable({iterator, f, state, 0, initial}, ifilter_helper_mt), state, 0
end


-- map and filter with closures ------------------------------------------------

-- map in any order with a closure
local function mapc(f, iterator, state, initial)
  local k, v = iterator(state, initial)
  return function()
    if k == nil then return end
    local k0, v0 = k, v
    k, v = iterator(state, k)
    return k0, f(v0)
  end
end
local imapc = mapc

-- filter in pairs order with a closure
local function filterc(f, iterator, state, initial)
  local k, v = iterator(state, initial)
  return function()
    if k == nil then return end
    local k0, v0
    repeat
      k0, v0 = k, v
      k, v = iterator(state, k)
    until k == nil or f(k0, v0) == true
    return k0, v0
  end
end


-- filter in ipairs order with a closure
local function ifilterc(f, iterator, state, initial)
  local k, v = iterator(state, initial)
  local j = 0
  return function()
    if k == nil then return end
    local k0, v0
    repeat
      k0, v0 = k, v
      k, v = iterator(state, k)
    until k == nil or f(k0, v0) == true
    j = j + 1
    return j, v0
  end
end


-- map and pairs with intermediate tables --------------------------------------

-- map in pairs order with an intermediate table.  Much simpler.
local function mapt(t, f)
  local r = {}
  for k, v in pairs(t) do
    r[k] = f(v)
  end
  return r
end


-- map in ipairs order with an intermediate table.  Take advantage of numeric for.
local function imapt(t, f)
  local r = {}
  for i = 1, #t do
    r[i] = f(t[i])
  end
  return r
end


-- filter in pairs order with an intermediate table
local function filtert(t, f)
  local r = {}
  for k, v in pairs(t) do
    if f(k, v) then
      r[k] = v
    end
  end
  return r
end


-- filter in ipairs order with an intermediate table.  Take advantage of numeric for.
local function ifiltert(t, f)
  local r, j = {}, 1
  for i = 1, #t do
    local v = t[i]
    if f(i, v) then
      r[j] = v
      j = j + 1
    end
  end
  return r
end


-- Tests -----------------------------------------------------------------------

-- A little test iterable object.
local a = setmetatable({},
{
  __pairs = function(a) return a, nil, 0 end,
  __ipairs = function(a) return a, nil, 0 end,
  __call = function(a, _, i)
    i = i + 1
    if i <= TABLE_SIZE then
      return i, i % 100
    end
  end
})
local function even(i) return i%2==0 end
local function square(v) return v*v end


-- pairs order, no intermediate table
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  for k, v in map(filter(a, even), square) do
    sum = sum + k + v
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("map(filter): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- pairs order, closure
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  for k, v in mapc(square, filterc(even, pairs(a))) do
    sum = sum + k + v
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("mapc(filterc): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- pairs order, intermediate table.  We have to call pairs on the result of mapt.
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  for k, v in pairs(mapt(filtert(a, even), square)) do
    sum = sum + k + v
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("mapt(filtert): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- ipairs order, no intermediate table
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  for k, v in imap(ifilter(a, even), square) do
    sum = sum + k + v
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("imap(ifilter): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- ipairs order, closure
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  for k, v in imapc(square, ifilterc(even, ipairs(a))) do
    sum = sum + k + v
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("imapc(ifilterc): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- ipairs order, intermediate table.  Because we used the numeric for above,
-- we need to start with a real table.
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  local a2 = {}
  for i = 1, TABLE_SIZE do
    a2[i] = i % 100
  end
  local r = imapt(ifiltert(a2, even), square)
  for i = 1, #r do
    sum = sum + i + r[i]
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("imapt(ifiltert): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- Just do it (in ipairs order)
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  local j = 1
  for k = 1, TABLE_SIZE do
    if k % 2 == 0 then
      local v = k % 100
      sum = sum + j + v * v
      j = j + 1
    end
  end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("loop (ipairs order): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")


-- Three tables (in ipairs order)
local sum = 0
local start = os.clock()
for i = 1, ITERATIONS do
  local t1 = {}
  for j = 1, TABLE_SIZE do t1[j] = j % 100 end
  local k, t2 = 1, {}
  for j = 1, #t1 do if j % 2 == 0 then t2[k] = t1[j]; k = k + 1 end end
  local t3 = {}
  for j = 1, #t2 do local v = t2[j]; t3[j] = v * v end
  for j = 1, #t3 do sum = sum + j + t3[j] end
end
local stop1 = os.clock()
local s = collectgarbage("count")
collectgarbage("collect")
io.stderr:write("three tables (ipairs order): ", stop1 - start, "s, ", os.clock() - start, "s, ", s, "kb, ", sum, "\n")