Оберните делегата в IEqualityComparer

Question

Оберните делегата в IEqualityComparer

Несколько функций Linq. Многочисленные IEqualityComparer<T>, Есть ли удобный класс-обертка, который адаптирует delegate(T,T)=>bool реализовать IEqualityComparer<T>? Это достаточно просто написать (если вы игнорируете проблемы с определением правильного хэш-кода), но я хотел бы знать, есть ли готовое решение.

В частности, я хочу сделать операции над Dictionarys, используя только ключи для определения членства (сохраняя значения в соответствии с различными правилами).

131

.net linq delegates

Источник

user9990 18 сен '08 в 23:34

15 ответов

Решение

О важности `GetHashCode`

Другие уже прокомментировали тот факт, что любой обычай IEqualityComparer<T> реализация должна действительно включать GetHashCodeметод; но никто не удосужился объяснить,почему в любой детали.

Вот почему В вашем вопросе конкретно упоминаются методы расширения LINQ; почтивсе из них полагаются на хэш-коды для правильной работы, потому что они используют хеш-таблицы внутри для эффективности.

приниматьDistinct, например. Рассмотрим последствия этого метода расширения, если все, что он использовал, было Equals метод. Как вы определяете, был ли элемент уже отсканирован в последовательности, если у вас есть только Equals? Вы перечисляете всю совокупность значений, которые вы уже просматривали, и проверяете соответствие. Это приведет к Distinct используя алгоритм O (N²) в худшем случае вместо алгоритма O(N)!

К счастью, это не так. Distinct не просто использовать Equals; оно использует GetHashCode также. На самом деле, это абсолютно не работает должным образом без IEqualityComparer<T>который поставляет надлежащийGetHashCode, Ниже приведен надуманный пример, иллюстрирующий это.

Скажем, у меня есть следующий тип:

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

Теперь скажи, что у меня есть List<Value> и я хочу найти все элементы с отдельным именем. Это идеальный вариант использования для Distinctиспользуя пользовательский компаратор равенства. Итак, давайте использоватьComparer<T>класс из ответа Аку:

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

Теперь, если у нас есть куча Valueэлементы с одинаковымиNameсобственности, все они должны свернуться в одно значение, возвращаемоеDistinct, право? Посмотрим...

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

Выход:

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

Хм, это не сработало, не так ли?

Как насчетGroupBy? Давайте попробуем это:

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

Выход:

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

Опять же: не работает.

Если вы думаете об этом, это будет иметь смысл для Distinct использовать HashSet<T> (или эквивалент) внутри страны и для GroupBy использовать что-то вроде Dictionary<TKey, List<T>> внутренне. Может ли это объяснить, почему эти методы не работают? Давайте попробуем это:

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

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

Выход:

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

Да... начинает иметь смысл?

Надеюсь, из этих примеров понятно, почему в том числе GetHashCode в любой IEqualityComparer<T> реализация так важна.

Оригинальный ответ

Расширяя ответ orip:

Есть несколько улучшений, которые можно сделать здесь.

Во-первых, я бы взял Func<T, TKey> вместо Func<T, object>; это предотвратит упаковку ключей типа значения в фактическую keyExtractor сам.
Во-вторых, я бы на самом деле добавил where TKey : IEquatable<TKey> ограничение; это предотвратит бокс в Equals вызов (object.Equals занимает object параметр; тебе нужен IEquatable<TKey> реализация принять TKey параметр без бокса это). Ясно, что это может накладывать слишком жесткие ограничения, поэтому вы можете создать базовый класс без ограничения и производный класс с ним.

Вот как может выглядеть полученный код:

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

178

Источник

user105570 15 сен '10 в 16:39

Когда вы хотите настроить проверку на равенство, 99% времени вы заинтересованы в определении ключей для сравнения, а не в самом сравнении.

Это может быть элегантным решением (концепция из метода сортировки списка Python).

Использование:

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

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

KeyEqualityComparer учебный класс:

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

120

Источник

user37020 06 авг '09 в 14:41

Боюсь, что нет такой обертки из коробки. Однако это не сложно создать:

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

48

Источник

user1196 18 сен '08 в 23:52

То же, что и ответ Дана Тао, но с некоторыми улучшениями:

Полагается на EqualityComparer<>.Default выполнить реальное сравнение, чтобы избежать коробок для типов значений (structs) который реализовал IEquatable<>,
поскольку EqualityComparer<>.Default использовал это не взрывается на null.Equals(something),
Предоставлена статическая обертка вокруг IEqualityComparer<> который будет иметь статический метод для создания экземпляра сравнения - облегчает вызов. сравнить
```
Equality<Person>.CreateComparer(p => p.ID);
```
с
```
new EqualityComparer<Person, int>(p => p.ID);
```
Добавлена перегрузка для указания IEqualityComparer<> за ключ.

Класс:

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

Вы можете использовать это так:

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

Человек это простой класс:

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

26

Источник

