Discussion :

[pyriame]

Bonjour,

J'ai une table de jonction (ID, A(int), B(int)) entre 2 tables. Dans la colonne A plusieurs fois le même int possible et dans la colonne B plusieurs fois le même int possible aussi. Seul le couple Ax/Bx est unique.

Je soupçonne dans cette table qu'il y'est des doublons, c'est a dire qu'un Ax soit lié exactement aux même B1,B2,Bn etc... qu'un autre Ay. En soit ce n'est pas un problème et je ne cherche pas à éliminé ces doublons mais juste a les confondre pour pouvoir faire un traitement un peu différent.

Pour cela je suis partie sur un dictionnaire de list<int> avec pour chaque Ax dans la table, la liste de tous les B existants.

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
 
 using (var db = new DiagEntities())
                {
                    Dictionary<int, List<int>> Dict_Sum_Qvrai = new Dictionary<int, List<int>>();
 
                    var TableRestante = (from p in db.Jonctabs  // jonctabs = table complete
                                  where p.QuestionSEQ==8
                                  select p).ToList();
 
                    var Reponse = ((from p in TableRestante
                                    select p.ReponseSEQ).Distinct()).ToList();
 
                    foreach (var item in Reponse)
                    {
                        var ListeQuestion = (from p in TableRestante
                                       where p.ReponseSEQ == item
                                      select p.QuestionSEQ).ToList();
 
                        Dict_Sum_Qvrai.Add(item, ListeQuestion);
                    }
 
 
                    Rita1.DataSource = Dict_Sum_Qvrai;
                    Rita1.DataBind();

Déja mon gridview refuse de m'afficher un dictionnaire de liste , il me sort une erreur du style il lui manque la capacity . Je suppose que l'autocolumn ne lui va pas et que je doit lui donner le nombre de colonne que je souhaite. Je sais pas faire Bon c'est pas grave cela me sert uniquement de contrôle visuel.

A présent je voulais savoir de qu'elle façon il était possible de comparer des listes entre elles afin de déterminer si une ou plusieurs d'entre elles étaient strictement identique ?

merci de votre aide

[jopopmk]

Salut,

avec Linq une méthode possible pour comparer deux énumérables peut être d'utiliser les fonctions Except et Union. La première fera la soustraction des éléments de la liste en paramètre (liste2) dans la liste appelante (list1). Problème : si liste2 possède tous les éléments de liste1 avec quelques valeurs en plus on obtient quand même 0 éléments en sortie. Il faut donc faire la même manip' dans l'autre sens et agglomérer les deux différences dans un même set, c'est là qu'intervient la deuxième fonction. En gros ça donnerait un truc du genre :

Code :

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

MessageBox.Show((list1.Except(list2).Union(list2.Except(list1)).Count() == 0) ? "same lists" : "different lists");

Niveau perf' je sais pas ce que ça vaut par contre.

[pyriame]

Bonjour merci pour ton aide .

Effectivement j'avais passer en revu le travail sur les ensembles et j'avais tenté un truc avec exept, intersect union etc.. et une double boucle (for (int i.....) dans for (int j...) sans grande réussite. Enfin je dit ça mais en vérité le truc était tellement tordu que j'arrivais même plus a me représenter le résultat que je devrais obtenir pour me dire "ça marche "
Je pensais pas pouvoir agréger les choses comme tu l'as fait donc à tester !

Pour la perf je me pose toujours la question aussi . Les tables de jonctions peuvent être treeesss longue... le compare " List 1 à List2, puis list1 a List3 puis List 1 à list n. Ensuite compare List2 a List3, puis List 2 à List4 , ensuite compare List3 etc...
ça risque de faire trèeeeesss long niveau nombre d'opération. Comme je suis sur des fonctions de vérification j'ai pas trop le moyen de m'y soustraire. Pour une toute petite table j'ai déjà 19 listes donc a la louche 324 comparaison a faire.

Il n'existerait pas a votre connaissance un moyen peu gourmand en ressource de comparer un grand nombre de liste entre elle ?

Bonne journée et merci!

[jopopmk]

Pour la comparaison de toutes les listes entre elles je penses pas qu'on puisse y échapper (c'est le but même de l'exercice). On pourrait simplement imaginer ne pas refaire les comparaisons sur des listes identiques (ex. List1 == List7, alors plus besoin de comparer la List7 avec les listes List8 à ListN, on l'aura déjà fait via List1). Plus les "doublons" sont fréquents, plus le code sera rapide.

Pour la comparaison d'une liste avec une autre, à regarder si une comparaison sur des listes triées ne seraient pas plus rapide. En effet comparer deux listes triées c'est beaucoup plus rapide que comparer deux listes mélangés, et les algo de tris peuvent être particulièrement performants. A tester.

[pyriame]

Oui j'y est penser après coup , trier la liste et effacer les doublons est peut être une meilleur solution qu'un algo de comparaisons naïf à complexité quadratique (enfin je crois ... ).
Je vais m'orienter vers des algo de tri un peu plus sophistiquer et je reviendrais poster la réponse.

merci de ton aide

[jopopmk]

Autre chose que j'ai oublié : dans un test préliminaire, avant de comparer tous les éléments des deux listes, tu pourrais vérifier que celles-ci ont le même nombre d'éléments. Si ce n'est pas le cas pas besoin d'aller plus loin dans la comparaison.

Pour le tri je pensais simplement à utiliser celui fournit par .NET qui semble pas mal géré, extrait :

[..] Cette méthode utilise le Array.Sort méthode qui applique le tri approfondie comme suit :

• Si la taille de partition est moins de 16 éléments, il utilise un algorithme de tri d'insertion.
• Si le nombre de partitions est supérieure à 2 * LogN, où N correspond à la plage du tableau d'entrée, il utilise un algorithme de Heapsort.
• Sinon, il utilise un algorithme de tri rapide.

(source)

Après y'a plus qu'à comparer élément par élément, à partir du moment ou deux sont différents pas besoin d'aller plus loin : les listes sont différentes (on économise la comparaison des éléments restants).

[pyriame]

A minima je m'était fait un truc dans ce genre en me disant je vais utiliser le count de chaque liste, si déja y'en a aucun pareil c'est que y'a pas de doublon et problème résolu. Ensuite j'en ai trouvé (évidement... ) avec même Count mais qui sont pas des doublons! Alors en gros fainéant j'ai rajouté une condition avec le Sum de chaque liste ! Et ba même comme ça j'en ai trouvé
Du coup je me suis résolu a partir sur une VRAI solution à ce problème.
Ceci dit un test préliminaire sur le Count est peut être une bonne chose , faut juste que je voit si le temps de tous les passer en revu et d'en faire une liste de potentiellement doubloné est pas plus chronophage qu'un test de tri évolué.

Merci pour la source je vais regarder ce heapsort. J'était parti sur un "tri fusion" qui avait l'air très prometteur https://fr.wikipedia.org/wiki/Tri_fusion.

[jopopmk]

Vérifier la somme des valeurs me semble pas une bonne idée pour ce que tu cherches à faire. Ça va engendrer un parcours de chacune des listes pour un résultat peu probant. Par contre le test sur le nombre d'éléments peut être un bon épurage avant de mettre en branle la comparaison en "brut force" (il me semble que le Count est précalculé automatiquement lors de la création de/ajout d'élément à la List, donc pas de surcoût).

