Separate numerically keyed table to get an order of keyed table?

Posted by Rivius on Mon 31 Oct 2011 06:46 PM — 5 posts, 22,776 views.

Rivius Mon 31 Oct 2011 06:46 PM #0

For a particular task I am trying to accomplish, I require the ability to quickly check for the existence of a variable using table[variable_name] for quick confirmation that it exists. I use this pretty frequently. Recently, however, I've learned that if I kept tabs on the order of this table, I would be able to accomplish another task. The thing is, the keys can be deleted after they have existed for a set amount of time, or if I clear them before then (I use timers for this).

The problem this creates is, if I delete some keys out of order, to delete them in the corresponding numerically keyed table, I would need to loop through it, compare the names, and table.remove.

I just want to reduce the performance cost, since I do this fairly frequently.

TO illustrate in code what I mean:

I would create a key and do:


table["dog"] = true
table.insert(reference_table, "dog")

but when I'm reading to clear it, I have to do:


table["dog"] = nil
for n,i in ipairs(reference_table) do
   if i == "dog" then
       table.remove(reference_table, n)
   end
end

Is there any way I can try to maintain a semblance of order and easily add and remove entries without having to resort to looping through the ordered table and picking off entries? I admit I know little about lua and performance, but I imagine looping through like this as often as I may need to call this will get a little costly.

Twisol USA Mon 31 Oct 2011 07:15 PM #1

The most optimal thing I can think of looks like this:


-- adding
table.insert(reference_table, "dog")
table['dog'] = #reference_table

-- removing
var idx = table["dog"]
table.remove(reference_table, idx)
for i=idx, #reference_table do
  var k = reference_table[i]
  table[k] = table[k] - 1
end
table["dog"] = nil

I'm storing the current index of each item as its key, instead of just using true. That lets me remove the item directly. The new issue here is that table.remove moves later items up by one, so those indices have now changed. I use the stored index for the removed element and go over all of the later ones - but only the later ones - and update their index in the main table.

In the end, there's still some looping, but the optimization is that I only go over the items that are known to need changing.

In your case, you're looking for the element, then shuffling all of the later ones back by one (through table.remove). So you're going over each item in the list, guaranteed, every time. (Actually it's worse than that, because you're not using 'break' as soon as you find what you were looking for.)

[EDIT]: Actually, mine goes over the latter part of the list twice when it doesn't necessarily need to. First when removing (it shuffles all items backwards), and again when updating the main list. And #reference_table goes over the whole thing to find out the length... Well, a more accurate version looks like this:

var idx = table["dog"]
while true do
  idx = idx + 1
  var k = reference_table[idx]
  
  -- end of the list
  if k == nil
    break
  end
  
  -- shuffle items backwards
  reference_table[i-1] = k
  
  -- update index in main table
  table[k] = table[k] - 1
end

reference_table[idx-1] = nil
table["dog"] = nil

Untested, but it's just merging those three bits together. Finding the end of the list, moving items back, and updating in the main table - all in one single loop.

Just goes to show, though: my original attempt actually performed worse than your original code, even with the missing break. If you added that 'break' in it really wouldn't be an awfully inefficient solution.

Rivius Mon 31 Oct 2011 08:36 PM #2

Thanks, Twisol. A slight problem is that I assign these variables to things other than "true". Someone suggested I follow your solution and take a third table. Overall it feels a bit unwieldy, but there really seems to be no better way.

I'll try to see how I use your suggestion, and thanks so much again :)

Nick Gammon Australia Forum Administrator Tue 01 Nov 2011 12:31 AM #3

Maybe use SQLite3? You could have a database table with multiple keys (numeric key, alpha key). For speed you can make an in-memory table (not a disk one).

Failing that, a bit depends how many entries you have. Reconstructing, or searching, a medium size table wouldn't take too long.

Twisol USA Tue 01 Nov 2011 02:18 AM #4

Rivius said:
Thanks, Twisol. A slight problem is that I assign these variables to things other than "true". Someone suggested I follow your solution and take a third table. Overall it feels a bit unwieldy, but there really seems to be no better way.

I'll try to see how I use your suggestion, and thanks so much again :)

Well, there's an alternative that merges the two original tables together, if the items are always strings. So you can keep it down to two tables if you have one for ordering/existence (which is the two original tables) and one for the actual data.

I don't have much time (Halloween, hooray), but here's the idea. Instead of this:

tbl["foo"] = (index)
reference_table[(index)] = "foo"

Use:

table[(index)] = "foo"
table["foo"] = (index)

Since the items themselves are always strings, they'll never clash with the integer indices. So this easily keeps the idea of existence + ordering kept in a single table, and you can use another table for holding the actual data associated with each item.