Browse in LUA tables

Question

I have two tables created in LUA. I want to go through if there is an equal value between the two. Something like this.

table1={5,10,30,40,50,60,40}
table2={10,30,40}
for i=1,#table1 do
  if table1[i]==table2[i] then
    print("valor igual")
  end
end

The problem is that as table 1 is larger than two, you won’t be able to go through the whole table. How can I adapt this?

Answer 1

If you have neither memory nor disk space to create an orderly copy of either table, there is no way: you need two fors:

for i=1,#table1 do
  for j=1,#table2 do
    if table1[i]==table2[j] then
      print("valor igual")
    end
  end
end

(note the difference in the indexes)

Obviously, the problem is that if you can’t afford the cost of sorting the tables, it probably implies that they are giant, and therefore the above algorithm is O(m n), which is a cost you also cannot pay, unless for some reason processing time is much cheaper than disk and/or memory.

What are you can do in this case is a probabilistic approach: you can create a Bloom filter (English), popular with the elements of one table and consult all the elements of the other table against this filter Bloom; the advantage is that this is very economical in time/memory, but you create the risk of a false positive - the algorithm can say that the tables have elements in common when they don’t (but if the algorithm says the tables nay have elements in common, it is guaranteed that this is true).

---

If you can order one of the tables, you can make a binary search of each element of the unordered table in the ordered table, which has complexity O(m log n), where n is the size of the ordered table; of course, you should whenever possible sort the larger table.

---

If you can order both the tables, you can do this:

i = 1
j = 1
while i <= #table1 and j <= #table2 do
    if table1[i] < table2[j] then
        i = i + 1
    else if table2[j] < table1[i] then
        j = j + 1
    else
        print("valor igual")
        break
    end
end

The idea is that, as the lists are ordered, if the smallest element of the first table is less than the smallest element of the second table, it will never be equal to any element of the second table, and therefore can be discarded.

If you really need to squeeze the performance of that comparison, there’s a paper by Ricardo Baeza-Yates which deals with intersection algorithms of ordered lists.

---

If the two lists are lowercase, the two fors of the beginning of this answer are the best solution - the threads that the other solutions involve will end up costing more than making all the comparisons between all the pairs of values.

Answer 2

If you can create another table, try this:

table1={5,10,30,40,50,60,40}
table2={10,30,40}

values={}
for k,v in pairs(table1) do
    values[v]=true
end
for k,v in pairs(table2) do
    if values[v] then
        print(v)
    end
end

This method takes time and memory O(m+n).

Answer 3

This mode traverses both tables. The index of the first will serve as the sorter and the index of the second will serve as the controller. The sorter counts and displays the items and the controller checks whether or not the values are equal. Of course it’s only one model out of countless.

table1={5,10,30,40,50,60,40}
table2={10,30,40}
for i=1,#table1 do
    for j=1,#table2 do
        if table1[i]==table2[j] then
            num1, num2 = table1[i], table2[j]
            print(string.format("%d e valor igual a %d",table1[i],table2[j]))
        end
    end
end

Exit:

10 e valor igual a 10
30 e valor igual a 30
40 e valor igual a 40
40 e valor igual a 40