If you have neither memory nor disk space to create an orderly copy of either table, there is no way: you need two for
s:
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 for
s 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.
Are tables necessarily integer tables? Can you guarantee that they are sorted? You can pay the cost of ordering them if they are not ordered?
– user25930
This is an example, I am even using with strings. Tables cannot be ordered because they are of the cool as they are inserted.
– akm
Why do you want to know this? What real problem do you want to solve with this step?
– lhf