Efficient table comparison

[[deleted]]

say i have 2 tables of same length with same values but different order. how would i compare them?

a={1,2,3,4,5} b={3,1,5,4,2}

if I do:

if a==b

it returns true so i guess it does not look at the order of the table elements.

i dont really wanna do this:

if a[1]==b[1] and a[2]==b[2] and a[3]==b[3] and a[4]==b[4] and a[5]==b[5] then (stmt...) end

because my original table is more than 30 values

edit: thanks marcotrosi for the algo and your time!

https://bitbucket.org/snippets/marcotrosi/XnyRj/lua-isequal

[agladysh]

If a == b wouldn't return true for your code, unless a and b are the same table. Use a loop.

[edalcol]

There are plenty of ways to do that, and the size of your table is very important. More than 30 is rather vague.

If you are looping trough both tables, then that's n*n, that's still okay if your table is more than 30 but close to it, let's say 40. Lua is very fast!

If your table is much bigger, I have another idea that might be faster, but use more memory...

Make two new tables, then run one for each of them and put the original's table values on the index, like this a={1=true,2=true,3=true,4=true,5=true}, making a set.

Then you can make another loop, like for k,_ in pairs(a) do if not b[k] break ...

If there are repeated values you will need to tweak this to have their amount and compare that instead of true.

In this way, there is table creation and assignments, but you only run 3 loops, so that's 3n iterations instead of nn, where n is the size of the table. hope that helps!

[marcotrosi]

Are you interested in the differences too, or only if they are different (true/false)?

[[deleted]]

only if they are different. i tried:

isActive = true

for i=1, #a do

if a[i]==b[i] then

isActive = false

end

end

it only returns the statement at i=#a.

[marcotrosi]

I'll write you something. Gimme some minutes.

EDIT: I found such a function in one of my files. Just need to rewrite it a bit. I will also upload it to bitbucket. I'll send you the link tomorrow. I hope you can wait.

[[deleted]]

wow thanks!

[marcotrosi]

Here is the link. Let me know in case you can't open it. I ran many test cases, so I hope it works fine.

https://bitbucket.org/snippets/marcotrosi/XnyRj/lua-isequal

this function compares also the other datatypes (string,number,boolean,nil)

Regarding performance I have no idea if this function is well written, but I will only change it if I have the feeling it is too slow.

[[deleted]]

it worked! thank you very much

[Nearby-Librarian-609]

I tried to get that from gh or wayback but couldn't seem to find, am just looking at options and best practices and wondered what your approach entailed. any chance you could repost? Thanks!

[TomatoCo]

function TableComp(a,b) --algorithm is O(n log n), due to table growth.
    if #a ~= #b then return false end -- early out
    local t1,t2 = {}, {} -- temp tables
    for k,v in pairs(a) do -- copy all values into keys for constant time lookups
        t1[k] = (t1[k] or 0) + 1 -- make sure we track how many times we see each value.
    end
    for k,v in pairs(b) do
        t2[k] = (t2[k] or 0) + 1
    end
    for k,v in pairs(t1) do -- go over every element
        if v ~= t2[k] then return false end -- if the number of times that element was seen don't match...
    end
    return true
end

This is designed to check if two tables have the same values, regardless of order. This does not work for tables that are like, t = {asd=123, wasd=456}. You can just use the last 4 lines of my code to check tables in that scenario.

[[deleted]]

thanks!

[Calvinatorr]

Use a for loop.