Avvolgi un delegato in un IEqualityComparer

StackOverflow https://stackoverflow.com/questions/98033

  •  01-07-2019
  •  | 
  •  

Domanda

Diverse funzioni Linq.Enumerable richiedono un'estensione IEqualityComparer<T>.Esiste una classe wrapper conveniente che adatta a delegate(T,T)=>bool implementare IEqualityComparer<T>?È abbastanza facile scriverne uno (se ignori i problemi con la definizione di un hashcode corretto), ma mi piacerebbe sapere se esiste una soluzione pronta all'uso.

Nello specifico, voglio eseguire operazioni di impostazione su Dictionarys, utilizzando solo le chiavi per definire l'appartenenza (mantenendo i valori secondo regole diverse).

È stato utile?

Soluzione

Di solito, risolverei il problema commentando @Sam sulla risposta (ho apportato alcune modifiche al post originale per ripulirlo un po' senza alterarne il comportamento.)

Quello che segue è il mio riff di @ Risposta di Sam, con una correzione critica [IMNSHO] alla politica di hashing predefinita:-

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 );
    }
}

Altri suggerimenti

Sull'importanza di GetHashCode

Altri hanno già commentato il fatto che qualsiasi consuetudine IEqualityComparer<T> implementazione dovrebbe davvero includere a GetHashCode metodo;ma nessuno si è preso la briga di spiegare Perché in ogni dettaglio.

Ecco perché.La tua domanda menziona specificamente i metodi di estensione LINQ;quasi Tutto di questi si basano su codici hash per funzionare correttamente, poiché utilizzano tabelle hash internamente per efficienza.

Prendere Distinct, Per esempio.Considera le implicazioni di questo metodo di estensione se tutto ciò che utilizza fosse un Equals metodo.Come determini se un elemento è già stato scansionato in una sequenza se lo hai solo fatto Equals?Enumeri l'intera raccolta di valori che hai già esaminato e controlli la corrispondenza.Ciò comporterebbe Distinct utilizzando il caso peggiore O(N2) invece di un algoritmo O(N)!

Fortunatamente, non è così. Distinct no Appena utilizzo Equals;utilizza GetHashCode anche.Infatti, assolutamente non funzionare correttamente senza un IEqualityComparer<T> che fornisce un corretto GetHashCode.Di seguito è riportato un esempio inventato che illustra questo.

Diciamo che ho il seguente tipo:

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);
    }
}

Ora diciamo che ho un List<Value> e voglio trovare tutti gli elementi con un nome distinto.Questo è un caso d'uso perfetto per Distinct utilizzando un comparatore di uguaglianza personalizzato.Quindi usiamo il Comparer<T> classe da La risposta di Aku:

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

Ora, se ne abbiamo un sacco Value elementi con lo stesso Name proprietà, dovrebbero collassare tutti in un unico valore restituito da Distinct, Giusto?Vediamo...

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);
}

Produzione:

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

Hmm, non ha funzionato, vero?

Che dire GroupBy?Proviamolo:

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);
    }
}

Produzione:

[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

Ancora:non ha funzionato.

Se ci pensi, avrebbe senso Distinct usare a HashSet<T> (o equivalente) internamente e per GroupBy usare qualcosa come a Dictionary<TKey, List<T>> internamente.Questo potrebbe spiegare perché questi metodi non funzionano?Proviamo questo:

var uniqueValues = new HashSet<Value>(values, comparer);

foreach (Value x in uniqueValues)
{
    Console.WriteLine(x);
}

Produzione:

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

Sì...inizia ad avere senso?

Si spera che da questi esempi sia chiaro il motivo per cui includere un file appropriato GetHashCode in qualsiasi IEqualityComparer<T> l'implementazione è così importante.

Risposta originale

Espansione la risposta di orip:

Ci sono un paio di miglioramenti che possono essere apportati qui.

  1. Per prima cosa, prenderei un Func<T, TKey> invece di Func<T, object>;ciò impedirà il boxing delle chiavi del tipo valore nella realtà keyExtractor si.
  2. Secondo, in realtà aggiungerei a where TKey : IEquatable<TKey> vincolo;questo impedirà la boxe nel Equals chiamata (object.Equals prende un object parametro;hai bisogno di un IEquatable<TKey> implementazione per prendere a TKey parametro senza boxarlo).Chiaramente questo potrebbe rappresentare una restrizione troppo severa, quindi potresti creare una classe base senza il vincolo e una classe derivata con essa.

Ecco come potrebbe apparire il codice risultante:

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));
    }
}

