Agrupar um delegado em um IEqualityComparer

127

Várias funções Linq.Enumerable recebem um IEqualityComparer<T>. Existe uma classe de wrapper conveniente que adapte a delegate(T,T)=>boolpara implementar IEqualityComparer<T>? É fácil escrever um (se você ignorar problemas ao definir um código hash correto), mas eu gostaria de saber se existe uma solução pronta para uso.

Especificamente, quero definir operações em Dictionarys, usando apenas as Chaves para definir associação (mantendo os valores de acordo com regras diferentes).

Marcelo Cantos
fonte

Respostas:

44

Normalmente, eu resolvia isso comentando @Sam na resposta (fiz algumas edições na postagem original para limpá-la um pouco sem alterar o comportamento).

A seguir, é apresentado o meu riff de resposta de @ Sam , com uma correção crítica [IMNSHO] para a política de hash padrão: -

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 );
    }
}
Ruben Bartelink
fonte
5
Para mim, esta é a resposta correta . Tudo o IEqualityComparer<T>que deixa de GetHashCodefora é simplesmente quebrado.
Dan Tao
1
@ Joshua Frank: Não é válido usar igualdade de hash para implicar igualdade - apenas o inverso é verdadeiro. Em suma, @ Dan Tao é completamente correto em que ele diz, e esta resposta é simplesmente a aplicação desse fato para uma resposta anteriormente incompleta
Ruben Bartelink
2
@ Ruben Bartelink: Obrigado por esclarecer. Mas ainda não entendo sua política de hash de t => 0. Se todos os objetos sempre fazem hash com a mesma coisa (zero), isso não é ainda mais complicado do que usar obj.GetHashCode, conforme o argumento de @Dan Tao? Por que nem sempre forçar o chamador a fornecer uma boa função de hash?
21410 Joshua Frank
1
Portanto, não é razoável supor que um algoritmo arbitrário em um Func fornecido não possa retornar verdadeiro, apesar dos códigos de hash serem diferentes. Seu argumento de que retornar zero o tempo todo simplesmente não é hash é verdadeiro. É por isso que há uma sobrecarga que requer o Func de hash quando o criador de perfil diz que as pesquisas não são suficientemente eficientes. O único ponto em tudo isso é que, se você tiver um algoritmo de hash padrão, ele deverá funcionar 100% do tempo e não possuir um comportamento superficialmente correto perigoso. E então podemos trabalhar na performance!
Ruben Bartelink
4
Em outras palavras, como você está usando um comparador personalizado, ele não tem nada a ver com o código de hash padrão do objeto relacionado ao comparador padrão , portanto, você não pode usá-lo.
Peet Brits
170

Sobre a importância de GetHashCode

Outros já comentaram o fato de que qualquer IEqualityComparer<T>implementação personalizada deve realmente incluir um GetHashCodemétodo ; mas ninguém se preocupou em explicar o porquê em detalhes.

Aqui está o porquê. Sua pergunta menciona especificamente os métodos de extensão LINQ; quase todos eles contam com códigos de hash para funcionar corretamente, porque utilizam tabelas de hash internamente para obter eficiência.

Tome Distinct, por exemplo. Considere as implicações desse método de extensão se tudo o que ele utilizou fosse um Equalsmétodo. Como você determina se um item já foi digitalizado em uma sequência, se você apenas o possui Equals? Você enumera toda a coleção de valores que você já examinou e verifica a correspondência. Isso resultaria no Distinctuso de um algoritmo O (N 2 ) do pior caso, em vez de um algoritmo O (N)!

Felizmente, este não é o caso. Distinctnão apenas usa Equals; ele usa GetHashCodetambém. De fato, absolutamente não funciona corretamente sem um IEqualityComparer<T>que forneça um adequadoGetHashCode . Abaixo está um exemplo artificial que ilustra isso.

Digamos que eu tenha o seguinte 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);
    }
}

Agora diga que tenho um List<Value>e quero encontrar todos os elementos com um nome distinto. Este é um caso de uso perfeito para Distinctusar um comparador de igualdade customizado. Então, vamos usar a Comparer<T>classe da resposta de Aku :

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

Agora, se tivermos um monte de Valueelementos com a mesma Namepropriedade, todos eles deverão ser recolhidos em um valor retornado por Distinct, certo? Vamos ver...

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

Resultado:

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

Hmm, isso não funcionou, não é?

Que tal GroupBy? Vamos tentar isso:

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

Resultado:

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

Mais uma vez: não funcionou.

