Qual é o caminho mais rápido para comparar dois conjuntos em Java?

Eu estou tentando otimizar um pedaço de código que compara elementos da lista.

Por exemplo.

public void compare(Set firstSet, Set secondSet){ for(Record firstRecord : firstSet){ for(Record secondRecord : secondSet){ // comparing logic } } } 

Por favor, leve em consideração que o número de registros em conjuntos será alto.

obrigado

Shekhar

 firstSet.equals(secondSet) 

Isso realmente depende do que você quer fazer na lógica de comparação … ou seja, o que acontece se você encontrar um elemento em um conjunto e não no outro? Seu método tem um tipo de retorno void então eu suponho que você fará o trabalho necessário neste método.

Controle mais refinado se você precisar:

 if (!firstSet.containsAll(secondSet)) { // do something if needs be } if (!secondSet.containsAll(firstSet)) { // do something if needs be } 

Se você precisa obter os elementos que estão em um conjunto e não o outro.
EDIT: set.removeAll(otherSet) retorna um booleano, não um conjunto. Para usar removeAll (), você terá que copiar o conjunto e usá-lo.

 Set one = firstSet; Set two = secondSet one.removeAll(secondSet); two.removeAll(firstSet); 

Se o conteúdo de one e two estiverem vazios, você sabe que os dois conjuntos são iguais. Se não, então você tem os elementos que fizeram os conjuntos desiguais.

Você mencionou que o número de registros pode ser alto. Se a implementação subjacente é um HashSet então a busca de cada registro é feita no tempo O(1) , então você não pode realmente ficar muito melhor do que isso. TreeSet é O(log n) .

Se você simplesmente quer saber se os conjuntos são iguais, o método equals no AbstractSet é implementado aproximadamente como abaixo:

  public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection c = (Collection) o; if (c.size() != size()) return false; return containsAll(c); } 

Observe como ele otimiza os casos comuns em que:

  • os dois objects são os mesmos
  • o outro object não é um conjunto, e
  • os tamanhos dos dois conjuntos são diferentes.

Depois disso, containsAll(...) retornará false assim que encontrar um elemento no outro conjunto que também não esteja neste conjunto. Mas se todos os elementos estiverem presentes em ambos os conjuntos, será necessário testar todos eles.

O pior desempenho ocorre, portanto, quando os dois conjuntos são iguais, mas não os mesmos objects. Esse custo é tipicamente O(N) ou O(NlogN) dependendo da implementação this.containsAll(c) .

E você terá um desempenho próximo do pior caso se os conjuntos forem grandes e diferirem apenas em uma pequena porcentagem dos elementos.


ATUALIZAR

Se você estiver disposto a investir tempo em uma implementação personalizada, há uma abordagem que pode melhorar o caso “quase o mesmo”.

A idéia é que você precise pré-calcular e armazenar em cache um hash para todo o conjunto, de modo que você possa obter o valor atual do hashcode do conjunto em O(1) . Então você pode comparar o código hash para os dois conjuntos como uma aceleração.

Como você poderia implementar um hashcode assim? Bem, se o set hashcode foi:

  • zero para um conjunto vazio e
  • o XOR de todos os hashcodes do elemento para um conjunto não vazio,

então você pode atualizar o hashcode em cache do conjunto sempre que adicionar ou remover um elemento. Em ambos os casos, você simplesmente XOR o hashcode do elemento com o hashcode atual definido.

Obviamente, isso pressupõe que os hashcodes dos elementos sejam estáveis ​​enquanto os elementos são membros de conjuntos. Ele também assume que a function hashcode das classs do elemento fornece uma boa distribuição. Isso ocorre porque, quando os dois hashcodes definidos são os mesmos, você ainda precisa retornar à comparação O(N) de todos os elementos.


Você poderia levar essa ideia um pouco mais longe … pelo menos na teoria.

Suponha que sua class de elemento set tenha um método para retornar uma sum de verificação de criptografia para o elemento. Agora, implemente as sums de verificação do conjunto fazendo XOR nas sums de verificação retornadas para os elementos.

O que isso nos compra?

Bem, se assumirmos que nada de baixo está acontecendo, a probabilidade de que quaisquer dois elementos de conjunto desiguais tenham as mesmas sums de verificação de N-bits é 2- N . E a probabilidade de 2 conjuntos desiguais terem as mesmas sums de verificação de N bits é também 2- N . Então, minha ideia é que você pode implementar equals como:

  public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection c = (Collection) o; if (c.size() != size()) return false; return checksums.equals(c.checksums); } 

Sob as suposições acima, isso só lhe dará uma resposta errada uma vez em 2N vezes. Se você fizer N grande o suficiente (por exemplo, 512 bits), a probabilidade de uma resposta errada se torna insignificante (por exemplo, aproximadamente 10 -150 ).

O lado negativo é que calcular os checksums criptocharts dos elementos é muito caro, especialmente à medida que o número de bits aumenta. Então você realmente precisa de um mecanismo efetivo para memorizar os checksums. E isso pode ser problemático.

Existe um método no Guava Sets que pode ajudar aqui:

 public static  boolean equals(Set set1, Set set2){ return Sets.symmetricDifference(set1,set2).isEmpty(); } 

Se você estiver usando biblioteca Guava , é possível fazer:

  SetView added = Sets.difference(secondSet, firstSet); SetView removed = Sets.difference(firstSet, secondSet); 

E então faça uma conclusão baseada neles.

Existe uma solução O (N) para casos muito específicos onde:

  • os conjuntos são classificados
  • ambos classificados na mesma ordem

O código a seguir assume que ambos os conjuntos são baseados nos registros comparáveis. Um método semelhante poderia ser baseado em um Comparador.

  public class SortedSetComparitor > implements Comparator> { @Override public int compare( SortedSet arg0, SortedSet arg1 ) { Iterator otherRecords = arg1.iterator(); for (Foo thisRecord : arg0) { // Shorter sets sort first. if (!otherRecords.hasNext()) return 1; int comparison = thisRecord.compareTo(otherRecords.next()); if (comparison != 0) return comparison; } // Shorter sets sort first if (otherRecords.hasNext()) return -1; else return 0; } } 
 public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Set a = this; Set b = o; Set thedifference_a_b = new HashSet(a); thedifference_a_b.removeAll(b); if(thedifference_a_b.isEmpty() == false) return false; Set thedifference_b_a = new HashSet(b); thedifference_b_a.removeAll(a); if(thedifference_b_a.isEmpty() == false) return false; return true; } 

Eu colocaria o secondSet em um HashMap antes da comparação. Dessa forma, você reduzirá o tempo de pesquisa da segunda lista para n (1). Como isso:

 HashMap hm = new HashMap(secondSet.size()); int i = 0; for(Record secondRecord : secondSet){ hm.put(i,secondRecord); i++; } for(Record firstRecord : firstSet){ for(int i=0; i 

Eu acho que a referência de método com o método equals pode ser usada. Assumimos que o tipo de object sem sombra de dúvida possui seu próprio método de comparação. Exemplo simples e simples está aqui,

 Set set = new HashSet<>(); set.addAll(Arrays.asList("leo","bale","hanks")); Set set2 = new HashSet<>(); set2.addAll(Arrays.asList("hanks","leo","bale")); Predicate pred = set::equals; boolean result = pred.test(set2); System.out.println(result); // true