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

Я пытаюсь реализовать пользовательский сопоставитель в двух списках строк и использовать метод 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(). Равно() никогда не прикасается. Любые идеи?

Ответы

Ответ 1

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

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

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

Ответ 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, и я не уверен, действительно ли возможно иметь эффективную реализацию для вашего правила сравнения.

Ответ 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);