table.find(…) vs Key Indexing
This is an interesting problem I have been noticing throughout the community. I have been seeing a lot of people use table.find even when indexing a key in a dictionary was possible for them. In this article, I will be going over why that isn’t the most efficient solution and also a brief introduction to algorithms and time complexity.
Ⅰ. Algorithms
What is an algorithm? Think of an algorithm as a set of instructions to achieve your result. A basic example would be baking a cake. Let’s look at some general steps on how to bake a cake.
- Get ingredients
- Mix
- Pour batter into pan
- Put in oven
That is a set of instructions to bake a cake. Though these steps could be more specific, we are only going to focus on the broader part. It seems that computers can also follow instructions we give to achieve our result the same way.
Now, let’s move away from the cake part and focus on giving a machine instructions. Let’s say we have an randomly-arranged array of numbers. How do we tell the computer to find the given number? Most of you reading this would probably say iterate over every number and check if it is the number we want. Ok, well let’s try to define that in pseudocode.
array= {1,4,2,0,9,10,3}
numberToFind = 2
foundNumber = false
for each number in array:
if number == numberToFind:
foundNumber = true
break
print(foundNumber)
Now, as you can see from the pseudocode. We create an unsorted array that contains different numbers. We loop through each number in the array. If the number in the array is the number we want, then we change foundNumber to true and break the loop. Now let’s do the same thing but in Lua.
local numbers = {1,4,2,0,9,10,3}
local numberToFind = 2
local foundNumber = false
for _,number in ipairs(numbers) do
if number == numberToFind then
foundNumber = true
break
end
end
print(foundNumber)
Congrats! We just created an algorithm to find a number. Now this leads us into a few questions? How efficient is our algorithm? Was there any other possible solution? How do we measure the efficiency of an algorithm?
ⅠⅠ. Algorithm Efficiency
We are going to dive a little deeper into learning about time complexity(I don’t want this article to focus too much on the math part, so I won’t be explaining how to measure the time complexity). Time Complexity describes how many operations an algorithm has to do based on the input given.
It all starts with Big O Notation. If you have seen people say things like “Hey, that algorithm is O(n)” or “The time complexity of the algorithm is O(n^2)”, you have probably wondered what they mean. If you haven’t, don’t fret.
In Computer Science, we use Big O Notation to describe the performance of an algorithm(time complexity). Since machines are different and efficiency varies, we use Big O. O is basically a function and n is our input. If you go back to the algorithm we made in section one, n would the number of elements in the array.
Big O Notation tells us how many steps an algorithm has to take to achieve the result. It’s usually used to describe it in the worst-case scenario. What would be the worst case for the algorithm we made in section one? Well, let’s think about it. What if the number we wanted to find was at the very end of the array. How many steps or iterations will it take to find that number? It would take us n iterations or exactly the length of array.
Let’s say we added more numbers to the array. In the worse-case scenario, would it still take n number of steps? Yes, it would. Ok! Well, what about the best-case scenario? What if the number we were looking for was the first element of the array? How many iterations or steps would it take? It would take us 1 iteration.
Ok, we are starting to see the efficiency of this algorithm. So the algorithm we made in section one has a worst-case scenario of O(n) or a best-case scenario of Ω(1). We use the “Ω” or omega symbol to represent best-case scenario. It turns out we can actually graph this.
I only want you to pay attention to the green and yellow line. t is how long the algorithm takes and n is how big our input is. As you can see, the green line is proportional or linear. For the green line, the time the algorithm takes is proportional to the input size. For the yellow line, no matter how large the input is, it will always take the same amount of time. We can call the green line a linear complexity and the yellow line a constant complexity.
Our algorithm we made is a linear complexity for the worst-case scenario. Now if we got lucky and the number were looking for was the first element, it would only take us 1 step. So our best-case scenario was a constant complexity.
ⅠⅠⅠ. The Efficiency of table.find
If you take a look at the screenshot from Roblox API-Reference for table, you will see it says “A linear search algorithm is performed”. What is a linear search algorithm? Well, we implemented the same algorithm in section 1.
table.find works the same way. It has a worst-case scenario of O(n) and a best-case scenario of Ω(1). If you start thinking of large inputs to give table.find, you can see that the algorithm is not efficient. Again, we could get lucky and it could take us a few steps, but we could also be
extremely unlucky and the number was at the end of the array.
local array = {3, 2, 1, 5, 0, 4, 10, 32, 46, 21, 102, 59, 105}
table.find(array, 105) -- This takes us n iterations or for our case, exactly 13 iterations.
table.find(array, 3) -- This takes us 1 iteration.
If you take a look at comments, you will see how many steps or iterations it would take to find the number.
Ⅳ. table.find vs Key Indexing
Now in this section we are going to look at what’s more efficient. If your confused on what I mean by “key indexing”, it means to index into a dictionary using a key.
Now let’s think of a game scenario in where we would use table.find. How about a whitelist system? Only certain people can join your game(I know not the best scenario, but it works for now).
local whitelist = { -- A table full of UserIds that are allowed to play your game.
12345678, 984210983, 741290,
8321038, 48103210, 48810321,
9321301, 83747310, 93931209,
8031203, 830821083, 1729321
}
game:GetService("Players").PlayerAdded:Connect(function(Player)
if not table.find(whitelist, Player.UserId) then -- If it did not find the UserId in the table
Player:Kick("Not allowed to join the game.") -- Kick the player
end
end)
Ok. We have a simple whitelist script. What if the player who joined had a UserId of 1729321? It would take us n number of iterations to find it or the length of the table. As you can see, using table.find for this is not the most efficient way. What if we made the whitelist a dictionary using the UserId as the key?
local whitelist = { -- A dictionary with UserIds as the key
["12345678"]=1, ["984210983"]=1, ["741290"]=1,
["8321038"]=1, ["48103210"]=1, ["48810321"]=1,
["9321301"]=1, ["83747310"]=1, ["93931209"]=1,
["8031203"]=1, ["830821083"]=1, ["1729321"]=1
}
game:GetService("Players").PlayerAdded:Connect(function(Player)
if not whitelist[tostring(Player.UserId)] then -- If it did not find the UserId key
Player:Kick("Not allowed to join the game.") -- Kick the player
end
end)
This is a lot more efficient than using table.find. We could have the value to be pretty much anything truthy. 1 is just short to type.
I hope this article helped you realize how there are better alternatives to table.find most of the time. For what table.find is meant to do, it is as efficient as it can be. If you notice any typos or mistakes, please let me know. As this is my first article on DevForum, it might not be the best. Thank you for reading.