Se você pensar bem, faria sentido Distinctusar um HashSet<T>(ou equivalente) internamente e GroupByusar algo como um Dictionary<TKey, List<T>>internamente. Isso poderia explicar por que esses métodos não funcionam? Vamos tentar isso:

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

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

Resultado:

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

Sim ... começando a fazer sentido?

Felizmente, a partir desses exemplos, fica claro por que a inclusão de um apropriado GetHashCodeem qualquer IEqualityComparer<T>implementação é tão importante.


Resposta original

Expandindo a resposta do orip :

Existem algumas melhorias que podem ser feitas aqui.

  1. Primeiro, eu pegaria um em Func<T, TKey>vez de Func<T, object>; isso impedirá o encaixe das chaves de tipo de valor no keyExtractorpróprio real .
  2. Segundo, eu adicionaria uma where TKey : IEquatable<TKey>restrição; isso impedirá o encaixe na Equalschamada ( object.Equalsaceita um objectparâmetro; você precisa de uma IEquatable<TKey>implementação para pegar um TKeyparâmetro sem encaixotá-lo). Claramente, isso pode representar uma restrição muito severa, para que você possa criar uma classe base sem a restrição e uma classe derivada com ela.

Aqui está a aparência do código resultante:

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));
    }
}
Dan Tao
fonte
1
Seu StrictKeyEqualityComparer.Equalsmétodo parece ser o mesmo que KeyEqualityComparer.Equals. A TKey : IEquatable<TKey>restrição faz o TKey.Equalstrabalho de maneira diferente?
Justin Morgan
2
@JustinMorgan: Sim - no primeiro caso, já que TKeypode ser de qualquer tipo arbitrário, o compilador usará o método virtual Object.Equalsque exigirá o boxe de parâmetros de tipo de valor, por exemplo int,. No último caso, no entanto, como TKeyé restrito à implementação IEquatable<TKey>, TKey.Equalsserá utilizado o método que não exigirá nenhum boxe.
Dan Tao
2
Muito interessante, obrigado pela informação. Eu não tinha ideia de que GetHashCode tinha essas implicações no LINQ até ver essas respostas. É bom saber para uso futuro.
11137 Justin Morgan
1
@JohannesH: Provavelmente! Teria eliminado a necessidade de StringKeyEqualityComparer<T, TKey>também.
Dan Tao
1
+1 @DanTao: Obrigado por uma ótima exposição de por que nunca se deve ignorar códigos de hash ao definir a igualdade no .Net.
Marcelo Cantos
118

Quando você deseja personalizar a verificação de igualdade, 99% do tempo está interessado em definir as chaves a serem comparadas, não a comparação em si.

Essa poderia ser uma solução elegante (conceito do método de classificação de lista do Python ).

Uso:

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

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

A KeyEqualityComparerclasse:

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();
    }
}
orip
fonte
3
Isso é muito melhor do que a resposta do aku.
SLaks
Definitivamente, a abordagem correta. Existem algumas melhorias que podem ser feitas, na minha opinião, que mencionei na minha própria resposta.
Dan Tao
1
Este é um código muito elegante, mas não responde à pergunta, e é por isso que aceitei a resposta do @ aku. Eu queria um invólucro para Func <T, T, bool> e não tenho necessidade de extrair uma chave, pois a chave já está separada no meu dicionário.
Marcelo Cantos
6
@ Marcelo: Tudo bem, você pode fazer isso; mas lembre-se de que, se você seguir a abordagem do @ aku, adicione realmente a Func<T, int>para fornecer o código de hash para um Tvalor (como sugerido em, por exemplo, a resposta de Ruben ). Caso contrário, a IEqualityComparer<T>implementação que você deixou é bastante interrompida, especialmente no que diz respeito à sua utilidade nos métodos de extensão LINQ. Veja minha resposta para uma discussão sobre o motivo disso.
Dan Tao
Isso é bom, mas se a chave selecionada fosse um tipo de valor, haveria boxe desnecessário. Talvez seja melhor ter um TKey para definir a chave.
Graham Ambrose
48

