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é?

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

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

[agparchitecture]

Ok merci pour les éclaircissement et les explication pour la complexité algorithmique

donc je pourrais faire une fonction pour récupérer les doublons comme :

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
 
public List<string> RecuperationDoubons(List<string> lst)
{
 
     List<string> listDoublons = new List<string>(); //Elements à retourner
     HashSet<string> hash = new HashSet<string>(); //Hashset temporaire
 
     foreach(string str in lst)
     {
 
          if(hash.add(str) == false) listDoublons.Add(str); //Question: Ajoute bien les suivants mais comment intégrer le premier mis dans le Hashset pour obtenir liste complète des doublons.
 
     }
 
     return listDoublons;
 
}

question sur cette fonction: voir commentaire dans la fonction.

Mes recherches m'ont également apportée la solution suivante (non testé actuellement) mais qui en plus donne également le nombre de doublons par élément

Code :

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

1
2
3
4
5
6
7
 
public Dictionary<string, int> RecuperationDoubons(List<string> lst)
{
     return lst.GroupBy(x=>x)
                   .Where(g=>g.Count()>1)
                   .ToDictionary(x=>x.Key,y=>y.Count());
}

Quelle solution est la meilleure?

J'ai quand même toujours un problème que je ne vois pas comment résoudre avec le hashset ou avec Link.

En fait j'ai une liste qui comprend des raccourcis internets et je souhaiterais pouvoir récupérer tous les doublons qui pointent vers la même page en sachant que je souhaiterais que les liens suivants :

• http://www.domaine.com/page1.html
• http://domaine.com/page1.html
• http://www.domaine.com/page1.html#emplacementDansLaPage
• http://domaine.com/page1.html#emplacementDansLaPage

soient considérés comme identique.

Comment envisager/aborder l'algorithme afin qu'il le fasse?

[anemol]

Hum. Trouver des doublons de liens Internet c'est déjà plus ardu.

Tout va dépendre de la provenance de tes liens.

Par exemple:
http://www.developpez.net et http://www.developpez.net/forums/ pointent au final la même page. (c'est le site lui même qui redirige la page par défaut)

[DonQuiche]

donc je pourrais faire une fonction pour récupérer les doublons comme :

Tu as tout compris.

Quelle solution est la meilleure?

D'abord à toi de décider si tu as besoin du nombre de doublons.

* Si oui tu as le choix entre une solution à base de dictionnaire (voir solution d'Anemol) en O(n) et celle avec Linq (avec un Q).
* Sinon tu as le choix entre une solution à base d'ensemble comme celle que tu as faite en O(n) ou celle avec Linq.

La solution avec Linq est en O(n²) : pour chacun des n éléments, on appelle Count() qui est lui-même en O(n) (passe en revue tous les éléments). Donc cette solution sera plus lente pour un grand n (pas forcément pour un petit n, il faudrait tester).

Mais as-tu un grand n ? As-tu besoin d'une solution optimale ? Ou as-tu besoin d'une solution lisible ? Dans ce dernier cas, les trois peuvent être bien écrites, à toi de choisir celle qui te plaît le mieux. Pour ma part j'avais abordé les perfs dès le début pour la seule raison que ton tri me laissait à penser que c'était ton objectif.

PS : concernant la taille du n, disons qu'au-delà de quelques dizaines d'éléments il est certain que les solutions à base de dico/ensemble l'emporteront. Mais tu n'as sans doute pas de probllème de perfs à moins d'avoir au moins quelques milliers d'éléments (ce qui donnerait quelques millions de cycles pour du O(n²) - une broutille pour un CPU moderne).

En fait j'ai une liste qui comprend des raccourcis internets et je souhaiterais pouvoir récupérer tous les doublons qui pointent vers la même page en sachant que je souhaiterais que les liens suivants :

Qu'entends-tu par "récupérer les liens" ? Ta page est-elle représentée par un simple suite de caractères ou bien par un arbre représentant les composants de la page ? Veux-tu récupérer des positions au sein d'une chaîne de caractères ou bien des objets pré-existants représentant des liens ?

De ce que tu me dis j'ai l'impression que tu cherches en fait à grouper des objets représentant des liens similaires. Si oui alors tu peux utiliser .Group() tout seul, comme dans Linq. C'est équivalent à un code à base de dictionnaire. Tu obtiendras alors un groupe par url unique, et dans chaque groupe l'ensemble des objets représentant les liens pointant vers cette url.

Si tu n'as pas d'objet pré-existant, seulement une chaîne de caractères, alors un code à base de dictionnaire fera l'affaire, avec une liste associé à chaque clé (Dictionnary<string, List<position>>).

[agparchitecture]

J'ai récupérer de chrome, firefox, et IE de plusieurs PC/tablette, portables, ... les favoris en pages html et fichiers urls (semblant gestionnaires de favoris).

je lis l'ensemble des fichiers pour obtenir une énorme liste des favoris récupérés (actuellement +/- 53.000 Liens url -> j'ai eu la favorite aigüe à un moment ou je mettais toutes les pages intéressantes en favoris ).

j'ai donc créer une class model pour un favoris comprenant :

1. propriété (type) : explication
   Id (Guid): pour l'identification de chaque favoris
   Nom (string): le nom de la page)
   Adresse (string): l'adresse url du lien
   Groupes (string[]): les dossiers dans lesquels le favoris était classé

j'ai ensuite créer une class pouvant gérer l’ensemble des favoris pour les reclasser, les supprimer, vérifier les redirections, vérifier les pages 404, les exporter, ...

