Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
1

How do I remove a member of a table without knowing its position?

Asked by
Trew86 175
6 years ago
local system = game.Workspace:GetChildren()
local myTable = {}

for i, v in pairs(system) do
    if v.Name == "Boogie" then
        table.insert(myTable, v)
        if v.Bool.Value == false then
            --how do I remove v from the table?
        end
    end
end

I would have used table.remove, but I don't know what to put for the position parameter since I don't know the position of v in the table. How can I find the position of v and remove it?

2 answers

Log in to vote
4
Answered by
Rare_tendo 3000 Moderation Voter Community Moderator
6 years ago
Edited 6 years ago

You can run another for loop to find the index of the value in the table:

local system = game.Workspace:GetChildren()
local myTable = {}

function removeValue(val)
    for i,v in pairs(myTable) do
         if v == val then
              table.remove(myTable, i)
         end
    end
end

for i, v in pairs(system) do
    if v.Name == "Boogie" then
        table.insert(myTable, v)
        if v.Bool.Value == false then
            removeValue(v)
        end
    end
end

Please accept if it worked

Ad
Log in to vote
3
Answered by
fredfishy 833 Moderation Voter
6 years ago

The question you're asking is basically "How do I find an element in a list". This isn't a problem unique to Lua or to ROBLOX, so you'll be able to find a whole bunch of stuff online.

In addition to Doobb_yyus's answer, you might want to look in to hashing, or in to binary searches.

Hashing

Hashing is probably the best solution to the problem in the general case in terms of raw performance.

While a linear search (going through every item in turn to check if it's what we want, Doobb_yyus's answer) works in pretty much every case we can throw at it, if we have a really long list, it's fairly expensive to do.

On the contrary, hashing takes exactly the same amount of time to find an element in a list whether we have 10 elements or whether we have 1 000 000 000. (Slight caveat to this - this doesn't apply if the list doesn't fit into memory, but you won't ever need to worry about this in ROBLOX. This only really becomes a problem if you're writing something on the scale of an enterprise-grade database manager or something.)

Here's a post I wrote about how hashing works.

In short, rather than assigning our values indexes of 1, 2, 3, 4, ..., we assign them an index based on something we can calculate from the value itself.

For example, if we were storing strings, we could convert letters to numbers (a -> 1, b -> 2, etc) and add all these numbers up. The string "aab" would hash to 1 + 1 + 2 = 4, so we'd look at index 4 for the value.

HOWEVER, hashing is one of those things in Computer Science which is actually really difficult to get right, and entire research papers will have been written solely on the basis of generating efficient hashing algorithms for classes of values in a certain domain. So, you very rarely actually properly write your own hashing function - you let the language do it for you.

In the case of Lua, arrays/lists/dictionaries/tables are actually all the same thing - they all use this method of indexing data. If you've ever wondered how the hell Lua builds a data structure on the basis of very human-friendly things like strings, this is how.

If you have a table in Lua, tab, and we assign an element x to index "banana", the syntax for this is obviously tab["banana"] = x. What Lua does "Under the hood" is exactly this hashing method we've discussed.

In your case, it looks like you could index myTable by player name, meaning that rather than doing table.insert(myTable, valueWeWantToRemoveLater), you'd do table[characterName] = valueWeWantToRemoveLater.

Then, when we want to remove it later, we can just do table[characterName] = nil.

Binary search

I won't go too much in to binary search, because it requires input to be sorted, and that doesn't look to be the case here.

Basically, if you have a long list of sorted numbers, how do you check for the presence of a sepcific number? The naive way to literally go through, number by number, checking to see if the current one matches the one you're looking for.

A much better way is to start in the middle, so if we have 100 numbers, we'd start at the 50th. We compare numbers[50] to targetNumber. If numbers[50] > targetNumber, it means that the number we're searching for MUST be in the left half of the list, if it's present at all. If numbers[50] < targetNumber it MUST be in the right, if present at all. If numbers[50] == targetNumber, we've found it, and can terminate.

Because we're talking about a really common issue in Computer Science, you probably don't even have to write this yourself. A quick Google search of "Lua binary search implementation" yielded this, which you could probably just stick straight in your program in most circumstances.

In terms of the number of cycles required to find an element, we're looking at lg n, where n is the number of elements in our list. lg x is a maths way of saying "how many times do we need to divide x by 2 before it gets to 1? So lg 100 is 6.64ish. Therefore, running on a list of size 100, we'd need to do a maximum of 7 cycles. Compared to the average case performance of a linear search at 50 cycles, this is much better.

Optimising a basic linear search

If you do decide on a linear search, there are still some small ways to optimise it. If you're interested, you can look up "search sentinels". However, at this point, unless you're working with a ridiculously hot piece of code, the savings you'd see are easily swallowed by the overheads involved in using Lua over something like C.

Summing up

Basically, in terms of ROBLOX, these methods probably won't ever be very useful. You're not massively likely to run in to anything requiring a list of more than 100 elements, and computers are pretty fast, so this is easy.

However, if you ever go further in programming, these are really core concepts it's good to understand. For example, even though you might not use a binary search here, SO many problems in Computer Science basically just turn out to be a binary search in disguise.

For more information you can look up asymptotic time complexity / big O notation.

1
Oh my god, how long did it take you to type all that Amiaa16 3227 — 6y
0
20ish minutes? I'm hoping it should be equally as applicable to other questions, so people can link back to it if they need to in future. fredfishy 833 — 6y
0
love it DinozCreates 1070 — 6y

Answer this question