Discussion :

[agparchitecture]

Bonjour à tous, j'ai fait le petit code ci-dessous qui permet de récupérer un liste de doublons dans une liste de string. J'aurais souhaité avoir votre avis sur le code.

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
 
class Program
	{
		public static void Main(string[] args)
		{
			Console.WriteLine("Test recherche doublons");
 
			List<string> withdouble = new List<string>(new string[] {"A", "B", "C", "C", "C", "C", "D", "E", "E", "G", "F"} );
 
			List<string> Doublons = new List<string>();
			string BaseCompare = "";
 
			withdouble.Sort(); //On trie par ordre
 
 
			for (int i = 0; i < withdouble.Count; i++)
			{
 
				if ((i+1 < withdouble.Count) && (withdouble[i] == withdouble[i+1]))
				{
					BaseCompare = withdouble[i];
					Doublons.Add(withdouble[i] + " - index : " + i.ToString()); //On ajoute le premier doublons
 
					int j = i; // entier de la boucle imbriquée pour voir si plusieurs doubles
 
					do
					{
						j++;
						if (withdouble[j] == BaseCompare ) Doublons.Add(withdouble[j] + " - index : " + j.ToString());
 
					}while((j+1 < withdouble.Count) && (withdouble[j+1] == BaseCompare));
 
					if (j < withdouble.Count) i = j; else i = withdouble.Count;
				}
 
			}
 
 
			foreach (string s in Doublons)
			{
				Console.Write(s + Environment.NewLine);
			}
 
 
			Console.Write("Press any key to continue . . . ");
			Console.ReadKey(true);
		}
	}

Merci beaucoup.

[anemol]

Bonjour,

En utilisant Linq, tu pourrais faire plus simplement ceci:

Code :

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

1
2
3
4
5
6
 
using System.Linq;
...
List<string> avecDoublons = new List<string>(new string[] {"A","Z", "B", "C", "C", "C", "C", "D", "E", "E", "G", "F"} );
 
List<string> sansDoublon=avecDoublons.Distinct().ToList();

[agparchitecture]

Effectivement j'avais vu lors de mes recherches.

Il me sembles que link supprime les doublons de la list. mais ce qui m'intéresse réellement c'est de pouvoir récupérer une list des doubles afin de pouvoir sélectionner ultérieurement ceux que je souhaite supprimer et éventuellement en conserver l'un ou l'autre...

en fait l'avis sur le code était plus sur le comptage des index et la vérification des condition de boucles.

Merci

[DonQuiche]

Bonjour à toi.

a) L'idée de base n'est pas mauvaise mais pas optimale. Et surtout l'implémentation est erronée :
* Un algo naïf serait en O(n²) avec deux boucles imbriquées.

* Ton algo à base de tri préliminaire aurait dû être en O(n.l(n)) mais tu l'as mal implémenté en ajoutant une étape en O(n² / 2). Tu ne devrais pas deux boucles imbriquées, tu devrais à la place avoir une seule boucle avec une variable "nombrePrécédent".

* L'algo optimal utiliserait des tables de hachages (HashSet ou Dictionnaire) pour un résultat en O(n) (l'insertion et la lecture dans une table de hachage sont en O(1)).


b) Il y a des problèmes avec les conventions de style qui rendent le code plus difficile à lire qu'il ne devrait l'être. Opte soit pour l'anglais soit pour le français mais ne mélange pas les deux. Et respecte une convention de casse, de préférence la convention standard de c# (args, doublons, withDouble, baseCompare, etc). Voir wikipédia pour CamelCase contre pascalCase.

c) Si une fonction fait plus de dix lignes (grosso modo), découpe-la. Ici le bon choix aurait été de créer une fonction spécifique pour la boucle intérieure mais puisque tu vas devoir changer l'algo...

[agparchitecture]

Ok merci pour les informations et critique.

Par contre pourrais-je avoir des explications sur :

a.1) algo en : O(n.l(n)), O(n²/2), O(n), ... Que signifie le O et le n ?

a.2) HashSet ou Dictionnaire: Qu'est-ce que c'est et comment pourrais-je les utiliser?

b) memo perso: Il faut vraiment que je fasse attention

c) explication complémentaire : La création d'une fonction est bien prévue mais ce projet est juste une application console minimum afin de tester l'algorithme avant de l'utiliser dans un projet un peu plus complet.

