Lua 比较两个表值无顺序

Question

我想知道是否有更快的方法来检查两个表是否相等（键中没有顺序）。

这是我的解决方案

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

Answer 1

是的，有更快的方法。您的方法目前是 O(n²)，因为它必须将每个元素与其他元素进行比较。一种方法是先对数组进行排序。另一种方法是使用散列部分构建查找 table ("set")。如果假定散列访问需要摊销常数时间，这应该运行在 O(n) 时间内——明显更快。它将占用 O(n) 额外的内存，但保持传递的 tables 完好无损；要使用排序执行相同操作，您必须先创建一个副本，然后对其进行排序。

散列方法如下所示（并且也适用于像 tables 这样的值，这些值通过引用进行比较并且不能排序，除非设置了 metatable 或自定义比较器提供功能）：

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

为了完整起见，这里有一个使用排序的简单实现：

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

这应该在 O(n log n) 中大致运行（性能由排序算法决定，通常是快速排序，它的平均值为运行宁时间).

Lua 比较两个表值无顺序

Lua Compare two Tables values No Order

performance

lua

lua-table