# [SOLVED] Lua Compare two Tables values No Order

## Issue

I wonder if there is a faster way to check if two tables are equal (without order in the keys).

This is my solution

``````function TableCompareNoOrder(table1,table2)
if #table1 ~= #table2 then return false end
local equal = false
for key, item in pairs(table1) do
for key2, item2 in pairs(table2) do
if item == item2 then equal = true end
end
if equal == false then return false end
end
local equal = false
for key, item in pairs(table2) do
for key2, item2 in pairs(table1) do
if item == item2 then equal = true end
end
if equal == false then return false end
end

return equal
end

a = {1,2,3,0}
b = {2,3,1,0}
print(TableCompareNoOrder(a,b))
``````

## Solution

Yes, there are faster ways. Your approach is currently O(n²) as it has to compare each element with each other element. One way is to sort the arrays first. Another one would be to build a lookup table ("set") using the hash part. If hash access is assumed to take amortized constant time, this should run in O(n) time – significantly faster. It will take O(n) additional memory but leaves the passed tables intact; to do the same using sorting you’d have to first create a copy, then sort it.

The hash approach looks like the following (and also works for values like tables which are compared by reference and can’t be sorted unless a metatable is set or a custom comparator function is supplied):

``````function TableCompareNoOrder(table1, table2)
if #table1 ~= #table2 then return false end
-- Consider an early "return true" if table1 == table2 here
local t1_counts = {}
-- Check if the same elements occur the same number of times
for _, v1 in ipairs(table1) do
t1_counts[v1] = (t1_counts[v1] or 0) + 1
end
for _, v2 in ipairs(table2) do
local count = t1_counts[v2] or 0
if count == 0 then return false end
t1_counts[v2] = count - 1
end
return true
end
``````

For the sake of completeness, here’s a simple implementation using sorting:

``````function TableCompareNoOrder(table1, table2)
if #table1 ~= #table2 then return false end
-- Lazy implementation: Sort copies of both tables instead of using a binary search. Takes twice as much memory.
local t1_sorted = {table.unpack(table1)} -- simple way to copy the table, limited by stack size
table.sort(t1_sorted)
local t2_sorted = {table.unpack(table2)}
table.sort(t2_sorted)
for i, v1 in ipairs(t1_sorted) do
if t2_sorted[i] ~= v1 then return false end
end
return true
end
``````

This should roughly run in O(n log n) (performance is determined by the sorting algorithm, usually quicksort which has this as it’s average running time).