Quickly find a specific Entry in a massively long Table

[SegFault22]

With Lua, you can make an ipairs function to iterate through a list until it finds the right entry, then return that entry (or something on the same line, like another property of that entry) - like this:

Code: Select all

table = {
{"red","Red"},
{"green","Green"},
{"blue","Blue"},
}
function <modid>.list_get_name(id,name)
    for _, row in ipairs(table) do
        column_1 = row[1]
        column_2 = row[2]
        if column_1 = id then
            return column_2
        end
    end
end

This makes it very convenient to get for the "name" of an item from a given id - it is a lot better to use the first-capitalized "name" of an item for the description, rather than just use the non-capitalized id. I have been using a similar function which makes it very easy to give a proper description to a large number of items to be registered, when only given the id of an entry in the table of all types (specifically, the "material id" is used to find the "material name", which is passed on to the part of the function which concatenates that to the rest of the name of the item being registered - like "<material name> Pickaxe", for example)
However, when the list is extremely long - such as over 100 entries - I can understand that it would put an enormous load on the processor to iterate through the entire list, looking for one specific entry by checking every single entry, and starting over with the next entry if the previous one does not have the specified id.

I would like to use a more efficient table searching algorithm, which takes significantly less time than the current one (although the time is only taken during the loading stage because these functions are never used during the "running" stage of the server, it is still an enormous load at the stage where it is used). My primitive understanding of Lua does not permit me to readily create an algorithm that goes directly to the specified entry with the given id, although I can understand kinda how such an algorithm should work (and kinda how it would be written too) - however, logic says that even such a cleaner algorithm (which avoids using ipairs to iterate to each entry, checking if it matches the id, and going to the next if it doesn't) would still be just about as resource-hogging as the existing one, because it would have to check each entry by the id before it finds the right one.
Is there something I am missing, or is the currently used method "as quick as it gets"? (specifically, is there a way to go directly to the entry by the specified id, without the program itself having to check each entry until it finds the one which is specified?)

[blert2112]

Do you mean something like this...

Code: Select all

local table = {
	red = "Red",
	green = "Green",
	blue = "Blue"
}

print(table.red)
-- or you could do
print(table["red"])
-- or even
local color = "red"
print(table[color])

edit:
If all you want to do is capitalize the first letter of a word then you could go about like this...

Code: Select all

local str = "red"
str = str:gsub("^%l", string.upper)
print(str)

[SegFault22]

Do you mean something like this...

Code: Select all

local table = {
	red = "Red",
	green = "Green",
	blue = "Blue"
}

print(table.red)
-- or you could do
print(table["red"])
-- or even
local color = "red"
print(table[color])

edit:
If all you want to do is capitalize the first letter of a word then you could go about like this...

Code: Select all

local str = "red"
str = str:gsub("^%l", string.upper)
print(str)

Yes, the first thing is what I was talking about possibly implementing, but it was somewhat beyond my comprehension until now (as there are not many examples of its usage on the internet, outside of very complex scripts which obscure the functionality of themselves). Thank you for providing these simpler examples which have simultaneously cleared up many of my misunderstandings of the Lua functionality.
However, I need to know if the Lua engine/core still has to iterate through all of the entries in the table until it finds table.red or table["red"]. Does it still have to search the whole table until it finds which entry is "red", or does it just go to table.red without "hitting" any of the other entries? If it still goes to all preceding entries first before finding the right one and returning for the next step, it will take about as long to compute as the earlier code, which is unintended. I will upgrade my code to use this method where it can be applied, regardless of if it reduces the computational load or not - because it is a lot "cleaner" than what I have wrote before, simpler to work with, and much easier to understand.

Regarding the code to capitalize the first letter, I see where it can be useful but I currently don't have anywhere to use it, as it will not be compatible with my naming conventions which often include underscores when referencing sub-types of certain items, where applicable. Still, thank you for providing this, as it will be useful in several places in the future (such as the fluid API mod, which I will begin working on as soon as I release the mod I am currently working on)

Again, thank you for the help with this. I am working on a large, ground-breaking new mod, and this functionality will be very useful for a lot of stuff I still have to make.

[blert2112]

Any time.
I have no clue if it still iterates through the table but, I would assume that if it does, it would do it in the fastest way possible. I think it is just like calling a variable though. you can always test it if you like. See here...
http://dev.minetest.net/minetest.get_us_time

[SegFault22]

Any time.
I have no clue if it still iterates through the table but, I would assume that if it does, it would do it in the fastest way possible. I think it is just like calling a variable though. you can always test it if you like. See here...
http://dev.minetest.net/minetest.get_us_time

Alright, I will see how long it takes compared to the other method. However, I believe that it will be much faster than what I was using before, because it doesn't use ipairs and all that. Again, thank you - I did not even know about the minetest.get_us_time() function until now.

[rubenwardy]

That method is like an index.
You could also try a binary search algorithm instead. It's O(n*log n) iirc.