Discussion :

[Opsse]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[joel.drigo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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) :

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Opsse]

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à.

[joel.drigo]

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.

[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.

[joel.drigo]

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 :

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 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.