Quando desideri personalizzare il controllo dell'uguaglianza, il 99% delle volte sei interessato a definire le chiavi in ​​base alle quali confrontare, non il confronto stesso.

Questa potrebbe essere una soluzione elegante (concetto da Python metodo di ordinamento dell'elenco).

Utilizzo:

var foo = new List<string> { "abc", "de", "DE" };

// case-insensitive distinct
var distinct = foo.Distinct(new KeyEqualityComparer<string>( x => x.ToLower() ) );

IL 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();
    }
}

Temo che non esista un involucro del genere.Tuttavia non è difficile crearne uno:

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));

Uguale alla risposta di Dan Tao, ma con alcuni miglioramenti:

  1. Fa affidamento su EqualityComparer<>.Default per eseguire il confronto effettivo in modo da evitare il boxing per i tipi di valore (structs) che ha attuato IEquatable<>.

  2. Da EqualityComparer<>.Default usato non esplode null.Equals(something).

  3. Fornito wrapper statico IEqualityComparer<> che avrà un metodo statico per creare l'istanza dell'operatore di confronto - facilita la chiamata.Confrontare

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

    con

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

  4. Aggiunto un sovraccarico da specificare IEqualityComparer<> per la chiave.

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));
        }
    }
}

puoi usarlo in questo modo:

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);

Person è una classe semplice:

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 );
    }
}

Con estensioni:-

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 risposta di orip è fantastica.

Ecco un piccolo metodo di estensione per renderlo ancora più semplice:

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())

Risponderò alla mia stessa domanda.Per trattare i dizionari come insiemi, il metodo più semplice sembra essere quello di applicare operazioni di insieme a dict.Keys, quindi riconvertirli in dizionari con Enumerable.ToDictionary(...).

L'implementazione in (testo tedesco) Implementazione di IEqualityCompare con l'espressione lambdasi preoccupa dei valori null e utilizza metodi di estensione per generare IEqualityComparer.

Per creare un IEqualityComparer in un'unione Linq devi solo scrivere

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

Il comparatore:

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();
  }
}

È inoltre necessario aggiungere un metodo di estensione per supportare l'inferenza del tipo

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));
       }
   }

Una sola ottimizzazione:Possiamo utilizzare EqualityComparer pronto all'uso per confronti di valori, anziché delegarlo.

Ciò renderebbe anche l'implementazione più pulita poiché la logica di confronto effettiva ora rimane in GetHashCode() e Equals() che potresti aver già sovraccaricato.

Ecco il codice:

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(); 
  } 
}

Non dimenticare di sovraccaricare i metodi GetHashCode() e Equals() sul tuo oggetto.

Questo post mi ha aiutato: c# confronta due valori generici

Sushil

la risposta di orip è grande.Espandendo la risposta di orip:

penso che la chiave della soluzione sia utilizzare il "metodo di estensione" per trasferire il "tipo anonimo".

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

Utilizzo:

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;
  }

Ciò rende possibile selezionare una proprietà con lambda come questa: .Select(y => y.Article).Distinct(x => x.ArticleID);

Non conosco una classe esistente ma qualcosa del tipo:

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();
  }
}

Nota:In realtà non l'ho ancora compilato ed eseguito, quindi potrebbe esserci un errore di battitura o un altro bug.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top