The Better Way To Remove a Value From a Table?


  • A long time ago before the Roblox forums were removed, I asked a question about what table.remove does when removing a value from a table. What was responded with was that that blank would be filled in. For example:

    local Table = {1, 2, 3}
    table.remove(Table, 2)
    

    Instead of becoming 1, nil, 3 it would bump up the 3, or 1, 3. (Something like this, anyways.)

    Now here comes the question. :P Because it does this, is it better to go from the end of the table to the beginning?

    local Table = {1, 2, 3}
    for i = #Table, 1, -1 do
    if Table[i] == 2 then
    table.remove(Table, i)
    end
    end
    

    Or from start to end?

    local Table = {1, 2, 3}
    for i = 1, #Table do
    if Table[i] == 2 then
    table.remove(Table, i)
    end
    end
    

  • It does not matter at all.


  • @kingdom5 Wdym?

  • Global Moderator

    @TheAlphaStigma What kingdom mean is that either way it will require a linear traversal of the table, which you should avoid if possible.

    Consider using a different data structure, like a set. But of course if that's not possible or if your collection is going to contain few elements then a linear traversal is fine.

    A linear traversal has a worst case time complexity of O(n), where n is your input size; the length of your list. In other words in the worst case scenario -- that is if the value you are searching for is located at the end of your list -- then it will take exactly n steps.

    A linear complexity O(n) means the amount of steps is directly tied to the input size, which consequently means that for larger and larger lists it will take more time and more time.

    I mentioned using a different data structure earlier. Specifically sets. A set data structure is a collection that provides insertion, removal, and membership test operations in constant time complexity O(1), but it has no notion of ordering*, and does not allow duplicate elements*. While sets have no notion of ordering, it is still possible to iterate through their elements. However the order these elements are browsed in is unspecified.

    Constant time complexity O(1), quickly followed by logarithmic time complexity O(log(n)), are the best you can hope to achieve, while factorial O(n!) and exponential O(k^n) (where k is some constant) are the worst time complexity you can achieve.

    * : depending on the implementation.


  • @Link150 Just to make sure, is this what kingdom5 and you are talking about?

  • Global Moderator

    @TheAlphaStigma Yes, that is an implementation of a set.


  • @Link150 Nice. I'll study more on it. :D


  • A set in Lua will, for the most part, have an O(1) time complexity for membership tests. A membership test such as

    function Set:Contains(x)
      return self.Set[x] == true
    end
    

    will work for many values (1, "Hello world!", math.pi), but not for all.

    Say you have some class Vector1, not too exciting but it's excellent for this example

    local Vector1 = {}
    Vector1.__index = Vector1
    Vector1.new = function(X)
      return setmetatable({X = X}, Vector1)
    end
    function Vector1:__eq(Other)
      return self.X == Other.X
    end
    

    Now, we know that these hold true

    local v0 = Vector1.new(9)
    local v1 = Vector1.new(9)
    print(v0 == v1) --true
    

    and these hold false

    local v0 = Vector1.new(9)
    local v1 = Vector1.new(7)
    print(v0 == v1) --false
    

    since Vector1.new(9) == Vector1.new(9) is true, that means if we were to put it into a set, it should be a member, correct?

    Set:Add(Vector1.new(9))
    print(Set:Contains(Vector1.new(9))) --false
    

    But our naive set says that, no, Vector1.new(9) isn't a member of this set because while Vector1.new(9) == Vector1.new(9), they aren't the same objects. If you want a set that works for objects such as our Vector1 here, we can do a linear search for them.

    function Set:Contains(X)
      local Contains = self.Set[X]
      if Contains then
        return Contains
      end
      for Key in pairs(self.Set) do
        if Key == X then
          return true
        end
      end
    end
    

    It depends on what you consider equal or what you consider different.

  • Global Moderator

    @LegitimatlyMe That ruins the whole point of sets. If the value is not present then your set:Contains(x) method will perform an unsuccessful linear search for it anyway.

    There's a better solution: hashes. Compute a hash of your set elements and use that as the key. Two vectors that compare equal should return the same hash.

    Any value that is to be able to be added to a set should define a hash() method. Primitive types can be hashed by some global hash() function. This function should just fallback to the hash() method of its argument for complex objects.

Log in to reply
 

Looks like your connection to Scripting Helpers was lost, please wait while we try to reconnect.