Optimized Lua Table Searching

Question

I have a LUA table:

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

This table can be sorted by any of the above and may contain a very large data set.

Right now in order to insert I'm just iterating through the table ipairs until I find:

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

I need this function to work super fast. Is there a search algorithm someone could recommend for finding the index into the table to insert or some method I could use that would work on a lua table to optimize this for speed of insertions?

Answer 1

Why don't you create an index on name? If it is not fast enough, you can make __index less generic, i.e. hardcoding the only index on 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)

Answer 2

As I know, for strictly ordered structure you can use binary search or similar algorithms. Lua Users provides ready to use function.