Réimplémentation de LINQ to Objects : Partie 14 - « Distinct »

Je vais maintenant implémenter les opérateurs d'ensemble, en commençant par Distinct.

Distinct a deux surcharges qui diffèrent entre-elles de la plus simple des façons :

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source) 

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer)

Le but de l'opérateur est très simple : la séquence produite contient les mêmes éléments que la séquence d'entrée, sans les éléments dupliqués. Une séquence d'entrée telle que {0, 1, 3, 1, 5} produira en résultat la séquence {0, 1, 3, 5}. La seconde occurrence de « 1 » est supprimée.

Cette fois, j'ai vérifié et revérifié la documentation et dans ce cas, on peut vraiment considérer la première surcharge comme une version simplifiée de la seconde. Si vous ne précisez pas de comparateur d'égalité, le comparateur par défaut du type sera utilisé. Il en sera de même si vous passez une référence nulle comme comparateur. Le comparateur d'égalité par défaut d'un type peut être obtenu par la très utile propriété EqualityComparer<T>.Default.

Pour rappel , un comparateur d'égalité (représenté par l'interface IEqualityComparer<T>) peut réaliser deux choses :

• calculer le code de hachage pour un élément du type T ;
• comparer des éléments de type T deux à deux pour déterminer leur égalité.

Aucun besoin ici de fournir une quelconque notion d'ordre. L'interface IComparer<T> est faite pour cela bien qu'elle n'ait pas la possibilité de fournir un code de hachage.

Une remarque intéressante à propos de IEqualityComparer<T> est que la méthode GetHashCode() est supposée lever une exception si un argument null est fourni, mais dans la pratique, l'implémentation pour IEqualityComparer<T>.Default ne se comporte pas comme cela.

Tout cela mène à une question intéressante à propos de Distinct : comment doivent être gérés les éléments null ? Ce n'est documenté nulle part, mais en réalité, tant dans l'implémentation de LINQ to Objects que dans notre version simplifiée, une NullReferenceException est levée si vous utilisez un comparateur qui ne gère pas les null et qu'un élément null est présent. Notez que le comparateur d'égalité par défaut pour n'importe quel type (EqualityComparer<T>.Default) gèreles null.

Il existe encore d'autres aspects non documentés de Distinct. Tant l'ordre de la séquence résultante que le choix qui est effectué quant à l'élément retourné en cas d'égalité ne sont pas définis. Concernant l'ordre, c'est même explicitement non précisé. Extrait de la documentation : « La méthode Distinct renvoie une séquence non ordonnée qui ne contient pas de valeurs dupliquées ». Cependant, il existe une approche naturelle qui répond à ces deux questions. Distinct repose sur l'exécution différée (il ne lira pas la séquence d'entrée tant que vous ne commencerez pas à lire la séquence résultante), mais il « stream » également les résultats, d'une certaine manière : pour retourner le premier élément, il a uniquement besoin de lire le premier élément de la séquence d'entrée. D'autres opérateurs (tels que OrderBy) doivent lire toutes les données avant de fournir le premier résultat.

Quand vous implémentez Distinct de façon à ce qu'il ne lise pas plus de données que nécessaire, la réponse aux problèmes d'ordre et de choix d'éléments est évidente :

• la séquence résultante est dans le même ordre que la séquence d'entrée ;
• quand il y a plusieurs éléments égaux, celui qui apparaît le plus tôt dans la séquence d'entrée est celui qui est retourné dans la séquence résultat.

Rappelez-vous qu'il est parfaitement possible d'avoir des éléments considérés égaux par un comparateur particulier et qui ont l'air totalement différents quand ils sont observés sous un autre angle. L'exemple le plus simple pour illustrer cela est une comparaison de chaînes en ignorant la casse. En prenant en compte les règles ci-dessus, l'opérateur Distinct appliqué à {« ABC », « abc », « xyz »} avec un comparateur ne tenant pas compte de la casse fournit le résultat suivant : {« ABC », « xyz »}.

Tout ce qui a été décrit plus haut :).

Tous les tests se basent sur des séquences de chaînes par souci de clarté, mais j'utilise quatre comparateurs différents :

• le comparateur de chaînes par défaut (qui est un comparateur ordinal, sensible à la casse) ;
• le comparateur ordinal insensible à la casse ;
• un comparateur qui utilise l'identité des objets (qui traitera donc deux chaînes identiques, mais n'étant pas les mêmes objets, comme différentes) ;
• un comparateur qui ne gère pas les valeurs nulles.

