Envelopper un délégué dans un IEqualityComparer

https://stackoverflow.com/questions/98033

01-07-2019
|

Question

Plusieurs fonctions Linq.Enumerable utilisent un IEqualityComparer<T>. Existe-t-il une classe d’emballage qui adapte un delegate(T,T)=>bool pour implémenter Dictionary? Il est assez facile d’en écrire un (si vous ignorez les problèmes de définition d’un hashcode correct), mais j'aimerais savoir s’il existe une solution prête à l'emploi.

Plus précisément, je souhaite définir des opérations sur <=> s, en utilisant uniquement les touches pour définir l'appartenance (tout en conservant les valeurs en fonction de règles différentes).

La solution

Habituellement, je résoudrais cela en commentant @Sam sur la réponse (j'ai apporté quelques modifications au message d'origine pour le nettoyer un peu sans modifier le comportement.)

Ce qui suit est mon riff de @ La réponse de Sam , avec un correctif critique [IMNSHO] à la politique de hachage par défaut: -

class FuncEqualityComparer<T> : IEqualityComparer<T>
{
    readonly Func<T, T, bool> _comparer;
    readonly Func<T, int> _hash;

    public FuncEqualityComparer( Func<T, T, bool> comparer )
        : this( comparer, t => 0 ) // NB Cannot assume anything about how e.g., t.GetHashCode() interacts with the comparer's behavior
    {
    }

    public FuncEqualityComparer( Func<T, T, bool> comparer, Func<T, int> hash )
    {
        _comparer = comparer;
        _hash = hash;
    }

    public bool Equals( T x, T y )
    {
        return _comparer( x, y );
    }

    public int GetHashCode( T obj )
    {
        return _hash( obj );
    }
}

Autres conseils

Sur l'importance de `GetHashCode`

D'autres personnes ont déjà fait remarquer que toute implémentation IEqualityComparer<T> personnalisée devrait réellement inclure une Distinct méthode ; mais personne n'a pris la peine d'expliquer pourquoi en détail.

Voici pourquoi. Votre question mentionne spécifiquement les méthodes d'extension LINQ; presque tous dépendent du code de hachage pour fonctionner correctement, car ils utilisent des tables de hachage en interne pour plus d'efficacité.

Prenez Equals , par exemple. Considérez les implications de cette méthode d’extension si elle n’utilisait qu'une List<Value> méthode. Comment déterminez-vous si un élément a déjà été numérisé dans une séquence si vous n’avez que Comparer<T>? Vous énumérez l'ensemble des valeurs que vous avez déjà examinées et recherchez une correspondance. Cela se traduirait par Value l'utilisation du pire des algorithmes O (N ²) au lieu d'un algorithme O (N)!

Heureusement, ce n'est pas le cas. Name n'utilise pas simplement GroupBy; il utilise aussi HashSet<T>. En fait, cela absolument ne fonctionne pas correctement sans un Dictionary<TKey, List<T>> qui fournit un > correct. Vous trouverez ci-dessous un exemple artificiel illustrant ceci.

Disons que j'ai le type suivant:

class Value { public string Name { get; private set; } public int Number { get; private set; } public Value(string name, int number) { Name = name; Number = number; } public override string ToString() { return string.Format("{0}: {1}", Name, Number); } }

Maintenant, disons que j'ai un Func<T, TKey> et que je veux trouver tous les éléments avec un nom distinct. C'est un cas d'utilisation parfait pour Func<T, object> l'utilisation d'un comparateur d'égalité personnalisé. Utilisons donc la keyExtractor classe de réponse d'Aku :

var comparer = new Comparer<Value>((x, y) => x.Name == y.Name);

Maintenant, si nous avons un groupe d'éléments where TKey : IEquatable<TKey> avec la même propriété object.Equals, ils doivent tous être réduits en une valeur renvoyée par object, n'est-ce pas? Voyons voir ...

var values = new List<Value>(); var random = new Random(); for (int i = 0; i < 10; ++i) { values.Add("x", random.Next()); } var distinct = values.Distinct(comparer); foreach (Value x in distinct) { Console.WriteLine(x); }

Sortie:

x: 1346013431 x: 1388845717 x: 1576754134 x: 1104067189 x: 1144789201 x: 1862076501 x: 1573781440 x: 646797592 x: 655632802 x: 1206819377

