временная сложность метатаблицы в Lua при доступе

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

Какова временная сложность доступа к ins.base?


lua lua-table metatable
person 1hunch1kill    schedule 24.04.2014    source источник
comment
Я считаю, что третья строка должна быть cls .__ index = cls   -  person mpeterv    schedule 24.04.2014
comment
Правильно. Моя ошибка @peterm   -  person 1hunch1kill    schedule 24.04.2014
comment
Я думаю, что временная сложность такая же, как для cls.base. Вы просто добавляете несколько поисков по хешу. Сложность по времени для поиска хэша в лучшем O (1) в худшем случае O (n)   -  person moteus    schedule 24.04.2014

Ответы (1)


arrow_upward
3
arrow_downward

Вы можете ожидать 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 поддерживаются хэш-таблицами, поиск в таблицах обычно является операцией с постоянным временем.

person Colonel Thirty Two    schedule 24.04.2014