我是否可以仅从两个表格中提取相同的值?

在代码的清晰度或效率方面,找到两个Lua编号表格的“交集”的最佳方法是什么,即包含仅存在于两个表格中的值的表格?

例如,我有

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

由于3、4和5都在ab中找到,我想要{3,4,5}

点赞
用户10953006
用户10953006

你需要在其中一个表格上进行迭代,并且如果你在另一个表格找到对应的值,就输出它。在我的电脑上,以下代码返回{3,4,5},它实际上实现了两个集合的交集

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

function Contains (Array, Item)

  local Found = false
  local Index = 1

  while ((not Found) and (Index <= #Array)) do
    if Array[Index] == Item then
      Found = true
    else
      Index = Index + 1
    end
  end

  return Found
end

function Intersects (Ta, Tb)

  local Result = { }
  local Index

  for Index = 1, #Tb do
    if Contains(Ta, Tb[Index]) then
      Result[#Result + 1] = Tb[Index]
    end
  end

  return Result
end

Result = Intersects(a, b)

-- 打印结果
local Index, Value

for Index, Value in ipairs(Result) do
  print(Value)
end
2020-10-10 06:00:27
用户6632736
用户6632736

我建议采用基于_set_的稍微不同的方法。这种方法的性能不一定会提高,但代码会更清晰,更易懂,也更容易扩展。

在Lua中,可将_set_作为一个表来轻松实现,其中键是集合项,值是true。因此,要检查集合中是否存在项,只需使用if set[item] then即可。

我将提供三个代码变体。第一个变体清晰地实现了交集运算符,但必须将结果集转换回索引的Lua表。第二个变体立即将两个集合的交集返回为一个数组。第三个变体是第一个和第二个变体之间的妥协。

请注意,两者都没有包含关于ab的嵌套循环:它们的操作复杂度是_O(a + b)_而不是_O(ab)_。

第一个变体:

local insert, sort = table.insert, table.sort -- 为了性能本地化。

local a = {1,2,3,4,5}
local b = {3,4,5,6,7}

local function toset (tbl)
    local set = {}
    for _, value in ipairs (tbl) do
        set [value] = true
    end
    return set
end

local function intersect (set1, set2)
    local intersection = {}
    for item, _ in pairs (set1) do
        if set2 [item] then
            intersection [item] = true
        end
    end
    return intersection
end

local function toarray (set)
    local array = {}
    for item, _ in pairs (set) do
        insert (array, item)
    end
    sort (array)    -- 因为你希望得到{3,4,5}而不是{4,5,3}
    return array
end

-- 幸运的是,table.concat不需要前面的tostring:
print ('{' .. table.concat (toarray (intersect (toset (a), toset (b))), ', ') .. '}')

第二个变体:

local insert, sort = table.insert, table.sort -- 为了性能本地化。

local a = {1,2,3,4,5}
local b = {3,4,5,6,7}

local function toset (tbl)
    local set = {}
    for _, value in ipairs (tbl) do
        set [value] = true
    end
    return set
end

local function intersect_and_to_array (set1, set2)
    local array = {}
    for item, _ in pairs (set1) do
        if set2 [item] then
            insert (array, item)
        end
    end
    sort (array)    -- 因为你希望得到{3,4,5}而不是{4,5,3}
    return array
end

-- 幸运的是,table.concat不需要前面的tostring:
print ('{' .. table.concat (intersect_and_to_array (toset (a), toset (b)), ', ') .. '}')

第三个变体:

local insert = table.insert -- 为了性能本地化。

local a = {1,2,3,4,5}
local b = {3,4,5,6,7}

local function toset (tbl)
    local set = {}
    for _, value in ipairs (tbl) do
        set [value] = true
    end
    return set
end

local function filter_array_through_set (array, set)
    local filtered = {}
    for _, value in ipairs (array) do
        if set [value] then
            insert (filtered, value)
        end
    end
    return filtered -- 数组的顺序得到保留。
end

-- 幸运的是,table.concat不需要前面的tostring:
print ('{' .. table.concat (filter_array_through_set (a, toset (b)), ', ') .. '}')
2020-10-10 07:29:25