I want to optimize a Fibonacci function but using table index, and memoization seems a good method (iteration is as good)... However, soon I ran into a problem: I can't decide whether a key is in a table. How can I do that?
local fib = {}
function fib_index(t, k)
if k == 0 or k == 1 then
t[k] = k
else
t[k] = t[k-1] + t[k-2]
end
return t[k]
end
setmetatable(fib, {__index = fib_index})
Your code will run just fine in it's current state. The reason behind that is that already strored values have highter priority than __index metamethod, so if value does exist, it's returned immideately. There are few optimisations which can make your code look better:
local fib = setmetatable({1, 1}, {__index = function(t,k)
assert(k > 0, 'Invalid fib index') -- Most basic check
local res = t[k-1] + t[k-2]
t[k] = res
return res
end})
Here I remove function declaration at all (if you want to reuse it, consider making your function local with local function instead of function) and made code easier by adding inital values directly into table declaration (no index 0 to keep it lua way, also no zero in results) and utilizing the fact that setmetatable return originally passed table. You can remove assert if you want to, but it's probably good idea to see meaningful error message instead of "stack overflow".
And if you really wanna check does value exist in table (this code does not require this), use rawget:
rawget(fib, 10) == nil
will tell you is 10 already calculated and cached.
rawget(fib, k)fib = {[0]=0, [1]=1}. This greatly simplifiesfib_index.