java - repetidos - Encontrar duplicados en una lista ignorando un campo

eliminar elementos repetidos de una lista java

Question

Tengo una List de personas y quiero encontrar entradas duplicadas, consiguiendo todos los campos, excepto el id . Entonces usando el método equals() (y en consecuencia List.contains() ), porque toman en cuenta id .

public class Person {
private String firstname, lastname;
private int age;
private long id;
}

La modificación de equals() y hashCode() -methods para ignorar el campo id no es una opción porque otras partes del código se basan en esto.

¿Cuál es la forma más eficiente en Java para ordenar los duplicados si quiero ignorar el campo de id ?

Answer 1

Cree un Comparator<Person> para implementar su ordenamiento de clave natural y luego use una deduplicación basada en búsqueda binaria. TreeSet te dará esta habilidad de la caja.

Tenga en cuenta que el Comparator<T>.compare(a, b) debe cumplir con los requisitos habituales de antisimetría, transitividad, coherencia y reflexividad o que el orden de búsqueda binaria fallará. También debe hacer que sea nulo-aware (por ejemplo, si el primer campo de uno, otro o ambos son nulos).

Un comparador de claves naturales simple para su clase Persona es el siguiente (es una clase de miembro estática ya que no se ha mostrado si tiene accesadores para cada campo).

public class Person {
public static class NkComparator implements Comparator<Person>
{
public int compare(Person p1, Person p2)
{
if (p1 == null || p2 == null) throw new NullPointerException();
if (p1 == p2) return 0;
int i = nullSafeCompareTo(p1.firstname, p2.firstname);
if (i != 0) return i;
i = nullSafeCompareTo(p1.lastname, p2.lastname);
if (i != 0) return i;
return p1.age - p2.age;
}
private static int nullSafeCompareTo(String s1, String s2)
{
return (s1 == null)
? (s2 == null) ? 0 : -1
: (s2 == null) ? 1 : s1.compareTo(s2);
}
}
private String firstname, lastname;
private int age;
private long id;
}

Luego puede usarlo para generar una lista única. Use el método add que devuelve true si y solo si el elemento no existía en el conjunto:

List<Person> newList = new ArrayList<Person>();
TreeSet<Person> nkIndex = new TreeSet<Person>(new Person.NkComparator());
for (Person p : originalList)
if (nkIndex.add(p)) newList.add(p); // to generate a unique list

o cambie la línea final de esta línea para dar salida a los duplicados en su lugar

 if (nkIndex.add(p)) newList.add(p); 

Hagas lo que hagas, no uses remove en tu lista original mientras lo estás enumerando, es por eso que estos métodos agregan tus elementos únicos a una nueva lista.

Si solo está interesado en una lista única, y quiere usar la menor cantidad de líneas posible:

TreeSet<Person> set = new TreeSet<Person>(new Person.NkComparator());
set.addAll(originalList);
List<Person> newList = new ArrayList<Person>(set);

Answer 2

