Como determinar diferenças em duas listas de dados

Question

Este é um exercício para os caras do CS para brilhar com a teoria.

Imagine que você tem 2 recipientes com elementos. Pastas, URLs, arquivos, cordas, isso realmente não importa.

O que é o algoritmo AN para calcular o agregado e o removido?

Aviso :. Se existem muitas maneiras de resolver este problema, por favor envie um por resposta para que possa ser analisado e votado up

Editar : Todas as respostas resolver o assunto com 4 recipientes. É possível utilizar apenas a inicial 2?

Answer 1

Assumindo que você tem duas listas de itens exclusivos, e a ordem não importa, você pode pensar em ambos como conjuntos em vez de listas

Se você pensar em um diagrama de Venn, com a lista A como um círculo e lista B como o outro, então a interseção desses dois é a piscina constante.

Remova todos os elementos nesta intersecção de ambos A e B, e nada e deixado em uma foi excluída, enquanto qualquer coisa à esquerda na B foi adicionada.

Assim, iterate através de uma procura cada item B. Se você encontrá-lo, remova-a ambos A e B

Em seguida, A é uma lista de coisas que foram excluídos, e B é uma lista de coisas que foram adicionados

Eu acho que ...

[editar] Ok, com a nova restrição "apenas 2 container", o mesmo ainda se mantém:

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

Em seguida, você não está construindo uma nova lista, ou destruir seus velhos ... mas vai demorar mais tempo como com o exemplo anterior, você poderia apenas loop sobre a lista mais curta e remover os elementos do tempo. Aqui você precisa fazer ambas as listas

Um eu diria a minha primeira solução não usar 4 recipientes, ele só destruiu dois; -)

Answer 2

Eu não tenho feito isso em um tempo, mas eu acredito que o algoritmo é assim ...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

No que diz respeito à relação da lista direito a lista à esquerda, exclusões contém itens removidos e acrescenta agora contém novos itens.

Answer 3

O que disse Joe. E, se as listas são grandes demais para caber na memória, use um arquivo externo de classificação de utilidade ou uma espécie de mesclagem.

Answer 4

Falta de informação: Como você define adicionado / removido? Por exemplo. Se as listas (A e B) mostram o mesmo diretório no Servidor A e Servidor B, que está em sincronia. Se eu agora esperar por 10 dias, gerar as listas novamente e compará-los, como posso saber se algo foi removida? Não posso. Eu só posso dizer existem arquivos em um servidor não encontrado no servidor B e / ou vice-versa. Se isso é porque um arquivo foi adicionado ao Servidor A (assim, o arquivo não for encontrado no B) ou um arquivo foi excluído no servidor B (assim, o arquivo não for encontrado no B mais ) é algo que não pode determinar por ter apenas uma lista de nomes de arquivo.

Para a solução Sugiro, vou simplesmente assumir que você tem uma lista chamada OLD e uma lista nomeada NOVO. Tudo encontrado na idade, mas não no Novo foi removido. Tudo encontrado na NOVO, mas não em OLD foi adicionado (por exemplo, o conteúdo do mesmo diretório no mesmo servidor, no entanto listas foram criadas em datas diferentes).

Além disso vou assumir não há duplicatas. Isso significa que cada item de cada lista é único no sentido de: Se eu comparar este item para qualquer outro item na lista (não importa como isso funciona comparar), eu posso sempre dizer o item é ou menor ou maior que o que eu estou comparando-a, mas nunca iguais. Por exemplo. quando se lida com cordas, posso compará-los lexicographically e a mesma cadeia é nunca duas vezes na lista.

Nesse caso, o mais simples (não necessariamente melhor solução, embora) é:

1. Classificar as listas VELHAS. Por exemplo. Se a lista é composta por cordas, classificá-los em ordem alfabética. Classificando é necessário, porque isso significa que eu posso usar a pesquisa binária para encontrar rapidamente um objeto na lista, admitindo que existe lá (ou para determinar rapidamente, ela não existe na lista de todo). Se a lista é indiferenciado, encontrar o objeto tem uma complexidade de O (n) (Eu preciso olhar para cada item na lista). Se a lista é ordenada, a complexidade é apenas O (log n), como após cada tentativa para combinar um item na lista Eu sempre pode excluir 50% dos itens na lista não sendo um jogo. Mesmo que a lista tem 100 itens, encontrar um item (ou detecção de que o item não está na lista) leva, no máximo, 7 testes (ou é 8? De qualquer forma, muito menos do que 100). A nova lista não tem de ser resolvida.

2. Agora vamos executar a eliminação lista. Para cada item na lista do New, tente encontrar este item na lista antiga (utilizando busca binária). Se o item for encontrado, remover este item da lista OLD e também removê-lo da lista NOVO. Isso também significa que as listas ficam menores do mais os avanços de eliminação e, assim, as pesquisas se tornará mais e mais rápido. Desde remover um item da lista não tem efeito sobre a ordem de classificação correta das listas, não há necessidade de sempre recorrer a lista OLD durante a fase de eliminação.

3. No final da eliminação, ambas as listas pode estar vazio, caso em que eles eram iguais. Se eles não estiverem vazios, todos os itens ainda na lista OLD são itens ausentes na lista NEW (caso contrário, eles tinham removido), portanto, estes são os itens removidos . Todos os itens ainda na lista do New são itens que não estavam na lista antiga (mais uma vez, que os tinha removido de outra forma), portanto, estes são os itens adicionados .

Answer 5

Os objetos na lista "único"? Neste caso, eu iria primeiro construir dois mapas (HashMaps) e, então, verificar as listas e pesquisar todos os objetos nos mapas.

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

Desculpem a meta-linguagem horrível mistura de Ruby e Java :-P

No final <> fortes removedElements conterá os elementos pertencentes a lista1, mas não para lista2, e <> fortes addedElements fortes irá conter os elementos pertencentes a lista2.

O custo de toda a operação é O (4 * N) uma vez que a pesquisa no mapa / dicionário pode ser considerada constante. Por outro lado linear / binário pesquisar cada um dos elementos das listas fará que O (n ^ 2).

Editar : em um segundo pensou se movendo a última verificação para o segundo loop que você pode remover um dos loops ... mas isso é feio ...:)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}