Created
June 7, 2012 03:35
-
-
Save geoffleyland/2886368 to your computer and use it in GitHub Desktop.
Map and filter without intermediate tables
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- 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") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment