Most efficient key-value tracing method of a table?

Help and Feedback Scripting Support
#1 
local Data = {};
local keyHolder = {};
local dataCount = 0;

local function addKey(dataVal)
    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
#2

__index.

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

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?

#4

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.

#5

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
#6

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
#7

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

#8

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.

#9

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
#10

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
#12

table.remove isnt an O(1) operation.

#13

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.

#14

Then why use table.remove?

#15

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

#16

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

#17

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

#18

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

#19

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.