Hmm, ça n'a pas marché, n'est-ce pas?

Qu'en est-il de IEquatable<TKey> ? Essayons ça:

var grouped = values.GroupBy(x => x, comparer); foreach (IGrouping<Value> g in grouped) { Console.WriteLine("[KEY: '{0}']", g); foreach (Value x in g) { Console.WriteLine(x); } }

Sortie:

[KEY = 'x: 1346013431'] x: 1346013431 [KEY = 'x: 1388845717'] x: 1388845717 [KEY = 'x: 1576754134'] x: 1576754134 [KEY = 'x: 1104067189'] x: 1104067189 [KEY = 'x: 1144789201'] x: 1144789201 [KEY = 'x: 1862076501'] x: 1862076501 [KEY = 'x: 1573781440'] x: 1573781440 [KEY = 'x: 646797592'] x: 646797592 [KEY = 'x: 655632802'] x: 655632802 [KEY = 'x: 1206819377'] x: 1206819377

Encore une fois: cela n'a pas fonctionné.

Si vous y réfléchissez, il serait logique que TKey utilise un <=> (ou un équivalent) en interne et que <=> utilise quelque chose comme un <=> en interne. Cela pourrait-il expliquer pourquoi ces méthodes ne fonctionnent pas? Essayons ceci:

var uniqueValues = new HashSet<Value>(values, comparer); foreach (Value x in uniqueValues) { Console.WriteLine(x); }

Sortie:

