lua - 访问时Lua中元表的时间复杂度

Question

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

访问的时间复杂度是多少ins.base？

Answer 1

O(1)您可以从官方 Lua 实现中预期时间复杂度。

的代码__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 表由哈希表支持，因此查找表通常是一个恒定时间的操作。