訪問時Lua中metatable的時間複雜度

Question

local cls = {base = "base"} 
local ins = {} 
cls.__index = cls 
setmetatable(ins, cls) 

訪問ins.base的時間複雜度是多少？

Answer 1

您可以期望從官方Lua實施中獲得O(1)時間複雜度。

爲__index的代碼是大致相當於這個的Lua代碼，從手動採取：

function gettable_event (table, key) 
    local h 
    if type(table) == "table" then 
    local v = rawget(table, key) 
    if v ~= nil then return v end 
    h = metatable(table).__index 
    if h == nil then return nil end 
    else 
    h = metatable(table).__index 
    if h == nil then 
     error(···) 
    end 
    end 
    if type(h) == "function" then 
    return (h(table, key))  -- call the handler 
    else return h[key]   -- or repeat operation on it 
    end 
end 

的__index查找本身沒有環路，並且由於Lua的表由哈希表的支持下，表查找通常是恆定時間的操作。