user285996 02 авг '11 в 14:25

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

С расширениями:-

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

11

Источник

06 ноя '08 в 20:44

Ответ Орипа великолепен.

Вот небольшой метод расширения, чтобы сделать его еще проще:

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

6

Источник

user168043 27 май '11 в 09:44

Я собираюсь ответить на свой вопрос. Похоже, что для обработки словарей как наборов простейшим методом является применение операций над множествами к dict.Keys, а затем преобразование обратно в словари с помощью Enumerable.ToDictionary(...).

2

Источник

user9990 19 сен '08 в 00:09

Реализация в (немецкий текст) Реализация IEqualityCompare с лямбда-выражением заботится о нулевых значениях и использует методы расширения для генерации IEqualityComparer.

Чтобы создать IEqualityComparer в объединении Linq, вам просто нужно написать

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

Компаратор:

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

Вам также необходимо добавить метод расширения для поддержки вывода типа

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

2

Источник

user2534462 29 июн '13 в 11:26

Ответ Орипа великолепен. Расширяя ответ orip:

я думаю, что ключом решения является использование "метода расширения" для передачи "анонимного типа".

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

Использование:

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

1

Источник

user1295274 06 апр '12 в 06:52

Только одна оптимизация: мы можем использовать готовый EqualityComparer для сравнения значений, а не делегировать его.

Это также сделало бы реализацию чище, поскольку реальная логика сравнения теперь остается в GetHashCode() и Equals(), которые вы, возможно, уже перегружены.

Вот код:

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

Не забудьте перегрузить методы GetHashCode() и Equals() для вашего объекта.

Этот пост помог мне: C# сравнить два общих значения

Sushil

1

Источник

user379132 29 июн '10 в 15:17

      public class DelegateEqualityComparer<T>: IEqualityComparer<T>
{
    private readonly Func<T, T, bool> _equalsDelegate;
    private readonly Func<T, int>     _getHashCodeDelegate;

    public DelegateEqualityComparer(Func<T, T, bool> equalsDelegate, Func<T, int> getHashCodeDelegate)
    {
        _equalsDelegate      = equalsDelegate      ?? ((tx, ty) => object.Equals(tx, ty));
        _getHashCodeDelegate = getHashCodeDelegate ?? (t => t.GetSafeHashCode());
    }

    public bool Equals(T x, T y) => _equalsDelegate(x, y);

    public int GetHashCode(T obj) => _getHashCodeDelegate(obj);
}

0

Источник

user7226886 06 окт '22 в 20:52

Добавление аннотаций ссылочных типов, допускающих значение NULL, в ответ ldp615 .

      public static class Equality<T> where T : class
{
    public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector) where V : notnull
    {
        return CreateComparer(keySelector, EqualityComparer<V>.Default);
    }

    public static IEqualityComparer<T> CreateComparer<V>(
        Func<T, V> keySelector,
        IEqualityComparer<V> comparer)
        where V : notnull
    {
        return new KeyEqualityComparer<V>(keySelector, comparer);
    }

    class KeyEqualityComparer<V> : IEqualityComparer<T> where V : notnull
    {
        readonly Func<T, V> keySelector;
        readonly IEqualityComparer<V> comparer;

        public KeyEqualityComparer(
            Func<T, V> keySelector,
            IEqualityComparer<V> comparer)
        {
            if (keySelector == null)
                throw new ArgumentNullException(nameof(keySelector));
            if (comparer == null)
                throw new ArgumentNullException(nameof(comparer));

            this.keySelector = keySelector;
            this.comparer = comparer;
        }

        public bool Equals(T? x, T? y)
        {
            if (x == null || y == null)
            {
                if(x == y)
                {
                    return true;
                }

                return false;
            }

            return comparer.Equals(keySelector(x), keySelector(y));
        }

        public int GetHashCode(T obj)
        {
            return comparer.GetHashCode(keySelector(obj));
        }
    }
}

0

Источник

user682203 19 ноя '23 в 13:18

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

Это позволяет выбрать свойство с лямбдой так: .Select(y => y.Article).Distinct(x => x.ArticleID);

0

Источник

user260093 30 май '11 в 13:10

Я не знаю существующего класса, но что-то вроде:

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

Примечание: я еще не скомпилировал и не запустил это, так что может быть опечатка или другая ошибка.

-2

Источник

user18266 18 сен '08 в 23:55

Другие вопросы по тегам .net linq delegates

user11635 15 сен '10 в 16:13 2010-09-15 16:13 · Accepted Answer · 2010-09-15 16:13

Обычно я решаю эту проблему, комментируя ответ @Sam (я немного отредактировал исходное сообщение, чтобы немного его очистить, не меняя поведения).

Ниже приведен мой ответ @ Сэма с критическим исправлением [IMNSHO] к политике хеширования по умолчанию:-

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

Оберните делегата в IEqualityComparer

15 ответов

О важности GetHashCode

Оригинальный ответ

О важности `GetHashCode`