Lua Compare two Tables values No Order-CodePudding

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

CodePudding user response：

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).