linq Excepto y personalizado IEqualityComparer

Question

Estoy intentando implementar un comparador personalizado en dos listas de cadenas y usar el método .Except() linq para obtener aquellas que no son una de las listas. La razón por la que estoy haciendo un comparador personalizado es porque necesito hacer una comparación "difusa", es decir, una cadena en una lista podría estar incrustada dentro de una cadena en la otra lista.

he hecho la siguiente comparador

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

Cuando elimino errores, el único punto de interrupción que golpea está en el método GetHashCode(). The Equals() nunca se toca. ¿Algunas ideas?

Answer 1

Si todos los códigos hash devueltos son diferentes, nunca es necesario compararlos por igualdad.

Básicamente, el problema es que sus conceptos de hash e igualdad son muy diferentes. No estoy del todo seguro de cómo corregir esto, pero hasta que lo haya hecho, ciertamente no funcionará.

Debe asegurarse de que si Equals(a, b) devuelve verdadero, entonces GetHashCode(a) == GetHashCode(b). (Lo contrario no tiene que ser cierto: las colisiones hash son aceptables, aunque obviamente desea tener la menor cantidad posible).

Answer 2

Como señaló Jon, debe asegurarse de que el código hash de dos cadenas que son iguales (de acuerdo con su regla de comparación). Esto es desafortunadamente bastante difícil.

Para demostrar el problema, Equals(str, "") vuelve verdad para todas las cadenas str, que esencialmente significa que todas las cadenas son iguales a una cadena vacía y, como resultado, todas las cadenas deben tener el mismo hash-código como una cadena vacía. Por lo tanto, la única manera de implementar correctamente IEqualityComparer es volver siempre el mismo hash-código:

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

continuación, puede utilizar el método Except y se comportará correctamente. El único problema es que (probablemente) obtendrá una implementación bastante ineficiente, por lo que si necesita un mejor rendimiento, es posible que deba implementar su propio Except. Sin embargo, no estoy seguro de cuán ineficiente será la implementación de LINQ y no estoy seguro si es posible tener una implementación eficiente para su regla de comparación.

Answer 3

Quizás este problema se pueda resolver sin la implementación de la interfaz IEqualityComparer. Jon y Thomas tienen buenos puntos sobre la implementación de esa interfaz, y la igualdad no parece definir su problema. Según su descripción, creo que podría hacer esto sin usar la extensión Excepto durante la comparación. En lugar de eso, obtenga los partidos primero, luego haga el Excepto. Vea si esto hace el trabajo por usted:

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