Receio que não exista esse invólucro pronto para uso. No entanto, não é difícil criar um:

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));
aku
fonte
1
No entanto, tenha cuidado com a implementação do GetHashCode. Se você realmente vai usá-lo em algum tipo de tabela de hash, precisará de algo um pouco mais robusto.
Thecoop 15/06/09
46
esse código tem um problema sério! é fácil criar uma classe que tenha dois objetos iguais em termos desse comparador, mas que tenham códigos de hash diferentes.
empi
10
Para remediar isso, a classe precisa de outro membro private readonly Func<T, int> _hashCodeResolverque também deve ser passado no construtor e ser usado no GetHashCode(...)método
precisa saber é o seguinte
6
Estou curioso: por que você está usando em obj.ToString().ToLower().GetHashCode()vez de obj.GetHashCode()?
Justin Morgan
3
Os lugares na estrutura que IEqualityComparer<T>usam invariavelmente o hash nos bastidores (por exemplo, GroupBy, Distinct, Except, Join, etc) do LINQ e o contrato da MS em relação ao hash são quebrados nesta implementação. Aqui está o trecho da documentação da MS: "São necessárias implementações para garantir que, se o método Equals retornar true para dois objetos x e y, o valor retornado pelo método GetHashCode para x deve ser igual ao valor retornado para y". Veja: msdn.microsoft.com/en-us/library/ms132155
devgeezer 23/08/12
22

O mesmo que a resposta de Dan Tao, mas com algumas melhorias:

  1. Confia em EqualityComparer<>.Defaultfazer a comparação real para evitar boxe para os tipos de valor structque foram implementados IEquatable<>.

  2. Desde que EqualityComparer<>.Defaultusado, ele não explode null.Equals(something).

  3. O invólucro estático fornecido em torno do IEqualityComparer<>qual terá um método estático para criar a instância do comparador - facilita a chamada. Comparar

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

    com

    new EqualityComparer<Person, int>(p => p.ID);
  4. Adicionada uma sobrecarga para especificar IEqualityComparer<>a chave.

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

você pode usá-lo assim:

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

Pessoa é uma classe simples:

class Person
{
    public int ID { get; set; }
    public string Name { get; set; }
    public DateTime Birthday { get; set; }
}
ldp615
fonte
3
+1 por fornecer uma implementação que permite fornecer um comparador para a chave. Além de dar mais flexibilidade, isso também evita tipos de valores de boxe para as comparações e também para o hash.
Devgeezer
2
Esta é a resposta mais detalhada aqui. Eu adicionei uma verificação nula também. Completo.
Nawfal 18/04
11
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 );
    }
}

Com extensões: -

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 ) );
    }
}
Ruben Bartelink
fonte
@ Sam (que não existe mais a partir deste comentário): Limpe o código sem alterar o comportamento (e marcou com +1). Adicionado Riff em stackoverflow.com/questions/98033/…
Ruben Bartelink
6

A resposta do orip é ótima.

Aqui está um pequeno método de extensão para facilitar ainda mais:

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())
Bruno
fonte
2

Eu vou responder minha própria pergunta. Para tratar Dicionários como conjuntos, o método mais simples parece ser aplicar operações de conjunto a dict.Keys e depois converter novamente em Dicionários com Enumerable.ToDictionary (...).

Marcelo Cantos
fonte
2

A implementação em (texto em alemão) Implementing IEqualityCompare com expressão lambda se preocupa com valores nulos e usa métodos de extensão para gerar IEqualityComparer.

Para criar um IEqualityComparer em uma união Linq, basta escrever

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

O comparador:

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

Você também precisa adicionar um método de extensão para dar suporte à inferência de 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));
       }
   }
Frito
fonte
1

Apenas uma otimização: podemos usar o EqualityComparer pronto para uso para comparações de valor, em vez de delegá-lo.

Isso também tornaria a implementação mais limpa, já que a lógica de comparação real agora permanece em GetHashCode () e Equals (), que você já pode ter sobrecarregado.

Aqui está o código:

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ão se esqueça de sobrecarregar os métodos GetHashCode () e Equals () no seu objeto.

Este post me ajudou: c # comparar dois valores genéricos

Sushil

Sushil
fonte
1
Nota: o mesmo problema identificado no comentário em stackoverflow.com/questions/98033/… - CANT assume obj.GetHashCode () faz sentido
Ruben Bartelink
4
Eu não entendo o objetivo deste. Você criou um comparador de igualdade equivalente ao comparador de igualdade padrão. Então, por que você não o usa diretamente?
CodesInChaos
1

A resposta do orip é ótima. Expandindo a resposta do orip:

Eu acho que a chave da solução é usar "Método de extensão" para transferir o "tipo anônimo".

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

Uso:

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

Isso torna possível selecionar uma propriedade com lambda assim: .Select(y => y.Article).Distinct(x => x.ArticleID);

Máx.
fonte
-2

Não conheço uma classe existente, mas algo como:

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: Na verdade, eu ainda não compilei e executei isso; portanto, pode haver um erro de digitação ou outro bug.

Gregg
fonte
1
NB mesmo problema identificado na comentário sobre stackoverflow.com/questions/98033/... - não podem assumir obj.GetHashCode () faz sentido
Ruben Bartelink