d) compléments d'informations: le but final est de pouvoir travailler et récupérer une list<objetperso> vérifié sur une propriété string. je suppose que c'est le même principe que les conseil donné?

[DonQuiche]

a.1) algo en : O(n.l(n)), O(n²/2), O(n), ... Que signifie le O et le n ?

C'est la complexité algorithmique. Avec la notation en O majuscule pour désigner la composante dominant à l'infini (asymptotique).

Pour faire simple, pour un nombre d'éléments n, le temps de calcul sera proportionnel à n² si la complexité est en O(n²). Donc pour un n suffisamment grand un algorithme en O(n²) sera moins rapide qu'un algorithme en O(n.ln(n)), qui lui même sera moins rapide qu'un algorithme en O(n).

Dans ton algorithme tu commences par un tri dont la complexité est en O(n.ln(n)).
Puis tu ajoutes n + (n - 1) + (n - 2) + (n - 3) + ... itérations. C'est égal à n * (n-1) / 2, donc n²/2 - n/2.
La complexité totale serait donc en n²/2 + n.ln(n) + n/2 mais on retient seulement le terme le plus grand : n². Donc ton algorithme a une complexité en O(n²).

a.2) HashSet ou Dictionnaire: Qu'est-ce que c'est et comment pourrais-je les utiliser?

Un HashSet est un ensemble. Tu l'utilises un peu comme une liste sauf que les éléments ne sont pas ordonnés (tu ne peux pas demander le i-ème élément) et que chaque élément ne peut être présent qu'une fois. Il est très rapide de tester si l'ensemble contient un élément donné (O(1), contre O(n) pour une liste).

Code c# :

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

1
2
3
4
5
6
7
8
9
var ensemble = new HashSet<string>();
 
// Après ça tu peux utiliser :
ensemble.Add("A")         // renvoie vrai car "A" n'était pas encore dans l'ensemble.
ensemble.Add("A")         // renvoie faux car "A" est déjà contenu. L'élément n'est pas ré-ajouté
ensemble.Add("C")               // renvoie vrai.
ensemble.Add("D")               // renvoie vrai. L'ensemble contient maintenant A, C, D, dans n'importe quel ordre.
if (ensemble.Contains("A"))         // très rapide
ensemble[0]                  // erreur de compilation, impossible d'obtenir un élément par son indice

Pour le dictionnaire c'est un peu pareil mais tu associés des clés avec des valeurs. Par exemple la valeur pourrait être une personne et la clé un nom, pour retrouver rapidement une personne depuis son nom. Chaque clé ne peut être contenue qu'une fois. On utilise dictionnaire[clé] = valeur, ou valeur = dictionnaire[clé].

d) compléments d'informations: le but final est de pouvoir travailler et récupérer une list<objetperso> vérifié sur une propriété string. je suppose que c'est le même principe que les conseil donné?

L'ensemble n'est qu'un intermédiaire pour tester rapidement si un élément est déjà dans l'ensemble ou non. Libre à toi de générer ce que tu veux, une liste ou autre.

[anemol]

Effectivement j'avais vu lors de mes recherches.

Il me sembles que link supprime les doublons de la list. mais ce qui m'intéresse réellement c'est de pouvoir récupérer une list des doubles afin de pouvoir sélectionner ultérieurement ceux que je souhaite supprimer et éventuellement en conserver l'un ou l'autre...

en fait l'avis sur le code était plus sur le comptage des index et la vérification des condition de boucles.

Merci

Ah oui, désolé, je n'avais pas fait attention.

Sinon, j'aurai codé ceci:

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
 
                        Dictionary<string,int> spectre=new Dictionary<string, int>();
			List<string> withdouble = new List<string>(new string[] {"A", "B", "C", "C", "C", "C", "D", "E", "E", "G", "F"} );
			List<string> Doublons = new List<string>();
			withdouble.Sort();
 
			foreach(string item in withdouble)
			{
				if (!spectre.ContainsKey(item))
					spectre.Add(item,1);
				else
					spectre[item]++;
			}
 
			foreach(string item in spectre.Keys)
			{
				if (spectre[item]>1)
				{
					Console.WriteLine("{0}: {1} fois withdouble(#{2})",item,spectre[item],withdouble.IndexOf(item));
					Doublons.Add(item);
				}
			}
 
 
Qui donnera:
C: 4 fois withdouble(#2)
E: 2 fois withdouble(#7)