3

Tenho duas tabelas criadas em LUA. Quero percorrer se existe um valor igual entre as duas. Algo deste genero.

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

O problema é que como a tabela 1 é maior que a dois, não vai conseguir percorrer a tabela toda. Como posso adaptar isso?

3
  • As tabelas são necessariamente tabelas de inteiros? Você tem como garantir que elas estão ordenadas? Você pode pagar o custo de ordená-las se elas não estiverem ordenadas?
    – user25930
    Commented 4/06/2015 às 23:09
  • Isto é um exemplo, até estou a utilisar com strings. As tabelas não podem ser ordenadas porque são da maneiro como são inseridas.
    – akm
    Commented 4/06/2015 às 23:12
  • Por que você quer saber isso? Qual o problema real que você quer resolver com esse passo?
    – lhf
    Commented 10/06/2015 às 17:19

3 Respostas 3

2

Se você não tem espaço nem em memória nem em disco para criar uma cópia ordenada de nenhuma das duas tabelas, não tem jeito: você precisa de dois fors:

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

(note a diferença nos índices)

Obviamente, o problema é que se você não pode pagar o custo de ordenar as tabelas, isso provavelmente implica que elas são gigantes, e portanto o algoritmo acima é O(m n), que é um custo que você também não pode pagar, a menos que por algum motivo tempo de processamento seja muito mais barato que disco e/ou memória.

O que você pode fazer nesse caso é uma abordagem probabilística: você pode criar um bloom filter (inglês), popular com os elementos de uma tabela e consultar todos os elementos da outra tabela contra esse bloom filter; a vantagem é que isso é muito econômico em tempo/memória, mas você cria o risco de um falso positivo — o algoritmo pode dizer que as tabelas têm elementos em comum quando elas não tem (mas se o algoritmo disser que as tabelas não têm elementos em comum, é garantido que isso é verdade).


Se você pode ordenar uma das tabelas, você pode fazer uma busca binária de cada elemento da tabela não-ordenada na tabela ordenada, o que tem complexidade O(m log n), onde n é o tamanho da tabela ordenada; naturalmente, você deve sempre que possível, ordenar a tabela maior.


Se você pode ordenar ambas as tabelas, você pode fazer isso:

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

A ideia é que, como as listas são ordenadas, se o menor elemento da primeira tabela for menor que o menor elemento da segunda tabela, ele nunca vai ser igual a nenhum elemento da segunda tabela, e portanto pode ser descartado.

Se você realmente precisar espremer a performance dessa comparação, tem um paper do Ricardo Baeza-Yates que trata de algoritmos de interseção de listas ordenadas.


Se as duas listas forem minúsculas, os dois fors do começo dessa resposta são a melhor solução — as firulas que as outras soluções envolvem vão acabar custando mais do que fazer todas as comparações entre todos os pares de valores.

2

Se você pode criar uma outra tabela, experimente isso:

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

Esse método gasta tempo e memória O(m+n).

1
  • (e provavelmente vai rodar mais rápido que a comparação de listas ordenadas, já que a maioria das comparações é de inteiros e não de strings)
    – user25930
    Commented 12/06/2015 às 16:09
1

Este modo percorre as duas tabelas. O índice da primeira servirá como ordenador e o índice da segunda servirá como controlador. O ordenador conta e apresenta os itens e o controlador verifica se os valores são ou não são iguais. Claro que é somente um modelo dentre inúmeros.

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

Saída:

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .