Comparer et modifier les éléments d'une même liste

Bonjour,

J'ai un petit problème de programmation à vous poser.

J'ai un ensemble d'éléments que je récupère dans une liste et je voudrais supprimer les doublons, définit d'après mes critères.

Dans un monde parfait voila comment je l'aurais codé :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

List<DBObject> items = getItems().toArray();   for (DBObject item1 : items) { for (DBObject item2 : items) { if(looksLike(item1, item2)) { items.remove(item2); } } }

---

Evidemment ca ne fonctionne pas, modifier la liste pendant que je l’itère c'est un peu barbare.

Ils y a plusieurs solutions simples mais la liste est très grosse (jusqu'à plusieurs millions d'éléments) et j'aimerai trouvé une solution qui respecte quelques critères :

• Pas de copie de liste
• Pas de items.get(i)
• Le moins de tours de boucle possible (ne pas faire la vérification 2 fois)

Est ce possible ?

Salut,

Avec les contraintes que tu donnes, c'est impossible, à moins que l'implémentation de List soit prévue pour (donc pas avec les implémentations standard). Sans copie, on est obligé de faire des boucles pour savoir si une valeur existe en double (même implicite lorsqu'on fait un indexOf()). Sans get(), même implicite (ce qu'on fait lorsqu'on itère), impossible de connaitre le contenu de la liste.

Maintenant, la solution évidente sans double-boucle comme tu fais, et sans copie est, avec un défaut sur la position final des éléments dédoublonnés (Par exemple :[1,2,3,2] donne [1,3,2] et non [1, 2, 3]) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public static <T> void dedoublonneLent(List<T> list) { int position=0; for(Iterator<T> iter = list.iterator(); iter.hasNext(); ) { T item = iter.next(); final int index = list.lastIndexOf(item); if ( index>=0 && index!=position ) { iter.remove(); } else { position++; } } }

---

Seulement, avec une ArrayList, c'est ultra lent, parce que la suppression se fait par copie de partie de tableau, par la fin : donc avec 1 millon d'éléments par exemple, si le premier élément a un doublon en position 2, on copie 999 998 éléments.

La solution est de parcourir la liste par l'arrière, avec un "reverse iterator", mais on introduit forcément un get() pour le faire. L'avantage est qu'on supprime par l'arrière, donc les copies de tableau dues aux suppressions sont favorablement courte (sauf, si on a peu de doublon, en particulier s'ils sont distribués plutôt au début — cependant si on a peu de doublons, on fera peu de suppressions, donc peu de copies).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public static <T> void dedoublonne(List<T> list) { Iterator<T> iter = new Iterator<T>() { private int index=list.size(); private boolean ready; public boolean hasNext() { return index>0; } public T next() { if ( index>0 ) { ready=true; return list.get(--index); } throw new NoSuchElementException(); } public void remove() { if ( ready ) { list.remove(index); ready=false; } else { throw new IllegalStateException(); } } }; int position=list.size()-1; for(; iter.hasNext(); ) { T item = iter.next(); final int index = list.indexOf(item); if ( index>=0 && index!=position ) { iter.remove(); } position--; } }

---

Maintenant, je suppose que la contrainte de copie est un problème de mémoire : faut voir si ça vaut vraiment le coup d'économiser cette mémoire au détriment d'une part du temps, et d'autre part de la simplicité, moins importante certe.

Par exemple, la solution la plus évidente pour faire du dédoublonnage par copie, sans contrainte sur l'ordre est de passer par un set, tout simplement par new HashSet<Integer>(list);En Java 8, on pourra même conserver l'ordre avec un distinct sur un stream :

Code:

---

list.stream().distinct().collect(Collectors.toList());

---

Mais il y a forcément copie.

Les temps comparés des différentes méthodes sont éloquents (ici pour 1 000 000 de Integer créés aléatoirement) :

Citation:

---

Dedoublonnage par copie/set : 0.191 s
Dedoublonnage par stream : 0.187 s
Dedoublonnage sans copie (backward) : 1.879 s
Dedoublonnage sans copie lent (forward) : 687.823 s

---

Le programme complet :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

public class DedoublonneList {   public static <T> void dedoublonneLent(List<T> list) { int position=0; for(Iterator<T> iter = list.iterator(); iter.hasNext(); ) { T item = iter.next(); final int index = list.lastIndexOf(item); if ( index>=0 && index!=position ) { iter.remove(); } else { position++; } } }   public static <T> void dedoublonne(List<T> list) { Iterator<T> iter = new Iterator<T>() { private int index=list.size(); private boolean ready; public boolean hasNext() { return index>0; } public T next() { if ( index>0 ) { ready=true; return list.get(--index); } throw new NoSuchElementException(); } public void remove() { if ( ready ) { list.remove(index); ready=false; } else { throw new IllegalStateException(); } } }; int position=list.size()-1; for(; iter.hasNext(); ) { T item = iter.next(); final int index = list.indexOf(item); if ( index>=0 && index!=position ) { iter.remove(); } position--; } }   public static void main(String[] args) {   final int n = 1_000_000; final List<Integer> list = new ArrayList<>(n); final Random random = new Random(); for(int i=0; i<n; i++) { list.add(random.nextInt(100)); // la limite à 100 favorise les doublons (donc ici forcément beaucoup de valeurs en nombreux exemplaires) } final List<Integer> dupliqlist = new ArrayList<>(list); final List<Integer> dupliqlist2 = new ArrayList<>(list);   // version par copie dans un set final long timecopy = System.currentTimeMillis(); final Set<Integer> set = new HashSet<Integer>(list); System.out.println("Dedoublonnage par copie/set : "+((System.currentTimeMillis()-timecopy)/1000d)+" s");   // version java 8 final long timestream = System.currentTimeMillis(); final List<Integer> dedoublonnee = dupliqlist.stream().distinct().collect(Collectors.toList()); System.out.println("Dedoublonnage par stream : "+((System.currentTimeMillis()-timestream)/1000d)+" s");   // version par parcourt par l'arrière final long time = System.currentTimeMillis(); dedoublonne(list); System.out.println("Dedoublonnage sans copie (backward) : " + ((System.currentTimeMillis()-time)/1000d)+" s");   // version par parcourt par l'avant final long time2 = System.currentTimeMillis(); dedoublonneLent(dupliqlist2); System.out.println("Dedoublonnage sans copie lent (forward) : " + ((System.currentTimeMillis()-time2)/1000d)+" s");   }     }

---

A noter, que si l'ordre n'a pas besoin d'être conservé, il faut voir si un tri dès le départ (qui prend du temps forcément) est avantageux ou pas pour gagner du temps (sans copie) : il est sûr que le dédoublonnage d'une liste prétriée peut être fait très rapidement, par parcourt successive des "tronçons" de valeurs successives égales (les doublons), par un parcourt unique par l'arrière.

Beaucoup d'informations très intéressantes, merci pour tous ces détails.

Je ne peux pas utiliser de HashSet car l'égalité n'est pas stricte, j’accepte un pourcentage de différence sur certaines valeurs par exemple. Idem pour le trie, sans critère précis impossible de trier de façon cohérente.

Par contre tu m'as donnée une bonne idée : trier au moment de la récupération.
Comme je charge les éléments depuis une base de données je peux les récupérer un par un avec un curseur et ajouter à ma liste que si l'élément n'y est pas déjà.

Citation:

---

Envoyé par Opsse

Comme je charge les éléments depuis une base de données je peux les récupérer un par un avec un curseur et ajouter à ma liste que si l'élément n'y est pas déjà.

---

C'est encore mieux : ça économisera de la mémoire, et du tempts (agrandissement de la liste) et évitera d'avoir à perdre du temps à dédoublonner ensuite, à postérior. Par contre, je ne vois pas comment tu peux faire si l'égalité n'est pas "stricte". C'est d'ailleurs une même une très mauvaise idée d'implémenter un equals qui ne fasse pas une égalité stricte (ça va même à l'encontre du contrat de la la méthode). Quand j'ai besoin de faire ce genre de chose, je fais une autre méthode ( same(), qui me sert à tester si une instance est un "clone" au sens que ça représente la même chose, mais que ce n'est pas forcément égal, ou like(), quand ça ressemble à ). Sans ça, ce n'est pas seulement les sets ou les maps qu'on ne peut pas utiliser (ce n'est pas la seule condition pour les utiliser d'ailleurs), mais aussi les indexOf(), contains() etc, des List, sans parler de l'égalité en elle-même.

Je ne crois pas avoir dis que j'avais implémenté un equals, dans mon exemple j'ai appelé une méthode habillement nommée "looksLike".

Donc soit je n'ai pas compris ta remarque, soit il y a eu un malentendu.

Citation:

---

Envoyé par Opsse

Je ne crois pas avoir dis que j'avais implémenté un equals, dans mon exemple j'ai appelé une méthode habillement nommée "looksLike".

Donc soit je n'ai pas compris ta remarque, soit il y a eu un malentendu.

---

Tu disais :

Citation:

---

Envoyé par Opsse

Je ne peux pas utiliser de HashSet car l'égalité n'est pas stricte, j’accepte un pourcentage de différence sur certaines valeurs par exemple. Idem pour le trie, sans critère précis impossible de trier de façon cohérente.

---

Je pensais que tu disais que tu avais implémenté equals() de manière non stricte. Par ailleurs, j'ai dû mal à comprendre la notion de dédoublonnage avec des valeurs qui ne sont pas égales :weird: Un doublon de 1 c'est 1, pas 1.001. C'est encore plus problématique au sujet de la valeur à conserver : si on a 1, 1.001, 1.01, 0.999 qui sont équivalent, après dédoublonnage, c'est lequel qu'on conserve ?

Passons cet aspect : donc, si je comprends bien, le but est de conserver une seule valeur parmi plusieurs qui sont proches (ou plus généralement, se ressemblent). Dans ce cas, aucune méthode standard ne peut être utilisée (Que ça soit par set, par contains(), indexOf(), etc..., qui se fondent toutes sur equals() (et éventuellement hashCode()). Impossible de se passer d'un parcourt dans ce cas pour faire un équivalent de indexOf() (contains se base sur indexOf()).

Donc, la seule solution est de le faire en amont, sous forme de tri par insertion. Qui ne sera vraiment efficace que si tu mets en place une relation d'ordre (un tri). Sans relation d'ordre, il te faut parcourir l'ensemble des valeurs déjà insérées pour voir si l'une d'entre-elles "lookslike" celle que tu veux ajouter (à l'optimisation près que tu peux arrête la recherche dès qu'on a trouvé, mais au pire on parcourera toujours tous (s'il y a des millions de valeurs dans la liste, ça signifie parcourir des millions d'élements, ce qui sera très lent). Et en plus, tu ne peux même paralléliser.

Si tu as une relation d'ordre, même partielle, tu peux paralléliser, ou limiter le parcourt. Si tu peux déterminer à partir d'une valeur, une valeur pivot, celle qu'on conservera par dédoublonnage, alors la relation d'ordre peut s'appliquer aux valeurs pivots seulement. Soit par hashset (en se fondans sur le hashcode des valeurs pivot), ou par map, en utilisant des intervalles comme clefs (ce qu'on appelle "regroupements").

Par exemple, si la fonction lookslike est comme ça :

Code:

---

1 2 3

public boolean lookslike(double d1, double d2) { return ((int)d1)==((int)d2); }

---

Le pivot sera pivot(d)=((int)(d))

Et la relation d'ordre est celle des entiers.

Par exemple, si la fonction lookslike est comme ça (sans null) :

Code:

---

1 2 3

public boolean lookslike(String d1, String d2) { return d1.trim().toUpperCase().equals(d2.trim().toUpperCase()); }

---

Le pivot sera pivot(d)=d1.trim().toUpperCase()

Et la relation d'ordre est celle des String, ou une collation.

Je comprends bien l'enjeu de déterminer une relation d'ordre mais je crains que ce soit compliqué dans mon cas. J'ai simplifié le problème pour poser ma question, mais pour entrer un peu plus dans le détail voici à quoi ressemble les données que je traite :

String A1
String A2
boolean B
float C
int D
String E1
String E2
// autres champs non déterminant dans les comparaisons

je considère l'égalité parfaite entre item et item'' si :

Code:

---

1 2 3 4

if (A1.equals(A1'') || A2.equals(A2'')) return true; else return false;

---

je considère que item et item'' se ressemblent si :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

if(E1.equals(E1'') && E2.equals(E2'')) { if(B == true && B'' == true) { if(C égale à +/- 10% C'') return true; } else if(B == false && B'' == false) { if(D égale à +/- 1000 D'') return true; } } return false

---

Et donc pour chaque élément de la base de donnée je l'ajoute à ma liste si :
- aucune égalité stricte n'est trouvé dans ma liste
- aucune égalité partielle n'est trouvé dans ma liste

Je conserve le 1er élément que je trouve, ce choix n'est pas critique.

J'ai donc une complexité O(1+2+3+...+(n-2)+(n-1)) (ca me semble peu, je ne me suis pas trompé ?)
Pour ne rien arranger le nombre d'égalité, stricte ou partielle, est assez faible. Moins de 10% sur les données que j'ai testé.

Je pourrais effectivement trier en me basant sur le champ A1 et A2. Mais comme l'égalité stricte est assez rare, dans 99% des cas je serais quand même obligé de parcourir toute ma liste pour vérifier que je n'ai pas d'égalité partielle.
Par contre en triant en plus sur E1 et E2 ca peut être intéressant. Il existe une solution pour combiner de façon intelligente A1 ou A2 ou E1-E2 ?
Même si je regroupe les champs en faisant E3 = E1 + E2., je suis obligé de trier 3 fois puis de comparer 3 fois (A1, A2 puis E3).

Le plus drôle dans l'histoire c'est qu'une fois que j'ai ma liste je la compare de la même façon avec une 2ème base de données de plusieurs millions d'éléments afin de la mettre à jour. Heureusement je n'ai pas trop de contrainte de temps pour effectuer la totalité du traitement, disons 2h max mais le plus rapide est quand même le mieux.


PS : il est plus efficace de faire d1.toUpperCase().equals(d2.toUpperCase()); plutot que d1.equalsIgnoreCase(d2); ?

lookslike peut être égal à true, alors que equals() non ?

Mais, OK, pas de relation d'ordre à priori (quoique, je ne suis pas assez mathématicien pour le démontrer), mais partition possible (pour faire du traitement en parallèle), mais ça obligera à instancier probablement beaucoup de classe. C'est toujours mieux je pense que de tout charger et supprimer ensuite à mon avis.

Accessoirement, une petite optimisation est d'exclure les B!=B'' du "dédoublonnage" (les inclure donc systèmatiquement en cas de non égalité si cette condition est vérifiée). Enfin ce n'est plus vraiment un dédoublonnage, mais bon.

Citation:

---

Envoyé par Opsse

PS : il est plus efficace de faire d1.toUpperCase().equals(d2.toUpperCase()); plutot que d1.equalsIgnoreCase(d2); ?

---

Non (plein d'instanciation de chaînes), c'était juste pour l'exemple (bidon).