j'aurais souhaité, maintenant, récupérer la liste des doublons qui pointe vers une même adresse url afin de pouvoir choisir lequel supprimer en fonction du groupe dans lesquels se trouve le favoris.

@anemol

Tout va dépendre de la provenance de tes liens.

Je souhaiterais que cette fonction de recherche de même page ne tiennent pas compte des redirections serveurs mais uniquement de l'adresse du liens. Ce qui me pose problème est dans le cas d'une position précise dans la page avec # car l'adresse n'est pas considéré comme identique si présent ou non (idem si p^résence ou non de www)

@DonQuiche

Qu'entends-tu par "récupérer les liens"

Réellement récupérer une list des objet favoris (class model) qui "pointe" vers la même page

De ce que tu me dis j'ai l'impression que tu cherches en fait à grouper des objets représentant des liens similaires. Si oui alors tu peux utiliser .Group() tout seul, comme dans Linq. C'est équivalent à un code à base de dictionnaire. Tu obtiendras alors un groupe par url unique, et dans chaque groupe l'ensemble des objets représentant les liens pointant vers cette url.

La difficulté provient de la structure d'un lien qui peut être différente mais quand même pointé vers la même page

En gros et schématiquement j'aurais voulu faire dans un premier temps:


List des favoris récupérer (List obtenue par lecture des fichiers)

-> recherche et récupération (dans une autre List) des favoris pointant sur la même page (attention avec la structure du lien) CE QUI ME POSE PROBLEME

-> choix des favoris à conserver ou non dans la liste des favoris pointant vers la même page

-> Suppression des favoris dans la List principal en fonction des favoris sélectionnés dans la list des doublons pointant vers la même pages

-> List des favoris récupérer (List obtenue par lecture des fichiers) nettoyé des doublons selectionnés

Dans un second temps (seconde possibilité):

enlever les favoris en doubles et ajouter au group d'un favoris conservé les groups des favoris supprimés.

J'espère que vous avez compris un peu mieux mes envies. Je n'attend pas spécialement un code tout fait mais une direction/approche de la problématique.

merci pour le temps passer à résoudre mon problème.

[DonQuiche]

Puisque tes liens sont déjà sous forme d'objets, c'est assez simple :

Code :

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

1
2
3
4
5
6
7
8
var liensGroupés = liens.GroupBy(x => Simplifier(x.Adresse));
 
string Simplifier(string url)
{
   int index = url.LastIndexOf('#');
   if (index < 0) return url;
   return url.Substring(0, index);
}

Chaque groupe aura l'url en clé (sans le #....), et contiendra la liste des liens correspondant. Et de la façon la plus efficace possible, via un dictionnaire en interne.

[anemol]

Pour la simplification des liens, j'aurai plutôt utilisé Regex

Code :

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

1
2
3
4
5
6
7
 
string Simplifier(string url)
{
   string simplifiee=Regex.Replace(url,@"\?(.*)",""); // Supprime les paramètres éventuels
   simplifiee=Regex.Replace(simplifiee,@"#(.*)",""); // Supprime les ancres
   return simplifiee;
}

[DonQuiche]

Le problème des paramètres est qu'en général ils doivent être conservés. Par exemple sur les forums comme dvp l'id du sujet est un paramètre.

Si on veut faire un traitement fin il est possible d'avoir recours à HttpUtility.ParseQueryString pour obtenir un dictionnaire contenant les couples (paramètre, valeur).

Sinon pour virer l'ancre on peut même faire : url.Split('#').First()

[agparchitecture]

Le problème des paramètres est qu'en général ils doivent être conservés. Par exemple sur les forums comme dvp l'id du sujet est un paramètre.

Si on veut faire un traitement fin il est possible d'avoir recours à HttpUtility.ParseQueryString pour obtenir un dictionnaire contenant les couples (paramètre, valeur).

Sinon pour virer l'ancre on peut même faire : url.Split('#').First()

Exactement ce que je cherchais à faire supprimer l'ancre. Merci

Par contre je ne parviens pas à utiliser le group que je reçois avec le link. Il me retourne un GroupedEnumerate. Comment puis-je afficher le résultat dans une listbox ou un listview?

Faut-il que je fasse deux boucles imbriqués?

1 pour les groupes
1 pour les éléments dans les groupes?

Du coup cela ne revient-il pas à faire ce que je faisait avant?? Une subtilité m'échappe...

[DonQuiche]

C'est un énumérable d'éléments de type "Model", donc tu peux faire tout ce qu'on fait d'habitude avec les énumérables : foreach, utiliser les méthodes Linq (First, Order, GroupBy, Where, Select, etc).

Pour ListBox, tout dépend si tu utlises WPF ou WinForms. Selon le cas soit tu créeras manuellement des ListBoxItems (tu dois aussi pouvoir fournir directement une chaîne de caractères cela dit, par exemple l'adresse), soit tu utiliseras du data binding. Je t'invite à regarder des exemples pour ListBox.

Enfin tu devras faire deux boucles imbriquées si tu veux passer en revue tous les éléments (doublons compris) mais ce sera alors en O(n) car tu ne visiteras que N éléments au total. Et si tu te fiches des doublons tu n'as besoin que d'une seule boucle.

[agparchitecture]

Ok

c'est bon je suis parvenu à faire ce que je souhaitais. Merci pour votre aide et conseil j'ai encore appris pas mal de chose

A un prochain problème