Les tests ont comme prérequis que les aspects non documentés cités précédemment sont implémentés selon les règles que j'ai données. Cela signifie qu'ils sont hypersensibles dans le sens qu'une implémentation de Distinct qui met en œuvre tous les comportements documentés, mais qui retourne les éléments dans un ordre différent ne les réussira pas. Cela met en évidence un aspect intéressant des tests unitaires en général… qu'essayons-nous exactement de tester ? Dans notre cas, trois options me viennent à l'esprit :

• uniquement le comportement documenté : tout ce qui s'y conforme, même bizarrement, devrait passer ;
• le comportement LINQ to Objects : l'implémentation du framework devrait réussir tous les tests, tout comme notre implémentation ;
• le comportement connu (attendu) de notre implémentation : nous pouvons préciser que notre implémentation suivra les règles définies plus haut et au-delà du cadre des contrats documentés.

Dans des projets de production, ces différentes options sont valides en fonction des circonstances, selon ce qu'on essaye de faire exactement. Actuellement, il n'y a, à ma connaissance, aucune différence de comportement entre LINQ to Objects et Edulinq, bien que cela puisse évoluer plus tard, lors de l'optimisation.

Aucun des tests n'est particulièrement intéressant bien que je trouve intéressant le fait d'avoir dû implémenter une version délibérément fragile (mais valide) d'IEqualityComparer<T> de façon à tester complètement Distinct.

Je suis totalement confiant quant à implémenter la surcharge qui n'utilise pas de comparateur personnalisé en fonction de celle qui en utilise un. Nous avons deux possibilités pour définir le comparateur personnalisé qui sera utilisé dans l'appel délégué : nous pouvons passer null ou EqualityComparer<T>.Default, car leur comportement sera identique dans la seconde surcharge. J'ai décidé d'utiliser EqualityComparer<T>.Default par souci de clarté. Il n'est ainsi pas nécessaire pour quelqu'un qui lirait le code de la première surcharge de vérifier le comportement de la seconde surcharge pour comprendre ce qui sera fait.

Nous devons à nouveau utiliser l'approche du « bloc itératif privé » de façon à ce que les arguments puissent être évalués au plus tôt tout en permettant à la séquence résultante d'utiliser l'exécution différée. La méthode qui effectue réellement le travail utilise un HashSet<T> pour conserver une trace de tous les éléments qui ont déjà été retournés. Il reçoit un IEqualityComparer<T> dans son constructeur et la méthode Add ajoute un élément à l'ensemble s'il n'y en a pas déjà un équivalent et retourne une valeur booléenne qui stipule si l'élément a réellement été ajouté. Tout ce qu'il nous reste à faire, c'est parcourir la séquence d'entrée, appeler Add et fournir l'élément comme part de la séquence résultante si Add a retourné « true ». Facile !

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    return source.Distinct(EqualityComparer<TSource>.Default); 
} 
public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    if (source == null)  
    { 
        throw new ArgumentNullException("source"); 
    } 
    return DistinctImpl(source, comparer ?? EqualityComparer<TSource>.Default); 
} 
private static IEnumerable<TSource> DistinctImpl<TSource>( 
    IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    HashSet<TSource> seenElements = new HashSet<TSource>(comparer); 
    foreach (TSource item in source) 
    { 
        if (seenElements.Add(item)) 
        { 
            yield return item; 
        } 
    } 
}

Maintenant, que faire avec les null ? Eh bien, il semble que le HashSet<T> gère cela automatiquement, si le comparateur qu'il utilise le fait. Tant que le comparateur retourne la même clé de hachage à chaque fois qu'il reçoit un null, et qu'il considère null équivalent à null, null peut être présent dans la séquence. Sans Hashset<T> nous aurions eu une implémentation beaucoup moins élégante, surtout que Dictionary<TKey, Tvalue> n'accepte pas la valeur null comme clé.

Je suis franchement ennuyé par le manque de précision dans la documentation de Distinct. Devriez-vous vous fier à la règle de tri que j'ai fournie ici ? Je pense qu'en fait vous pouvez raisonnablement vous y fier, c'est le résultat le plus naturel de l'implémentation la plus évidente après tout. Je ne compterais pas sur le même résultat en utilisant un autre fournisseur LINQ, cependant. Par exemple, en récupérant les données d'une base de données, je ne serais absolument pas surpris de voir l'ordre changer. Et évidemment, le fait que la documentation précise explicitement que le résultat est non trié devrait vous dissuader de vous y fier.

Nous aurons à prendre des décisions similaires pour les autres opérateurs ensemblistes : Union, Intersect et Except. Eh oui, il est fort probable qu'ils utilisent également HashSet<T>…

Merci à Jon Skeet de m'avoir autorisé à traduire son article Reimplementing LINQ to Objetcs : Part 14 - Distinct.

Merci à Thomas Levesque (tomlev) pour sa relecture technique.

Merci à Claude Leloup pour la relecture orthographique de ce document.