# Most efficient key-value tracing method of a table?

``````local Data = {};
local keyHolder = {};
local dataCount = 0;

dataCount = dataCount + 1;
Data[dataCount] = dataVal;
keyHolder[dataVal] = dataCount;
end;
local function removeKey(dataVal)
-- ?
end;
``````

I have this code: I want my `Data` table to be an array, but also be able to indexable through its value.
I go about this issue by having 2 tables, the second holding the inverse key|value pair of the index.
Example:

``````t1[1] = 'hi'
t2['hi'] = 1
``````

This allows me to do `t1[t2['hi']]`.

Now, hereâ€™s the issue - when removing from the array, I could simply use `table.remove` to make the list go down by one.
But what about `t2`, which is a dictionary?
Looping through seems horribly inefficient, considering the tables can hold values of up to 10,000.
In conclusion - how would I update all the values in the dictionary, whenever the array updates, in the most efficient way possible (no looping), since table.remove makes all values above `n` go down by one itâ€™d create a domino effect?
Keep in mind Iâ€™d want it to stay as O(1) if possible.

2 Likes

__index.

``````local t = { "hi" }
setmetatable(t, { __index = function(_, key)
return table.find(t, key)
end }
print(t.hi) -- 1
``````
1 Like

Tried running your code with this;

``````local t = { "hi" }
setmetatable(t, { __index = function(_, key)
return table.find(t, key)
end })
t[2] = 'bye';
t[1] = nil;
warn(t.bye);
``````

didnâ€™t do anything.
Did I use it incorrectly?

I guess it stops working when the table no longer has an array part :\

index 2 is now part of the dictionary part when you removed `t[1]`. This worked when it had an array part.

It started working fine once I used table.remove (for obvious reasons), and although its an O(n) operation I donâ€™t think thereâ€™s a better way than this.

Iâ€™ll try using your code and check if I run into any issues, thanks!

1 Like

Canâ€™t you do the inverse of your insertion?

``````local value = table.remove(array, index)

dict[value] = nil
``````

Or, if you have a value instead of index:

``````local index = dict[value]

dict[value] = nil
table.remove(array, index)
``````

Although I also donâ€™t quite get the question. Is `table.remove` your issue? If so, you can swap the value with the last one in the array then nil the last one for a quick remove if order doesnâ€™t matter.

1 Like

Yes, but what about all the other values in the dictionary then?
theyâ€™d all be off, and I believe having a table with non-ordered keys would turn into a dictionary, which I donâ€™t want.

Iâ€™m looking for a way to update all values in the dictionary without any loops etc.
What incapaz proposed was indeed smart, but even though it utilized the C side more-so than the lua side, itâ€™s still O(n).

edit: I keep forgetting how big O notations work

To the best of my knowledge, this seems like a logical paradox:

You donâ€™t want to loop through things so you use a dictionary.

But if you want to change everything in a dictionary to match the array, you need to loop through things.

Unless there was some way for the dictionary to dynamically know which place in the array a word is, this is impossible. (And if that were possible, you wouldnâ€™t need a dictionary)

Also, why even have it be two different tables?
Why not just one?

``````t = {}
t[1] = 'hi'
t['hi'] = 1

print(t[t['hi']])
``````

now that I look at it like this, it seems kinda silly

You use a key to get an ID to get the exact same key?

Iâ€™m not sure I completely understand the use case, or maybe Iâ€™m not understanding the question.

So long as youâ€™re not changing anything visually, most modern machines should be able to easily handle looping through 10,000 things without breaking a sweat.

Yes, but then itâ€™d be O(n) - Iâ€™m trying to find a method to do so without having much impact.
If thereâ€™s no solution (probable), Iâ€™ll use incapazâ€™s method which is probably the best solution as it both allows me to use 1 table and also gives the C side all the work to do.

Also, for clarification:
I loop through 500+ objects in an array, every renderstep.
Using an array to loop through is a much better case than using a dictionary, and I believe it wouldnâ€™t just be micro-optimization.
Only problem that would offer would be to remove an object from the array, which is the reason I made this thread.

1 Like

You can use the the metod known as fast remove

``````local data = {}
local keys = {}
local dataCount = 0

local function insert(val)
dataCount = dataCount + 1
table.insert(data, val)
keys[val] = dataCount
end

local function remove(val)
if dataCount > 0 then
local index = keys[val]
local lastelem = data[dataCount]
data[index] = lastelem
table.remove(data, dataCount)
keys[lastelem] = index
keys[val] = nil
dataCount = dataCount - 1
end
end
``````

This allows us to remove in `O(1) + O(m) = O(m)` where `O(m)` is the time complexity of the hash function that indexes the `keys` table, and the index assigned to the key in the keys table is updated.

2 Likes

`table.remove` isnt an O(1) operation.

In that situation it is because weâ€™re removing the last index and no index shifting takes place. Btw I updated the solution, now it works.

Then why use `table.remove`?

The better question is why not to use it? It makes code clear and satisfies the conditions.

youre both indexing a table and calling a function, simply removing the last element directly is more efficient.

Then you can do `table[count] = nil` if you want, but still thereâ€™s no complexity difference, and maybe an unnoticeable time difference.

If I didnâ€™t care for optimization I wouldâ€™ve just used a dictionary in the first place

I donâ€™t know what are you trying to say at this point.

The only optimization that you can make is indeed what I said in my previous post but I bet that this isnâ€™t that hard for you to do and you can change table.remove to table[size] = nil so thereâ€™s no need to repeat what we have said earlier.