优化 Lua Table 搜索

Question

我有一个 LUA table:

local tableDatabase = {
  name = uniqueName,
  class = val_one_to_eight,   --not unique
  value = mostly_but_not_guaranteed_unique_int}

这个table可以按以上任何一种排序，可能包含一个非常大的数据集。

现在为了插入我只是遍历 table ipairs 直到我找到：

 insertedvalue.uniqueName > tableDatabase.uniqueName
 --(or comparing the other parms instead if they are the selected sort order.)

我需要这个功能来超快地工作。是否有人可以推荐一种搜索算法来查找要插入的 table 中的索引，或者我可以使用某种方法来对 lua table 进行优化以优化插入速度？

Answer 1

据我所知，对于严格排序的结构，您可以使用二进制搜索或类似算法。 Lua 用户 provides 准备使用功能。

Answer 2

为什么不在 name 上创建索引？如果它不够快，您可以使 __index 不那么通用，即硬编码 name.

上的唯一索引

-- Returns a table. ... is a list of fields, for which unique indices should be created:
function indexedTable (...)
    local t = {
        __indices = {},
        __insert = function (self, value)   -- instead of table.insert.
            self [#self + 1] = value    -- implicily calls metamethod __newindex.
        end     
    }
    -- Initialise indices:
    for _, index in ipairs {...} do
        t.__indices [index] = {}
    end
    setmetatable (t, {
        -- Allow t [{name = 'unique'}]:
        __index = function (t, key)
            if type (key) == 'table' then
                for index_key, index_value in pairs (key) do
                    local value = t.__indices [index_key] [index_value]
                    if value then
                        return value
                    end
                end
            else
                return rawget (t, key)
            end
        end,
        -- Updates all indices on t [k] = v, but doesn't work on table.insert, so use t:__insert"
        __newindex = function (t, key, value)
            -- insert uniqueness constraint here, if you want.
            for index_key, index in pairs (t.__indices) do
                index [value [index_key]] = value
            end
            rawset (t, key, value)
        end
    })
    return t
end

-- Test:

local tableDatabase = indexedTable ('name')

-- Not table.insert, as it is not customizable via metamethods:
tableDatabase:__insert {
    name    = 'unique1',
    class   = 1,
    value   = 'somewhat unique'
}

tableDatabase:__insert {
    name    = 'unique2',
    class   = 2,
    value   = 'somewhat unique'
}

tableDatabase:__insert {
    name    = 'unique3',
    class   = 2,
    value   = 'somewhat unique but not absolutely'
}

local unique2 = tableDatabase [{name = 'unique2'}]  -- index search.
print (unique2.name, unique2.class, unique2.value)

优化 Lua Table 搜索

Optimized Lua Table Searching

search

lua

lua-table