Lua比较两个表的值（不考虑键的顺序）

2022-3-5 0:34:24
收藏：0
阅读：3530
评论：1

我在想是否有一种更快的方法来检查两个表是否相等（不考虑键的顺序）。以下是我的解决方案

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

原文链接 https://stackoverflow.com/questions/71357936

点赞
stackoverflow用户7185318
stackoverflow用户7185318

是的，有更快的方法。你现在的方法是O(n²)，因为它必须将每个元素与其他元素进行比较。一种方法是先对数组进行排序。另一种方法是使用哈希表创建查找表("set")。如果哈希访问被假定为摊销常数时间，那么这应该以O(n)的时间运行——显着更快。它将需要O(n)额外的内存，但是会保留传递的数组不变；如果使用排序来做同样的事情，你必须先创建一个副本，然后再对其进行排序。

哈希表的方法如下(也适用于像table这样的值，它们是按引用比较的，除非设置metatable或提供自定义比较器函数，否则无法排序):

function TableCompareNoOrder(table1, table2)
    if #table1 ~= #table2 then return false end
    -- 如果table1 == table2，则在此处考虑早期的"return true"
    local t1_counts = {}
    -- 检查相同的元素出现相同的次数
    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
    -- 懒惰的实现: 对两个表的副本进行排序，而不是使用二分查找。需要两倍的内存。
    local t1_sorted = {table.unpack(table1)} --简单复制表的方法，受堆栈大小限制
    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)的时间复杂度(性能由排序算法决定，通常是快速排序，其平均运行时间为O(n log n))。

2022-03-05 13:13:15

作者:

stackoverflow用户14772327

stackoverflow用户14772327
推荐文章