local a = {1, 2, 3}
local b = {1, 2, 3, 4, 5, 6}
-- I need b - a = {4, 5, 6}
I want to remove all elements from array b that are also present in array a. Looking for FASTEST solution.
-
2Do you want to remove in place or create a new table with just the missing elements?Etan Reisner– Etan Reisner2015-09-03 13:47:12 +00:00Commented Sep 3, 2015 at 13:47
-
Faster approach. There might be ~100-1000 elements in each table.user606521– user6065212015-09-03 13:51:59 +00:00Commented Sep 3, 2015 at 13:51
-
Creating a new table is likely to be much faster.Etan Reisner– Etan Reisner2015-09-03 13:57:24 +00:00Commented Sep 3, 2015 at 13:57
-
When you say "array", do you mean "sequence"? "We use the term sequence to denote a table where the set of all positive numeric keys is equal to {1..n} for some non-negative integer n, which is called the length of the sequence.". Regardless, be aware that many of the solutions assume that the inputs are sequences. Your sample output is also a sequence but if you don't need that, in-place modification could be faster.Tom Blodget– Tom Blodget2015-09-03 21:25:58 +00:00Commented Sep 3, 2015 at 21:25
Add a comment
|
3 Answers
Invert the smaller table into a hash and compare against it in a loop.
function invtab(t)
local tab = {}
for _, v in ipairs(t) do
tab[v]=true
end
return tab
end
local a = {1, 2, 3}
local b = {1, 2, 3, 4, 5, 6}
local ainv = invtab(a)
-- To get a new table with just the missing elements.
local ntab = {}
for _, v in ipairs(b) do
if not ainv[v] then
ntab[#ntab + 1] = v
end
end
-- To remove the elements in place.
for i = #b, 1, -1 do
local v = b[i]
if ainv[v] then
table.remove(b, i)
end
end
2 Comments
user606521
Wow great. I forgot to mention that each array will be a SET in fact (there won't be duplicates) - do you think it is possible to speed up the code with this assumption?
Etan Reisner
Not that I can think of. Storing the sets as hashes in the first place will help as it means you can avoid the inversion step (which costs a table iteration, table creation, and table allocation(s)).
This code copies the duplicate keys over to array c
local a = {1, 2, 3}
local b = {1, 2, 3, 4,5 ,6}
local c = {}
for k,v in ipairs(b) do
local foundkey = false
for _k,_v in ipairs(a) do
if _v == v then
foundkey = true
end
end
if foundkey then
table.insert(c,v)
end
end
Or
local a = {1, 2, 3}
local b = {1, 2, 3, 4, 5, 6}
for k,v in ipairs(b) do
local key = 0
for _k,_v in ipairs(a) do
if _v == v then
key = _k
end
end
if key ~= 0 then
table.remove(a,key )
end
end
-- Outputs a = {7}
or
local a = {1, 2, 3}
local b = {1, 2, 3, 4, 5, 6}
local c = {}
for k,v in ipairs(b) do
local foundkey = 0
for _k,_v in ipairs(a) do
if _v == v then
foundkey = _k
end
end
if foundkey == 0 then
table.insert(c,v)
end
end
a = c
-- Output a = {4, 5, 6}
Comments
you can use stack here. when just compare two indexes that are not same push into stack. stack.
4 Comments
user606521
Can't do like that, because both arrays items might not be sorted, and length of "a" might be also greater than length of "b"
Asif Mehmood
length of two arrays does't matter here.
Asif Mehmood
you just choose one array e.g we have array named A and want to remove from it which is not in B so you just sort them using any algo but if the array is large then use quick sort and then finally do as i said at first.
SuperBiasedMan
Please edit your answer to change/add details, comments are not a good place to have an answer. Also please try to ensure your solution is likely to solve the problem, don't provide guesses if you might not be able to solve the issue.