Autre optim' possible si tes données viennent d'une DB : utilise ton SGBD pour faire le tri.

Après y'a sûrement d'autres spécificités du .NET à prendre en compte, c'est là où ma signature prend tout son sens

[pyriame]

Pour la somme je pensais à ça histoire d'avoir un truc un peu discriminant mais bon c'est un écrémage de plus, c'est ni nécessaire ni suffisant en effet.

Je vais partir sur un test préliminaire avec Count des valeurs. Après ce 1er filtre je ferais une comparaison entre chaque liste (après les avoir trié).

Me reste a déterminer le predicator le plus judicieux pour ma comparaison . La somme c'est une mauvaise idée, donc il me reste quoi ? Comparaison des 1er terme de chaque liste, si identique passage au 2nd terme, si identique passage 3eme terme etc... jusqu'a la fin de la liste?

[jopopmk]

Yep, par contre il ne faut pas oublier de "taguer" les listes identiques, pour ne pas les refaire par la suite.

[pyriame]

le tagage ou pointage je sais pas faire (oui des lacunes ) ou peut être sans le savoir alors merci pour l'info je vais me renseigner .

Je fait beaucoup trop de truc au feeling et ça me fou dans la mer**...

La j'ai du bol, sur le programme j'avais 19 possibilité différentes de FIN, 6 erreurs levées, une chance ! Mais j'en aurais eu 18 je les aurais pas plus anticipé. Celle que j'ai soumis la en est une , la plus coriace, les 5 autres sont plus simple mais bon quand même. Y'a peut être encore 10 erreurs systémiques que j'ai pas vu/anticipé qui se révéleront dès que la table aura doublé...