Puede usar Java HashMap usando pares <K,V> . Map<K,V> map = new HashMap<K,V>() . Además, alguna forma de implementación de Comparator para ir con. Si comprueba con los métodos containsKey o containsValue y descubre que ya tiene algo (es decir, está intentando agregar un duplicado, guárdelo en su lista original. De lo contrario, extráigalos. De esta forma, terminará con una lista con los elementos que fueron duplicados en su lista original. TreeSet <,> será otra opción, pero aún no la he usado, así que no puedo ofrecer consejos.

Answer 3

Aconsejaría no usar un Comparator para hacer esto. Es bastante difícil escribir un método legal de compare() basado en los otros campos.

Creo que una mejor solución sería crear una clase PersonWithoutId como tal:

public PersonWithoutId {
private String firstname, lastname;
private int age;
// no id field
public PersonWithoutId(Person original) { /* copy fields from Person */ }
@Overrides public boolean equals() { /* compare these 3 fields */ }
@Overrides public int hashCode() { /* hash these 3 fields */ }
}

Luego, dada una List<Person> llamada people puede hacer esto:

Set<PersonWithoutId> set = new HashSet<>();
for (Iterator<Person> i = people.iterator(); i.hasNext();)
if (!set.add(new PersonWithoutId(i.next())))
i.remove();

Editar

Como otros han señalado en los comentarios, esta solución no es ideal, ya que crea una carga de objetos para que el recolector de basura pueda manejar. Pero esta solución es mucho más rápida que una solución que utiliza un Comparator y un TreeSet . Mantener un Set en orden lleva tiempo y no tiene nada que ver con el problema original. Probé esto en List s de 1,000,000 instancias de Person construidas usando

new Person(
"" + rand.nextInt(500), // firstname
"" + rand.nextInt(500), // lastname
rand.nextInt(100), // age
rand.nextLong()) // id

y descubrió que esta solución es aproximadamente el doble de rápida que una solución que utiliza un TreeSet . (Es cierto que utilicé System.nanoTime() lugar de benchmarking adecuado).

Entonces, ¿cómo puedes hacer esto de manera eficiente sin crear montones de objetos innecesarios? Java no lo hace fácil. Una forma sería escribir dos nuevos métodos en Person

boolean equalsIgnoringId(Person other) { ... }
int hashCodeIgnoringId() { ... }

y luego escribir una implementación personalizada de Set<Person> donde básicamente corta y pega el código para HashSet excepto que reemplaza equals() y hashCode() por equalsIgnoringId() y hashCodeIgnoringId() .

En mi humilde opinión, el hecho de que pueda crear un TreeSet que use un Comparator , pero no un HashSet que use versiones personalizadas de equals / hashCode es un defecto grave en el lenguaje.

Answer 4

Como @LuiggiMendoza sugirió en los comentarios:

Puede crear una clase Comparator personalizada que compare dos objetos Person para igualdad, ignorando sus identificadores.

class PersonComparator implements Comparator<Person> {
// wraps the compareTo method to compare two Strings but also accounts for NPE
int compareStrings(String a, String b) {
if(a == b) { // both strings are the same string or are null
return 0;
} else if(a == null) { // first string is null, result is negative
return -1;
} else if(b == null){ // second string is null, result is positive
return 1;
} else { // no strings are null, return the result of compareTo
return a.compareTo(b);
}
}
@Override
public int compare(Person p1, Person p2) {
// comparisons on Person objects themselves
if(p1 == p2) { // Person 1 and Person 2 are the same Person object
return 0;
}
if(p1 == null && p2 != null) { // Person 1 is null and Person 2 is not, result is negative
return -1;
}
if(p1 != null && p2 == null) { // Person 1 is not null and Person 2 is, result is positive
return 1;
}
int result = 0;
// comparisons on the attributes of the Persons objects
result = compareStrings(p1.firstname, p2.firstname);
if(result != 0) { // Persons differ in first names, we can return the result
return result;
}
result = compareStrings(p1.lastname, p2.lastname);
if(result != 0) { // Persons differ in last names, we can return the result
return result;
}
return Integer.compare(p1.age, p2.age); // if both first name and last names are equal, the comparison difference is in their age
}
}

Ahora puede usar la estructura TreeSet con este Comparator personalizado y, por ejemplo, crear un método simple que elimine los valores duplicados.

List<Person> getListWithoutDups(List<Person> list) {
List<Person> newList = new ArrayList<Person>();
TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here
// foreach Person in the list
for(Person person : list) {
// if the person isn''t already in the set (meaning it''s not a duplicate)
// add it to the set and the new list
if(!set.contains(person)) {
set.add(person);
newList.add(person);
}
// otherwise it''s a duplicate so we don''t do anything
}
return newList;
}

La operación contains en TreeSet , como dice la documentación , "proporciona un costo de tiempo de registro (n) garantizado" .

El método que sugerí anteriormente toma el tiempo O(n*log(n)) ya que estamos realizando la operación contains en cada elemento de lista, pero también usa O(n) espacio para crear una nueva lista y TreeSet .

Si su lista es bastante grande (el espacio es bastante importante) pero su velocidad de procesamiento no es un problema, entonces, en lugar de agregar cada uno que no sea duplicado a la lista, puede eliminar cada duplicado que se encuentre:

 List<Person> getListWithoutDups(List<Person> list) {
TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here
Person person;
// for every Person in the list
for(int i = 0; i < list.size(); i++) {
person = list.get(i);
// if the person is already in the set (meaning it is a duplicate)
// remove it from the list
if(set.contains(person) {
list.remove(i);
i--; // make sure to accommodate for the list shifting after removal
}
// otherwise add it to the set of non-duplicates
else {
set.add(person);
}
}
return list;
}

Dado que cada operación de remove en una lista toma O(n) tiempo (porque la lista se desplaza cada vez que se elimina un elemento), y cada operación contains log(n) , este enfoque sería O(n^2 log(n)) a tiempo.

Sin embargo, la complejidad del espacio se reduciría a la mitad, ya que solo creamos el TreeSet y no la segunda lista.