1

Caution: May be hard to understand

So let's say I have a table which needs to hold indexes that correspond to a different table holding objects. For the sake of this question, I'm going to refer to these indexes as "idxs". I would like to have it so that it's viable to remove a specific idx quickly, but also to be able to loop over all the idxs quickly as well. I want this to go as fast as possible, and I have a few options to choose from:

Note: I would say there may be anywhere from 500 - 3000 objects at maximum, which means up to that many idxs to refer to them. However, there probably won't be more than 200 idxs stored in my table at a time.

  1. I can store each idx by pushing them onto the end of the table, which makes it easy to loop over them, but it creates a problem with removing them since I have to loop through the table to find the right one and then remove it.

  2. I can make the table into a sort of set as described here (Search for an item in a Lua list) which makes it extremely fast to remove the idxs but not so much to loop over them, since I may have to loop over all the empty gaps in the table which could be up to thousands long. Also, I'm actually going to have lots of these tables holding idxs so I don't think having that many tables of that length is a great idea.

There is possibly a third solution or maybe more but I'm not sure. What would be the best thing to do in this situation? Or is this a sign that I should redesign my program entirely?

As a second note, I would like to mention that removing idxs probably happens more times each frame than when I need to loop over them.

I can give more context if needed.

Novarender
  • 47
  • 9
  • What do you mean by empty gaps in a set-like table? For instance, if you print the keys in `local set = { [1] = true, [200] = true }` with `for k in pairs(set) do print(k) end`, `1` and `200` will be printed, with no gaps. – cyclaminist Feb 01 '20 at 19:35
  • Yes, but isn't there wide gaps of nil space in between them? Does the for loop not at least check if the current index is nil? I imagine it still has to at least *loop* over the gap, regardless of if it executes the rest of the code. – Novarender Feb 01 '20 at 19:39
  • No, there are no gaps. The iterator triplet returned by `pairs(set)` goes over all keys in the table (in an undefined order) and `nil` is not a valid key. `nil` is returned when the iteration is over and it stops the loop so `k` inside the loop never is `nil`. Try creating a set-like table with widely spaced integer keys and printing them with the code above and you'll see that `nil` is never printed. – cyclaminist Feb 01 '20 at 19:44
  • Ok. So... Is it both fast and efficient to have it be a set, then? Would factors make this more or less efficient such as how many idxs are being stored or how many total sets I have? – Novarender Feb 01 '20 at 19:48
  • A closely-spaced array-like table `{ 1, 200 }` *can* use less memory than the corresponding set-like table `{ [1] = true, [200] = true }` because tables use an array part and a hash part and the array part is more memory-efficient and values for integer keys can be placed there, but it's an implementation detail and not a hard rule. I don't know which is faster to iterate over, probably about the same. I simply use whichever one is most natural. For a set of unique values, I use a set-like table. – cyclaminist Feb 01 '20 at 20:10
  • Ok, thanks! I suppose this question is solved then. – Novarender Feb 01 '20 at 20:13
  • open-addressing, is what you are looking for, I guess. – Eugene Feb 02 '20 at 02:26
  • Eugene, I'll look into that. – Novarender Feb 03 '20 at 14:53

0 Answers0