Je cours après les bug d'exception Les tables de jonction c'est pratique SAUF quant l'absence de couple est AUSSI une information utiliser. Une matrice question/reponse avec 1 pour Oui et 0 pour NON c'est quand même plus simple à se représenter

Je code tous ça dans la semaine et je re-posterai la solution.

Encore merci

[jopopmk]

Pour avoir les id qui n'ont pas d'assoç il faut passer par un LEFT JOIN, mais c'est du SQL

[pyriame]

Et voila !
Je pense que ça peut encore être optimisé mais ça fait le job a savoir empêcher la poursuite du programme en cas de doublon dans une table de jonction.
Si il y a moyen de raccourcir je prend .
J'ai volontairement développé les truc pour bien voir le cheminement.

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
 
 List<List<int>> myList = new List<List<int>>();
                myList.Add(new List<int> { 3, 5, 7, 9 });
                myList.Add(new List<int> { 7, 4, 5, 9 });
                myList.Add(new List<int> { 5, 3, 9, 7 });
                //myList.Add(new List<int> { 5, 4, 9 });
 
                //Donne la 1ere liste de la liste qui est egale à myList[0]
                var Leprem = myList.First();
 
                // donnc le nombre d'item dans la 1ere liste
                int Lepremtaille = Leprem.Count();
 
                // classe la 1ere liste dans l'ordre décroissant
                var Lempremclass = Leprem.OrderByDescending(n => n).ToList();
 
                // créer une nouvelle liste de liste
                List<List<int>> ListRest = new List<List<int>>();
 
                // ajoute la 1ere liste classé par ordre décroissant dans cette nouvelle liste
                ListRest.Add(Lempremclass);
 
                // Pour chaque List en demarrant à myList[1]
                for (int i = 1; i < myList.Count; i++)
                    {
                     // si nbe d'element de la liste i suivante = nbe d'element de la 1ere liste 
                     if ( myList[i].Count() == Lepremtaille)
                        {
                        //On ajoute cette liste a la nouvelle liste "ListRest"
                        ListRest.Add(myList[i].OrderByDescending(n => n).ToList());                        
                        }
                    else
                        {
                        //On efface la liste complete et on sort de la boucle
                        ListRest.Clear();
                        break;
                        }                   
                   }
 
                // si la liste est egale a 0 on arrete
                if (ListRest.Count == 0)
                {
                    repetour.Text = "Toute les Liste n'ont pas le même nombre d'element";
                }
 
                // si la liste n'est pas égale a 0 on poursuit
                else
                {                   
                    // On a présent les listes avec même Count et trier dans l'ordre décroissant
 
                    //1ere liste de la liste qui est egale à myList[0]
                    var LaPremList = ListRest.First();
 
                    // Pour chaque List en demarrant à myList[1]
                    for (int i = 1; i < ListRest.Count; i++)
                    {
                        if (LaPremList.SequenceEqual(ListRest[i]))
                        {
                         // on continue
                        }
                        else
                        {
                            //On efface la liste complete et on sort de la boucle
                            ListRest.Clear();
                            break;
                        }
                    }
                    // si la liste est egale a 0 on arrete
                    if (ListRest.Count == 0)
                    {
                        repetour.Text = "Les listes n'ont pas les meme element";
                    }
                    else
                    {
                        repetour.Text = "OK";
                        Rita1.DataSource = ListRest.First();
                        Rita1.DataBind();
 
                    }
 
                }

