Distinct Elements dans List<T>

Bonjour

J'ai une List<T> contenant des elements de type Machin

Cette liste est chargée triée par nom

Code:

---

1 2 3 4 5

class Machin { int Id; string nom; }

---

Un Id peut avoir plusieurs noms, donc plusieurs element dans la liste

Je voudrais compter le nombre d'ID distinct
Une methode est evidemment de trier par id et de parcourir la liste

Question 1
Si je ne veux pas casser la sequence originale, je dois travailler sur une copie de la liste, comment faire une copie de List<T> a part dans une boucle : je n'ai pas vu de methode clone ou copy ?
Je sais on va me dire tu n'a qu'a retrier par nom apres : ca ne peut pas convenir car je ne dispose plus de la clef ayant produit le tri original !

Question 2
J'ai vu une methode distinct dans la la List<T> mais aucun exemple pratique peut elle servir dans ce cas ?

Tu peux utiliser LINQ to Objects pour faire ça, c'est tout simple (si tu es en .NET 3.5)

dans la serie brutasse:

Code:

---

1 2 3 4 5 6 7

List<int> ids = new List<int>(); foreach (Machin tmp in maListeOuJeVeuxCompterLesIds){ if (!ids.Contains(tmp.Id)){ ids.Add(tmp.Id); } }

---

et dans id.Count, tu as ton nombre d'ids :mrgreen:


mais y'a surement plus propre ;)

Avec .Net 3.5, un HashSet auquel tu files une fonction d'égalité qui va bien ferait l'affaire.

En C#2, je simule les Set avec des dico dont j'ignore les valeurs :

Code:

---

1 2 3

Dictionary<int, int> dico = new Dictionary<int, int>(); // un Dico<int, Choucroute> serait identique foreach(Machin m in listeMachins) dico[m.Id] = 0;

---

Là, t'as le compte avec dico.Count et les ids avec dico.Keys (non trié ceci dit, pour que ce soit trié il aurait fallu un SortedDictionary).

J'ai bouleversifié les perfs d'un projet dont j'ai hérité en remplaçant les codes style if (!contains) then add en utilisant des dicos. Une insertion et un accès en O(1), ça se sent.
Les dicos, c'est bien.

Merci Merci

3 reponses .... 3 solutions 8O

La solution de pvialatte :aie: ca effectivement j'evite comme la peste !
La solution de SaumonAgile : oui je suis en 3.5, mais j'ai jamais utilisé Linq et ta reponse ne me permet pas vraiment de voir si ce serait simple ou pas
La solution de Guulh : me semble séduisante, je n'ai jamais utilisé de dictionnaire non plus et je ne sais pas vraiment ou cet abnimal s'inscrit entre les listes, les collections, les array etc..

De mon expérience en C, je faisait toutes ces choses avec des tableaux de structures ou des tableaux de pointeurs, les pointeurs et les structure, c'etait mon quotidien favori

Je vais essayer de voir ce que c'est qu'un dictionnaire

Reste toujours deux interrogation

1- Peut on faire facilement une copie de liste
2- Que permet en pratique la methode distinct dans une Liste ?

Oups j'avais pas bien vu 8O

4 Solutions !!
2 pour Guulh : je n'avais pas vu la suggestion du Hashset

J'ai jamais essayé non plus mais ca me semble moins pertinent car tant qu'a faire c'est bien aussi de recuperer d'une maniere ou d'une autre la liste unique des Id triée !

Bonjour

Bon j'ai essayé de regarder les dictionary, j'avoue que j'ai pas encore bien capté comment ca fonctionnait ni meme comment l'utiliser

Pour ceux qui ont de la patience avec moi, je vais expliquer comment je l'aurait fait en C de la maniere la plus performante

1- Allouer un tableau de pointeur sur mes srtructures machin
2- Trier le tableau de pointeur (pas les structures) : c'est l'avantage du C, on peut avoir plusieurs tri sur le meme tableau en utilisant des tableau de pointeurs, en plus c'est extremement performant car on ne trie que des pointeurs (pas de move de data)
3- Parcours des pointeurs pour Count des ID different
4- Si necessaire allouer un tableau d'ID pour stocker la liste triée des ID distincts

Quel serait le meilleur equivallant en C# ?

Pour reviendre sur les solutions precedentes :

en 3.5 -> HashSet

Code:

---

1 2 3

HashSet<int> idSet = new HashSet<int>(); foreach (Machin tmp in maListeOuJeVeuxCompterLesIds)idSet.Add(tmp.Id)

---

En Linq

Code:

---

1 2 3

var nbIds= (from m in maListeOuJeVeuxCompterLesIds select m.Id).Distinct().Count();

---

et avec les dicos, tu as la solution de Guulh

Apres, pour rire, il faudrait faire un ch'tit test de perfs entre les solutions...mais a moins de bosser avec quelques million d'enregistrements, je pense que ca doit pas trop changer...

