Discussion :

[Johann7751]

Bonjour,

Dans mon application, je récupère des listes d'objets énormes (de 1 à 10 millions d'entités dans la liste)
Je cherche à récupérer une liste d'objets distincts, et que ce soit le plus performant possible.
Je compare mes objets entre eux en fonction d'une PK (plusieurs propriétés de mon objet)

Je connais une méthode, vu que je suis en C# 4.0, j'utilise la méthode Distinct de Linq To Object.
C'est extrêmement lent, c'est pourquoi je cherche une méthode alternative.
Voici comment je fais actuellement :

Ma classe représentant un objet et la classe "comparer de l'objet"

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
public class Article
	{
		public string ArtNr { get; set; }
		public short DLNr { get; set; }
		public int? BezNr { get; set; }
		public Boolean? KZSB { get; set; }
		public Boolean? KZMat { get; set; }
		public Boolean? KZAT { get; set; }
		public Boolean? KZZub { get; set; }
		public int? LosGr1 { get; set; }
		public int? LosGr2 { get; set; }
	}
 
    public class ArticleComparerPK : IEqualityComparer<Article>
    {
        public bool Equals(Article x, Article y)
        {
            if (x == null || y == null) return false;
            return Equals(x.ArtNr, y.ArtNr) && Equals(x.DLNr, y.DLNr);
        }
 
        public int GetHashCode(Article obj)
        {
            return obj.DLNr.GetHashCode();
        }
    }

Code métier où je fais mon distinct sur ma liste

Code :

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

1
2
3
ListEntities = new List<Article>();
// ... récupération des enregistrements dans ma liste ..
ListEntities = ListEntities.Distinct(new ArticleComparerPK()).ToList();

Voilà, pour info dans ce cas, pour cette liste d'objets, j'ai 3 500 000 objets, et ça me prends 46min.

Comment faire pour être plus performant ?

[Bluedeep]

Bonjour

Dans ce genre de cas, peut être faire faire le boulot par le SGBD qui est surement mieux outillé pour cela (sous réserve de plus d'info concernant le fonctionnel de l'appli ).

[Johann7751]

J'ai changé ma clé de hachage :

Code :

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

1
2
3
4
        public int GetHashCode(Article obj)
        {
            return obj.DLNr.GetHashCode() ^ obj.ArtNr.GetHashCode();
        }

Le Distinct passe de 46min à .... 15sec !
Ça me va.

Tout ce qui va suivre n'est que supposition mais :
Je comprends pas tout sur le principe de la clé de hachage mais je pense que le comparer s'en sert pour faire des "groupes" et que ça va comparer les éléments dans ces "groupes" les un après les autres.
Là dans ma liste j'avais 3 500 000 données, et en séparant uniquement par
DLNr, j'avais 450 "groupes". (450 DLNr différents)
En moyenne 7778 entités par groupe. Sauf que j'avais un groupe à 200 000 entités, je pense que comparer une à une 200 000 entités, c'est très long.
Je pense qu'il faut arriver à faire des "groupes" équitablement répartis pour avoir de bonnes performances quelque chose comme ça..
Si quelqu'un sait expliquer le principe je suis preneur..

[MaximePalmisano]

Le hashcode est un nombre qui va permettre de stocker/retrouver une entrée rapidement.

Le soucis est le suivant: On sait qu'à une valeur correspond un seul hashcode, mais plusieurs hashcodes peuvent retourner la même valeur.

Lorsque l'on veut stocker une valeur dans un dictionnaire par exemple (HashMap en Java, ça porte bien son nom), on utilise le hashcode de la clé pour le stocker. Ainsi, lorsque l'on cherche un objet, on hash la clé et on va chercher à l'endroit donné. L'opération est très rapide.

Maintenant, si l'on stocke un deuxième objet dont la clé est différente mais qui possède le même hashcode, on va vouloir le stocker au même endroit. C'est ce qui s'appelle une collision.

Il y a plusieurs implémentation pour gérer les collisions. On peut choisir de le stocker dans la case suivante, au même endroit, etc ...

Du coup, si tu n'as que 200 hashcodes différents, la recherche arrivera rapidement à déterminer dans quel "groupe" se trouve ton entrée. Par contre, vu qu'il y aura beaucoup d'éléments avec le même hashcode, la recherche devra comparer les objets un par un pour trouver le bon.

Avec un hashcode plus précis, tu as plus de groupes. Du coup, dès le calcul du hashcode, tu peux éviter tous les éléments dont le hashcode est différent. Il te reste beaucoup moins d'objets à comparer un à un.

Tu peux trouver beaucoup d'article qui parlent de la gestion des collisions dans les implémentations de dictionnaires/table de hashage, wikipedia (même la VF) est assez bien fournie: http://fr.wikipedia.org/wiki/Table_de_hachage