[pyriame]

Je reviens un peu dessus avant de mettre résolu.

J'ai longuement hésité sur l’intérêt d'intercalé entre la comparaison des Count de chaque liste et la comparaison final de chaque item de list, une comparaison uniquement du premier item.

Cet espèce d'algo doit permettre de démasquer les doublons d'une liste de liste et même si sur 4 éléments la vitesse n'est pas franchement un problème, sur une table de jonction avec 35 000 ligne cela peut le devenir. Comme a priori il doit y avoir peut de doublon sur ma table, même sur une grosse list de list la méthode d’arrêt des que les count sont différent devrait me permettre de très rapidement interrompre le processus.

Néanmoins, en admettant quand même que sur une table de 35 000 ligne un count identique est quand même pas si rare, 1000 lignes au final à trier, mettre dans une nouvelle list puis comparer ça chiffre un peu question temps de calcul...

D’où cette interrogation, ne vaut il pas mieux coder un peu plus et rajouter une opération d’arrêt si le 1er élément d'une list est différent plutôt que de se lancer directement dans la comparaison?
Je connais rien de chez rien a l'estimation des ressources et du temps nécessaire pour chaque type de calcul mais si je peut optimiser le truc tout de suite plutôt que de revenir dessus je prend !

Encore merci de votre aide

[jopopmk]

Re,

si j'ai le temps entre midi et deux je te ferais un bout de code qui explique comment je vois le truc.

[jopopmk]

