linq Except и пользовательский IEqualityComparer

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

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

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(). Equals() никогда не трогается. Любые идеи?


c# iequalitycomparer
person Joe    schedule 23.03.2010    source источник
comment
Для меня это было хорошим упражнением. В моем случае мне сошло с рук public int GetHashCode(string obj) {return obj.ToLower().GetHashCode();} Ваш вопрос старый, но я столкнулся с той же проблемой 4 года спустя.   -  person T.S.    schedule 22.02.2014

Ответы (3)


arrow_upward
17
arrow_downward

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

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

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

person Jon Skeet    schedule 23.03.2010
comment
Я начинаю думать, что это случай попытки применить пользовательское сравнение к набору предопределенных объектов (то есть строк). Если бы мне пришлось собирать коллекции пользовательских объектов, то я, вероятно, мог бы заставить его работать. Я думаю, мне придется придумать лучший способ, чем этот. :( Я оставлю это без ответа на один день, чтобы посмотреть, есть ли у кого-нибудь еще предложение. - person Joe; 23.03.2010
comment
В итоге я сделал это в два этапа. Я создал список элементов, которые частично совпадали с использованием содержимого, затем развернулся и сделал исключение, используя это подмножество против первого списка. Спасибо за вашу помощь. - person Joe; 26.03.2010

arrow_upward
6
arrow_downward

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

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

person Tomas Petricek    schedule 23.03.2010

arrow_upward
1
arrow_downward

Возможно, эту проблему можно решить без реализации интерфейса 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);
person Audie    schedule 24.03.2010