Il est connu que les hashcodes ont une meilleure répartition lorsque l'on utilise XOR car il disperse plus les bits que les autres opérateurs (Cf tables de AND/OR/XOR).

Je me rappelle aussi d'un article qui disait que l'on avait un encore meilleur résultat en utilisant des multiplications par des nombres premiers (37 et 13 de mémoire). Ca donnait quelque chose dans le genre:

Code :

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

1
2
3
4
5
 
public int GetHashCode()
{
    return 37 * (13 * champ1.GetHashCode()) ^ (13 * champ2.GetHashCode());
}

EDIT: J'ai retrouvé le lien, il s'agit de Jon Skeet (MVP, Auteur de C# in depth) qui poste sur SO http://stackoverflow.com/questions/8...of-two-numbers

[Babyneedle]

J'ajoute simplement aux commentaires émérites existants que cette façon de procéder risque de monopoliser la mémoire vive de l'environnement qui va rouler le processus.

Dans un environnement de production, ça pourrait causer des problèmes et c'est pour cela que ce genre d'opération devrait se faire au niveau de la base de données. S'il n'y en a pas, c'est un bon indice qu'il en faudrait une.

Règle d'or: toujours éliminer tout donnée superflue avant de la transporter en mémoire.

[MaximePalmisano]

En effet, je répondais juste sur la question du hashcode. Il est vrai qu'il est étrange de ne pas faire ça en amont sur la DB...

[Johann7751]

Merci pour les explications sur la clé de hachage.
L'article wikipedia est pas mal pour comprendre aussi.

Donc avec ma clé de hachage basée sur DLNr uniquement, j'avais 450 groupes de données (alvéoles), mais beaucoup de données dans certaines alvéoles (+ 200 000)
Le fait d'avoir plus d'une seule donnée dans une alvéole est appelé "collision" si j'ai bien compris.
Ensuite dans l'article, ils parlent de plusieurs façons de procéder, pour la recherche d'une valeur dans une alvéole dont la recherche linéaire.
C'est ça qui prend du temps.
Par contre je pense qu'il ne faut pas non plus aucune collision (1 alvéole = 1 donnée), sinon c'est la recherche de l'alvéole qui prend du temps je suppose.

Pour revenir à ce que je fais ici et pourquoi je n'utilise pas de base de données, ici en fait il s'agit de récupérer les données de gros fichiers textes pour les insérer en base de données ensuite justement.

Malgré tout la liste ne doit pas être trop grosse non plus pour faire le distinct
sinon on se tape une exception telle que celle ci :

Code :

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

1
2
3
4
5
6
7
Une exception de type 'System.OutOfMemoryException' a été levée.
 
   à System.Linq.Set`1.Resize()
   à System.Linq.Set`1.Find(TElement value, Boolean add)
   à System.Linq.Enumerable.<DistinctIterator>d__81`1.MoveNext()
   à System.Collections.Generic.List`1..ctor(IEnumerable`1 collection)
   à System.Linq.Enumerable.ToList[TSource](IEnumerable`1 source) ...

Sur un système 64 bits, en C# 4.0, la limite max d'un objet est 2Go
En 4.5 c'est plus (mais je ne suis pas en 4.5), ils introduisent gcAllowVeryLargeObjects.
http://bhrnjica.net/2012/07/22/with-...-2-gb-is-over/

[Babyneedle]

Bonjour,

Ton scénario implique d'éliminer les doublons entre plusieurs fichiers texte ou chaque fichier texte est en soit un univers clos?

[Bluedeep]

Pour revenir à ce que je fais ici et pourquoi je n'utilise pas de base de données, ici en fait il s'agit de récupérer les données de gros fichiers textes pour les insérer en base de données ensuite justement.

Euh.. oui; dans ce cas, typiquement je procéderais à un import massif "en vrac" dans une/des tables temporaires et je traiterais tout avec dans la base (un SGBD c'est fait pour cela, justement ....)

[Johann7751]

Bonjour,

Ton scénario implique d'éliminer les doublons entre plusieurs fichiers texte ou chaque fichier texte est en soit un univers clos?

Chaque fichier texte est un univers clos.
(Je peux trouver des doublons dans un même fichier texte, mais jamais entre deux fichiers textes)

Dans mon cas, sur mon système 32 bits, je peux pas traiter des fichiers de + de 500Mo.
L'instanciation de ma liste d'objet puis le distinct sur cette liste me provoque une OutOfMemoryException.

La solution de BlueDeep est la plus adaptée en fait :
1. Charger les données du fichiers en base de données dans une table temporaire.
2. Faire le distinct en base de données
3. Insérer les données dans la vraie base de données.

[Babyneedle]

Ça s'appelle un ETL...

Tu aurais pu aussi utiliser des regular expressions puisque chaque fichier est indépendant.

Bonne chance.