public class KeyEqualityComparer<T, TKey> : IEqualityComparer<T> { protected readonly Func<T, TKey> keyExtractor; public KeyEqualityComparer(Func<T, TKey> keyExtractor) { this.keyExtractor = keyExtractor; } public virtual bool Equals(T x, T y) { return this.keyExtractor(x).Equals(this.keyExtractor(y)); } public int GetHashCode(T obj) { return this.keyExtractor(obj).GetHashCode(); } } public class StrictKeyEqualityComparer<T, TKey> : KeyEqualityComparer<T, TKey> where TKey : IEquatable<TKey> { public StrictKeyEqualityComparer(Func<T, TKey> keyExtractor) : base(keyExtractor) { } public override bool Equals(T x, T y) { // This will use the overload that accepts a TKey parameter // instead of an object parameter. return this.keyExtractor(x).Equals(this.keyExtractor(y)); } }

Ouais ... commence à avoir un sens?

Espérons que ces exemples montrent clairement pourquoi il est si important d'inclure un <=> processus approprié dans toute <=> mise en œuvre.

Réponse originale

Développement de la réponse d'Orip :

Quelques améliorations peuvent être apportées ici.

Tout d'abord, je prendrais un <=> au lieu de <=>; cela empêchera la mise en boîte des clés de type valeur dans le <=> réel lui-même.

Deuxièmement, j'ajouterais une contrainte <=>; cela empêchera la boxe dans l'appel <=> (<=> prend un paramètre <=>; vous avez besoin d'une implémentation <=> pour prendre un paramètre <=> sans le mettre en boîte). Clairement, cela peut poser une restriction trop sévère, vous pouvez donc créer une classe de base sans la contrainte et une classe dérivée avec elle.

Voici à quoi pourrait ressembler le code résultant:
<*>

Lorsque vous souhaitez personnaliser la vérification de l'égalité, vous souhaitez définir les clés à comparer, et non la comparaison elle-même, 99% du temps.

Il pourrait s'agir d'une solution élégante (concept de la méthode de tri par liste de Python .

Utilisation:

var foo = new List<string> { "abc", "de", "DE" }; // case-insensitive distinct var distinct = foo.Distinct(new KeyEqualityComparer<string>( x => x.ToLower() ) );

La KeyEqualityComparer classe:

public class KeyEqualityComparer<T> : IEqualityComparer<T> { private readonly Func<T, object> keyExtractor; public KeyEqualityComparer(Func<T,object> keyExtractor) { this.keyExtractor = keyExtractor; } public bool Equals(T x, T y) { return this.keyExtractor(x).Equals(this.keyExtractor(y)); } public int GetHashCode(T obj) { return this.keyExtractor(obj).GetHashCode(); } }

Je crains qu'il n'y ait pas de tel emballage hors de la boîte. Cependant, il n’est pas difficile d’en créer un:

class Comparer<T>: IEqualityComparer<T> { private readonly Func<T, T, bool> _comparer; public Comparer(Func<T, T, bool> comparer) { if (comparer == null) throw new ArgumentNullException("comparer"); _comparer = comparer; } public bool Equals(T x, T y) { return _comparer(x, y); } public int GetHashCode(T obj) { return obj.ToString().ToLower().GetHashCode(); } } ... Func<int, int, bool> f = (x, y) => x == y; var comparer = new Comparer<int>(f); Console.WriteLine(comparer.Equals(1, 1)); Console.WriteLine(comparer.Equals(1, 2));

Comme la réponse de Dan Tao, mais avec quelques améliorations:

S'appuie sur EqualityComparer<>.Default pour effectuer la comparaison réelle de manière à éviter la mise en boîte des types de valeur (struct s) ayant implémenté IEquatable<>.

Comme null.Equals(something) utilisé, il n'explose pas le IEqualityComparer<>.

Fournit un wrapper statique autour de <=> qui aura une méthode statique pour créer l’instance de comparateur - facilite les appels. Comparer

Equality<Person>.CreateComparer(p => p.ID);

avec

new EqualityComparer<Person, int>(p => p.ID);

Ajout d'une surcharge pour spécifier <=> pour la clé.

La classe:

public static class Equality<T> { public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector) { return CreateComparer(keySelector, null); } public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector, IEqualityComparer<V> comparer) { return new KeyEqualityComparer<V>(keySelector, comparer); } class KeyEqualityComparer<V> : IEqualityComparer<T> { readonly Func<T, V> keySelector; readonly IEqualityComparer<V> comparer; public KeyEqualityComparer(Func<T, V> keySelector, IEqualityComparer<V> comparer) { if (keySelector == null) throw new ArgumentNullException("keySelector"); this.keySelector = keySelector; this.comparer = comparer ?? EqualityComparer<V>.Default; } public bool Equals(T x, T y) { return comparer.Equals(keySelector(x), keySelector(y)); } public int GetHashCode(T obj) { return comparer.GetHashCode(keySelector(obj)); } } }

vous pouvez l'utiliser comme ceci:

var comparer1 = Equality<Person>.CreateComparer(p => p.ID); var comparer2 = Equality<Person>.CreateComparer(p => p.Name); var comparer3 = Equality<Person>.CreateComparer(p => p.Birthday.Year); var comparer4 = Equality<Person>.CreateComparer(p => p.Name, StringComparer.CurrentCultureIgnoreCase);

Personne est une classe simple:

class Person { public int ID { get; set; } public string Name { get; set; } public DateTime Birthday { get; set; } }

public class FuncEqualityComparer<T> : IEqualityComparer<T> { readonly Func<T, T, bool> _comparer; readonly Func<T, int> _hash; public FuncEqualityComparer( Func<T, T, bool> comparer ) : this( comparer, t => t.GetHashCode()) { } public FuncEqualityComparer( Func<T, T, bool> comparer, Func<T, int> hash ) { _comparer = comparer; _hash = hash; } public bool Equals( T x, T y ) { return _comparer( x, y ); } public int GetHashCode( T obj ) { return _hash( obj ); } }

Avec extensions: -

public static class SequenceExtensions { public static bool SequenceEqual<T>( this IEnumerable<T> first, IEnumerable<T> second, Func<T, T, bool> comparer ) { return first.SequenceEqual( second, new FuncEqualityComparer<T>( comparer ) ); } public static bool SequenceEqual<T>( this IEnumerable<T> first, IEnumerable<T> second, Func<T, T, bool> comparer, Func<T, int> hash ) { return first.SequenceEqual( second, new FuncEqualityComparer<T>( comparer, hash ) ); } }

La réponse d’orip est excellente.

Voici une petite méthode d'extension pour le rendre encore plus facile:

public static IEnumerable<T> Distinct<T>(this IEnumerable<T> list, Func<T, object> keyExtractor) { return list.Distinct(new KeyEqualityComparer<T>(keyExtractor)); } var distinct = foo.Distinct(x => x.ToLower())

Je vais répondre à ma propre question. Pour traiter les dictionnaires en tant qu'ensembles, la méthode la plus simple semble être d'appliquer des opérations d'ensemble à dict.Keys, puis de les reconvertir en dictionnaires avec Enumerable.ToDictionary (...).

La mise en œuvre à (texte allemand) Mise en oeuvre d'IEqualityCompare avec expression lambda se soucie des valeurs nulles et utilise des méthodes d'extension pour générer IEqualityComparer.

Pour créer un IEqualityComparer dans une union Linq, il vous suffit d'écrire

persons1.Union(persons2, person => person.LastName)

Le comparateur:

public class LambdaEqualityComparer<TSource, TComparable> : IEqualityComparer<TSource> { Func<TSource, TComparable> _keyGetter; public LambdaEqualityComparer(Func<TSource, TComparable> keyGetter) { _keyGetter = keyGetter; } public bool Equals(TSource x, TSource y) { if (x == null || y == null) return (x == null && y == null); return object.Equals(_keyGetter(x), _keyGetter(y)); } public int GetHashCode(TSource obj) { if (obj == null) return int.MinValue; var k = _keyGetter(obj); if (k == null) return int.MaxValue; return k.GetHashCode(); } }

Vous devez également ajouter une méthode d'extension pour prendre en charge l'inférence de type
.
public static class LambdaEqualityComparer { // source1.Union(source2, lambda) public static IEnumerable<TSource> Union<TSource, TComparable>( this IEnumerable<TSource> source1, IEnumerable<TSource> source2, Func<TSource, TComparable> keySelector) { return source1.Union(source2, new LambdaEqualityComparer<TSource, TComparable>(keySelector)); } }

Juste une optimisation: Nous pouvons utiliser EqualityComparer, prêt à l'emploi, pour la comparaison de valeurs, plutôt que de le déléguer.

Cela rendrait également l'implémentation plus propre car la logique de comparaison réelle reste maintenant dans GetHashCode () et Equals () que vous avez peut-être déjà surchargée.

Voici le code:

public class MyComparer<T> : IEqualityComparer<T> { public bool Equals(T x, T y) { return EqualityComparer<T>.Default.Equals(x, y); } public int GetHashCode(T obj) { return obj.GetHashCode(); } }

N'oubliez pas de surcharger les méthodes GetHashCode () et Equals () sur votre objet.

Ce message m'a aidé: c # comparer deux valeurs génériques

Sushil

La
réponse d’orip est excellente. Développer la réponse de orip:

Je pense que la solution est d'utiliser & "Méthode d'extension &"; transférer le " type anonyme ".

public static class Comparer { public static IEqualityComparer<T> CreateComparerForElements<T>(this IEnumerable<T> enumerable, Func<T, object> keyExtractor) { return new KeyEqualityComparer<T>(keyExtractor); } }

Utilisation:

var n = ItemList.Select(s => new { s.Vchr, s.Id, s.Ctr, s.Vendor, s.Description, s.Invoice }).ToList(); n.AddRange(OtherList.Select(s => new { s.Vchr, s.Id, s.Ctr, s.Vendor, s.Description, s.Invoice }).ToList();); n = n.Distinct(x=>new{Vchr=x.Vchr,Id=x.Id}).ToList();

public static Dictionary<TKey, TValue> Distinct<TKey, TValue>(this IEnumerable<TValue> items, Func<TValue, TKey> selector) { Dictionary<TKey, TValue> result = null; ICollection collection = items as ICollection; if (collection != null) result = new Dictionary<TKey, TValue>(collection.Count); else result = new Dictionary<TKey, TValue>(); foreach (TValue item in items) result[selector(item)] = item; return result; }

Ceci permet de sélectionner une propriété avec lambda comme ceci: .Select(y => y.Article).Distinct(x => x.ArticleID);

Je ne connais pas de classe existante, mais quelque chose comme:

public class MyComparer<T> : IEqualityComparer<T> { private Func<T, T, bool> _compare; MyComparer(Func<T, T, bool> compare) { _compare = compare; } public bool Equals(T x, Ty) { return _compare(x, y); } public int GetHashCode(T obj) { return obj.GetHashCode(); } }

Remarque: je n'ai pas encore compilé ni exécuté cette application. Il pourrait donc y avoir une faute de frappe ou un autre bogue.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow

Envelopper un délégué dans un IEqualityComparer

Sur l'importance de GetHashCode

Réponse originale

Sur l'importance de `GetHashCode`