Citation:

---

Envoyé par olibara

J'ai jamais essayé non plus mais ca me semble moins pertinent car tant qu'a faire c'est bien aussi de recuperer d'une maniere ou d'une autre la liste unique des Id triée !

---

Ca depend quel est ton besoin precis, et de la volumetrie.
Si tu veux juste l'ensemble des IDs (ou le nb d'elemts distincts), un HashSet (ou Linq To Objets, mais je connais pas), ou mon pis-aller a base dico est le plus simple et surtout le plus performant.
Si tu veux que la liste soit triee, tu peux par exemple creer une liste avec ce set et la trier.

Mais tout ceci doit etre tres simplifie avec Linq. Renseigne-toi :)

Citation:

---

Envoyé par pvialatte

Apres, pour rire, il faudrait faire un ch'tit test de perfs entre les solutions...mais a moins de bosser avec quelques million d'enregistrements, je pense que ca doit pas trop changer...

---

Euh, si, quand meme :) Un code style if (!Contains) Add... est en O(n^2) pour une liste, ce qui est tres rapidement couteux. Rien que sur une liste de 10 000 elements, la difference est sensible.

Je sais pas si ça répond à ce que tu cherches

Code:

---

1 2 3 4

var req = from liste in listeElements group liste by liste.Nom into g select new { NbElements = g.Count() };

---

Salut a tous

Merci pour votre motivation a proposer des idées


Je vais essayer de faire une synthese

1- Hashet : sans doute tres performant, sans doute aussi un peu gourmand en memoire mais pas de resultat trié donc j'écarte a priori
2- Dico : ca doit a mon avis approcher ma solution de tableau de pointeur en C mais je connais pas je dois d'abord essayer de comprendre
3- Linq sans doute la solution la plus "moderne" merci a Harz62 de nous donner une petite demo qui doit faire plaisir aux amateurs sql mais je pense que pour faire ce que je veux c'est un group by Id que je dois faire
4- Je rejoins guulh dans sa reponse a pvialatte : NE JAMAIS sous estimer l'impact sur les performance le languages actuels font trop souvent oublier l'aspect "mecanique interne" et apres quelques semaines (ou mois) de developpement on finit par pleurer a chercher pourquoi tout est si lent en prod et on est souvent reparti pour quelques semaines de redesign. Donc autant ne pas le negliger au départ !

Code:

---

1 2 3

var req = from liste in listeElements group liste by liste.Id into g select new { NbElements = g.Count() };

---

Citation:

---

Envoyé par olibara

4- Je rejoins guulh dans sa reponse a pvialatte : NE JAMAIS sous estimer l'impact sur les performance

---

Euh...oui, et ?

;)

Je parlais pas de la solution avec la liste, mais des hash/dico/linq...

Linq et HashSet sont specifiques 3.5, les dicos existent en 2.0

Loin de moi l'idée de balancer des algos avec des O en exponentiel :mouarf:

Ceci dit, je n'adhere qu'a 80%, vu que le but, c'est quand meme, dans l'ordre, Make it work, make it right, make it fast ;)

Citation:

---

Envoyé par olibara

4- Je rejoins guulh dans sa reponse a pvialatte : NE JAMAIS sous estimer l'impact sur les performance le languages actuels font trop souvent oublier l'aspect "mecanique interne" et apres quelques semaines (ou mois) de developpement on finit par pleurer a chercher pourquoi tout est si lent en prod et on est souvent reparti pour quelques semaines de redesign. Donc autant ne pas le negliger au départ !

---

Euh... le probleme de perf n'a aucun lien avec la "mecanique interne" de C#, ni de sa plus grande abstraction, qui masquant une complexite reelle par une syntaxe allegee, menerait a du code potentiellement moins performant.

.Net fournit un certain nombre de conteneurs (comme C++ d'ailleurs, ce n'est pas une question de langage manage ou pas mais une question de librairie bien fichue), satisfaisant des besoins precis. la liste a une fonction Add en o(1), une insertion en o(n), une recherche en o(n), mais un coup memoire limite. Le dico a un acces et une insertion en o(1), mais n'a pas de notion d'ordre (il se base sur des IEqualer et pas des IComparer pour gerer ses cles), tout comme le HashSet qui en est une variation.

'fin ce que je veux dire, c'est que les conteneurs qui te conviendront dependent de ton besoin. Avoir l'ensemble distinct des ids est une problematique. Avoir l'ensemble trié des ids en est une autre. Pour des faibles volumetries, des manips sur des lists suffisent dans tous les cas.

Merci guulh et Pvialatte

Je suis tout a fait d'accord avec vous deux

Code:

---

Make it work, make it right, make it fast

---

Facile a adherer, c'est ma maniere d'avancer

Pour ce que dit guulh; d'accord aussi, mais ce que j'exprime c'est que je n'ai AUCUNE connaissance sur la maniere interne dont sont gérés les liste, les dico, etc les hashset ca je peux deviner