Alors voili voilou un gros pavé de code commenté, hésite pas à demander si un truc t'échappe :

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public static class Pyriame {
 
	// la classe représentant une association
	public class Association
	{
		// l'identifiant de référence
		public int		id_tab1 = 0;
		// la liste des identifiants associés
		public List<int>		id_tab2= new List<int>();
		// l'identifiant id_tab1 d'une liste d'associations ayant les mêmes id_tab2
		public int		id_same = 0;
 
		// une fonction de sérialisation pour vérifier
		public override string ToString() {
			string str = this.id_tab1.ToString() + " [" + this.id_same.ToString() + "] :";
			foreach (int tab2 in this.id_tab2)
				str += " " + tab2.ToString();
			return str + "\r\n";
		}
	}
 
	// la liste contenant les associations
	public static List<Association> Associations = new List<Association>();
 
	// la fonction de chargement des associations depuis la DB (dans mon cas j'utilise Excel)
	public static void LoadAssociations() {
		using (OleDbConnection cnx = new OleDbConnection("Provider =Microsoft.ACE.OLEDB.12.0;Data Source=C:\\Work\\visual\\winform\\asso.xlsx;Extended Properties=\"Excel 12.0 Xml;HDR=YES\"")) {
 
			// l'ordonnancement est fait par le SGBD via la requête
			OleDbCommand cmd = new OleDbCommand("SELECT * FROM [Asso$] ORDER BY id_tab1, id_tab2");
			cmd.Connection = cnx;
			cnx.Open();
 
			using (OleDbDataReader dr = cmd.ExecuteReader()) {
				Association curAsso = new Association();
				int curTab1 = 0;
				while (dr.Read()) {
					int tab1 = Convert.ToInt32(dr[0]);
					int tab2 = Convert.ToInt32(dr[1]);
 
					// si on change d'id_tab1 on crée une nouvelle association (cf. ORDER BY id_tab1)
					if (tab1 != curTab1) {
 
						// attention au cas 0, le premier passage dans l'algo ne nécessite pas de créer un nouvelle objet, ni d'ajouter le précédent à notre liste
						if (curTab1 != 0) {
							Pyriame.Associations.Add(curAsso);
							curAsso = new Association();
						}
						curAsso.id_tab1 = tab1;
						curAsso.id_tab2.Add(tab2);
						curTab1 = tab1;
 
					// sinon on ajoute l'id_tab2 à l'association en cours
					} else curAsso.id_tab2.Add(tab2);
				}
			}
		}
	}
 
	// la fonction qui va taguer les listes identiques
	public static void TagSameAssociations() {
		int assoCount = Pyriame.Associations.Count;
 
		// pour toutes les associations (pas besoin de faire la dernière)
		for (int i=0; i<assoCount -1; i++) {
 
			// si la liste "i" est déjà taguée pas besoin de comparer
			if (Pyriame.Associations[i].id_same == 0) {
 
				// que l'on compare avec toutes les autres associations qui arrivent après dans la liste
				for (int j=i+1; j<assoCount; j++) {
 
					// si les listes "i" et "j" ont le même nombre d'élément on compare pour de vrai
					if (Pyriame.Associations[i].id_tab2.Count == Pyriame.Associations[j].id_tab2.Count) {
						bool equal = true;
 
						// pour tous les éléments id_tab2 des deux listes
						for (int k=0; k< Pyriame.Associations[i].id_tab2.Count; k++) {
 
							// si on a un élément différent pas besoin d'aller plus loin
							if (Pyriame.Associations[i].id_tab2[k] != Pyriame.Associations[j].id_tab2[k]) {
								equal = false;
								break;
							}
						}
 
						// si on a comparé tous les éléments sans anicroche les listes sont identiques : on tag
						if (equal) Pyriame.Associations[j].id_same = Pyriame.Associations[i].id_tab1;
					}
				}
			}
		}
	}
 
	// une fonction d'affichage pour vérifier
	public static void ShowAssociations() {
		string str = "";
		foreach (Association asso in Pyriame.Associations)
			str += asso.ToString();
		MessageBox.Show(str);
	}
}

edit : j'ai mis la fonction de chargement pour montrer l'utilisation du ORDER BY en amont plutôt que par un tri en sus en aval, mais on pourrait imaginer, si ton cas s'y prête, à faire les comparaisons au moment de l'extraction des données, pour gagner un parcours. A voir tes besoins en optim'

[pyriame]

Sympas !
J'ai pas encore tous compris sur la logique du truc je vais le mettre dans VS pour voir un peu mieux le processus.
C'est beaucoup moins bordélique que mon code c'est certain

Je vais juste vérifier que Linq dispose des même appels qu'un SGBD classique . (Je passe les appel via une map de ma DB en réalité, Linq Entity).

Je testerai les 2 pour voir les différences de performance mais je me fais pas trop d'idée sur le résultat... Ton processus a l'air beaucoup plus minimaliste que le mien et je voit pas un appel a 200 000 inscription dans une list ou un dictionnaire comme le miens, ce qui n'est pas négligeable en terme de performance

merci beaucoup pour ton aide.

Je peut réellement mettre le topic comme "resolu" ce coup-ci

[jopopmk]

L'utilisation d'un ORM (Entity Framework dans ton cas) peut avoir une forte incidence sur les performances d'un programme,
mais de ce que j'ai lu sur le net il pourrait exister quelques optimisations dans son utilisation.
A creuser si les perf sont encore un souci.