linq За исключением и пользовательских IEqualityComparer

Question

Я пытаюсь реализовать пользовательский сопоставитель в двух списках строк и использовать метод linux .Except(), чтобы получить те, которые не являются одним из списков. Причина, по которой я делаю пользовательский сопоставитель, заключается в том, что мне нужно выполнить «нечеткое» сравнение, т. Е. Одна строка в одном списке может быть встроена внутри строки в другой список.

Я сделал следующее компаратор

public class ItemFuzzyMatchComparer : IEqualityComparer<string> 
{ 
    bool IEqualityComparer<string>.Equals(string x, string y) 
    { 
     return (x.Contains(y) || y.Contains(x)); 
    } 

    int IEqualityComparer<string>.GetHashCode(string obj) 
    { 
     if (Object.ReferenceEquals(obj, null)) 
      return 0; 
     return obj.GetHashCode(); 
    } 
} 

Когда я отладки, единственный точки останова, который попадает в методе GetHashCode(). Равно() никогда не прикасается. Есть идеи?

Answer 1

Если все возвращенные хэш-коды отличаются друг от друга, его никогда не нужно сравнивать для равенства.

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

Вы должны убедиться, что если Equals(a, b) возвращает true, то GetHashCode(a) == GetHashCode(b). (Обратное не должно быть правдой - допустимы хэш-коллизии, хотя очевидно, что вы хотите иметь как можно меньше из них.)

Answer 2

Как указал Джон, вам нужно убедиться, что хеш-код две строки, которые равны (согласно вашему правилу сравнения). Это, к сожалению, довольно сложно.

Для демонстрации проблемы Equals(str, "") возвращает true для всех строк str, что по существу означает, что все строки равны пустой строке, и в результате все строки должны иметь один и тот же хеш-код как пустую строку. Таким образом, единственный способ правильно осуществить IEqualityComparer, чтобы вернуться всегда один и тот же хэш-код:

public class ItemFuzzyMatchComparer : IEqualityComparer<string> { 
    bool IEqualityComparer<string>.Equals(string x, string y) { 
    return (x.Contains(y) || y.Contains(x)); 
    } 
    int IEqualityComparer<string>.GetHashCode(string obj) { 
    if (Object.ReferenceEquals(obj, null)) return 0; 
    return 1; 
    } 
} 

Затем вы можете использовать метод Except, и он будет вести себя правильно. Единственная проблема в том, что вы (вероятно) получите довольно неэффективную реализацию, поэтому, если вам нужна более высокая производительность, вам, возможно, придется реализовать свой собственный Except. Тем не менее, я не совсем уверен, насколько неэффективна реализация LINQ, и я не уверен, действительно ли возможно иметь эффективную реализацию для вашего правила сравнения.

Answer 3

Возможно, эта проблема может быть решена без реализации интерфейса IEqualityComparer. У Джона и Томаса есть хорошие моменты в реализации этого интерфейса, и равенство, похоже, не определяет вашу проблему. Из вашего описания, я думаю, вы могли бы сделать это, не используя расширение Except во время сравнения. Вместо этого сначала получите совпадения, затем выполните Except. Посмотрите, подходит ли это для вас:

List<String> listOne = new List<string>(){"hard", "fun", "code", "rocks"}; 
List<String> listTwo = new List<string>(){"fund", "ode", "ard"}; 

var fuzzyMatchList = from str in listOne 
         from sr2 in listTwo 
         where str.Contains(sr2) || sr2.Contains(str) 
         select str; 
var exceptList = listOne.Except(fuzzyMatchList);