C'est le defaut des couches d'abstraction offerte par le language : ca marche mais rare sont ceux qui savent vraiment comment
Donc le choix se fait generalement en fonction de la facilité rarement en fonction de l'efficacité ou de la pertinence !

Sur le sujet actuel, la syntaxe de linq est probablement la plus concise mais on la connait encore mal et ne sait rien des performances

Admetons que je travaille avec des liste, je ne sais toujours pas comment
a) faire une copie rapide d'une liste
b) a quoi sert le distinct

Quelqu'un le sait ?:?8O

Pour le moment j'ai donc bricolé en :
1- recopiant la liste en parcourant les eléments un a un : :aie: ABSURDE alors qu'on peut faire un clone et copy d'une DataTable ou qu'en C on peut faire un simple memmove ou memcopy
2- Tri de la liste temporaire
3- Comptage sur la liste triée et chargement d'une liste des distinct

Citation:

---

Envoyé par olibara

Donc le choix se fait generalement en fonction de la facilité rarement en fonction de l'efficacité ou de la pertinence !

Sur le sujet actuel, la syntaxe de linq est probablement la plus concise mais on la connait encore mal et ne sait rien des performancest

---

D'ou le but du proto rapide ;)

Sur ma becane...

trois fonctions

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

static int CountLinq(List<Machin> list){ return (from m in list select m.Id).Distinct().Count(); }   static int CountHash(List<Machin> list){ var idSet = new HashSet<int>(); foreach (Machin tmp in list)idSet.Add(tmp.Id);   return idSet.Count; }   static int CountDico(List<Machin> list){ var dico = new Dictionary<int, int>(); foreach (Machin tmp in list) dico[tmp.Id] = 0;   return dico.Keys.Count; }

---

une liste list de trois millions de Machin, avec des Id de 0 a 2999999
une liste listRed de trois millions de Machin, avec des Id de 0 a 9

je passe les 3 fonctions...

Hash -> list : 00:00:01.6 , listRed : 00:00:00.25
Dico -> list : 00:00:01.8 , listRed : 00:00:00.25
Linq -> list : 00:00:02 , listRed : 00:00:00.36

Et juste pour le fun, un petit test avec des listes toutes simples...

a 10 000 elements, on a les memes performances que les Hash/Dico/Linq a 3 000 000
a 100 000, list : 43 secondes; listRed : 00:00:00.015
a 1 000 000, list : pas essaye :aie:; listRed : 00:00:00.15

Citation:

---

b) a quoi sert le distinct

---

Citation:

---

Envoyé par MSDN

Retourne des éléments distincts d'une séquence et utilise le comparateur d'égalité par défaut pour comparer les valeurs.

---

Cela permet donc d'obtenir un énumérateur sur les éléments distincts présents dans une liste (et tout ce qui implémente IEnumerable au passage je pense), en utilisant le comparateur d'égalité pour définir ce qui est distinct et ce qui ne l'est pas (pour les classes perso).

Concernant les performances, certains semblent confondre optimisation et efficacité. Je rappelle pour ceux qui auraient oublié que l'optimisation prématurée est une des plus mauvaises choses qui peuvent arriver dans un projet.
Le projet commence par le design, c'est là qu'on choisit l'architecture la plus efficace. Une des dernières phases est l'optimisation. Il ne faut pas se tromper, si ce que vous appelez "optimisation" oblige à revoir le design complet, c'est qu'il y a eu une erreur à la conception. Mais ce n'est pas vraiment de l'optimisation, c'est corriger le design pour qu'il soit efficace. Dans ce cas là, le problème vient du fait que les critères d'acceptation en matière de performance n'ont pas été pris en compte lors de la conception.
L'optimisation c'est réorganiser des instructions pour qu'elles puissent être parallélisées (par exemple), mais soyons honnêtes dans la plupart des cas, l'optimisation n'est pas de gagner quelques cycles CPU, c'est surtout d'optimiser les entrées/sorties (DB, File System, Network, etc).

Pour SaumonAgile

Tu a raison !
Mais je prefere ne pas ouvrir un debat sur le sujet il est vaste et les confusions entre design, besoin, demande, performance, efficacité sont plus que nombreuses

Comme dirait Albert Tomlev :

La théorie, c'est quand on sait tout et que rien ne fonctionne.?
La pratique, c'est quand tout fonctionne et que personne ne sait pourquoi...............

Merci Stormimon

Code:

---

1 2	Envoyé par MSDN Retourne des éléments distincts d'une séquence et utilise le comparateur d'égalité par défaut pour comparer les valeurs.

---

Merci j'avais lu ca aussi

Et je pense meme qu'on peut lui donner n'importe quel comparer maison

Mais d'apres ce que tu lis là crois tu que ca peut peut me rendre la liste des ID distinct de ma liste ?

A mon avis non