Remove elements [1] vs remove elements [#elements]

Place to post guides, observations, things related to modding that are not mods themselves.
Post Reply
User avatar
darkfrei
Smart Inserter
Smart Inserter
Posts: 2903
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Remove elements [1] vs remove elements [#elements]

Post by darkfrei »

Hi all!

Did you notice that the command table.remove (elements, 1) (the first element) needs much more time than table.remove (elements, #elements) (the last element)? Why it needs more processing time?

eduran
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by eduran »

table.remove is used to remove an entry from an array-like table without leaving a gap.

Code: Select all

t = {'a', 'b', 'c', 'd'} -- same as {[1] = 'a', [2] = 'b', ...}
table.remove(t, 1) -- removes 'a' and moves every following entry down by one
for k, v in pairs(t) do
  game.print(k .. '=' .. v)
end
-- prints 1=b, 2=c, 3=d
If you remove the last element that is all table.remove has to do. If you remove the first one all of the following elements have to be shifted.

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3699
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by DaveMcW »

This is a well known problem in computer science. Sometimes it is solved by replacing the array with a fancy data structure (like lua's associative table), but the fastest way is to prioritize removing elements from the end of the array.

User avatar
Therenas
Factorio Staff
Factorio Staff
Posts: 232
Joined: Tue Dec 11, 2018 2:10 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by Therenas »

Also, if you don't need the sequential indexing of the table, you can just do elements[n] = nil, much faster.

User avatar
darkfrei
Smart Inserter
Smart Inserter
Posts: 2903
Joined: Thu Nov 20, 2014 11:11 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by darkfrei »

Therenas wrote:
Tue May 28, 2019 7:56 pm
Also, if you don't need the sequential indexing of the table, you can just do elements[n] = nil, much faster.
I'm using only one element per game tick and the order is not important. But on the next tick I need the next element and it must be some

Code: Select all

function get_first_element (elements)
  for i, element in pairs (elements) do
    local holder = table.deepcopy (element)
    elements[i] = nil
    return holder
  end
end

User avatar
mexmer
Filter Inserter
Filter Inserter
Posts: 869
Joined: Wed Aug 03, 2016 2:00 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by mexmer »

Setting table element to nil is bad practice, unless you are only doing it for your own functions/data and properly handle it.

For example it breaks #tablename functionalitity for for cycles. And there is other minor stuff.

While it’s fast it should never be used on shared data

eduran
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by eduran »

darkfrei wrote:
Tue May 28, 2019 8:53 pm
I'm using only one element per game tick and the order is not important. But on the next tick I need the next element and it must be some

Code: Select all

function get_first_element (elements)
  for i, element in pairs (elements) do
    local holder = table.deepcopy (element)
    elements[i] = nil
    return holder
  end
end
You don't need to copy the table, just doing "local holder = element" works. Even simpler:

Code: Select all

local next_key, next_value = next(elements)
elements[next_key] = nil
-- do something with next_key and next_value 
mexmer wrote:
Tue May 28, 2019 9:05 pm
Setting table element to nil is bad practice, unless you are only doing it for your own functions/data and properly handle it.

For example it breaks #tablename functionalitity for for cycles. And there is other minor stuff.

While it’s fast it should never be used on shared data
Setting table elements to nil is actually good practice in Lua. table.remove() should only be used when you need a sorted, array-like table without gaps. And what shared data are we talking about? During the data stage, you obviously should not delete or modify tables others might rely on. But during the control stage, every mod has its own Lua instance and nothing is shared.

User avatar
mexmer
Filter Inserter
Filter Inserter
Posts: 869
Joined: Wed Aug 03, 2016 2:00 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by mexmer »

eduran wrote:
Wed May 29, 2019 6:34 am
darkfrei wrote:
Tue May 28, 2019 8:53 pm
I'm using only one element per game tick and the order is not important. But on the next tick I need the next element and it must be some

Code: Select all

function get_first_element (elements)
  for i, element in pairs (elements) do
    local holder = table.deepcopy (element)
    elements[i] = nil
    return holder
  end
end
You don't need to copy the table, just doing "local holder = element" works. Even simpler:

Code: Select all

local next_key, next_value = next(elements)
elements[next_key] = nil
-- do something with next_key and next_value 
mexmer wrote:
Tue May 28, 2019 9:05 pm
Setting table element to nil is bad practice, unless you are only doing it for your own functions/data and properly handle it.

For example it breaks #tablename functionalitity for for cycles. And there is other minor stuff.

While it’s fast it should never be used on shared data
Setting table elements to nil is actually good practice in Lua. table.remove() should only be used when you need a sorted, array-like table without gaps. And what shared data are we talking about? During the data stage, you obviously should not delete or modify tables others might rely on. But during the control stage, every mod has its own Lua instance and nothing is shared.
i emphasized exact part, where people do that repeatedly, then complaining about broken mod compatibility.
that's why i say ... it's bad practice.

it's good practice if you are only one working with data, but when we talking about factorio mods, that is not the case.

eduran
Filter Inserter
Filter Inserter
Posts: 344
Joined: Fri May 09, 2014 2:52 pm
Contact:

Re: Remove elements [1] vs remove elements [#elements]

Post by eduran »

The case darkfrei is asking about is a prime example of when NOT to use table.remove(): it is not needed, it is slower than setting the element to nil (significantly so on large tables, which triggered him to post here) and it is used in on_tick. There is no shared data at all during the control stage that he would need to worry about. No other mod can see the table in question.

Shared data during the data.lua stage is either provided by Factorio' Lua engine (data.raw and various tables with functions) or by mods (some form of API). It does not matter if I delete that data with table.remove() or by setting it to nil or overwrite it with something else entirely. It is gone either way and will cause trouble to any mods trying to access it afterwards.

Post Reply

Return to “Modding discussion”