c# - linq Excepto y personalizado IEqualityComparer

Question

Estoy tratando de implementar un comparador personalizado en dos listas de cadenas y uso el método .Except () linq para obtener las 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 el 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 depuro, el único punto de interrupción que llega es en el método GetHashCode (). Los iguales () nunca son tocados. ¿Algunas ideas?

Answer 1

Como señaló Jon, debe asegurarse de que el código hash de dos cadenas que sean iguales (según su regla de comparación). Esto es lamentablemente bastante difícil.

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

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

Luego puedes usar 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, puede que tenga que implementar su propio Except . Sin embargo, no estoy exactamente seguro de cuán ineficiente será la implementación de LINQ y no estoy seguro de si es realmente posible tener una implementación eficiente para su regla de comparación.

Answer 2

Si todos los códigos hash devueltos son diferentes, nunca se necesita comparar para la igualdad.

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

Debe asegurarse de que si Equals(a, b) devuelve true, entonces GetHashCode(a) == GetHashCode(b) . (Lo contrario no tiene por qué ser cierto: las colisiones de hash son aceptables, aunque obviamente desea tener el menor número posible de ellas).

Answer 3

Tal vez este problema podría resolverse sin la implementación de la interfaz IEqualityComparer. Jon y Thomas tienen buenos puntos para implementar esa interfaz, y la igualdad no parece definir su problema. Desde su descripción, creo que podría hacer esto sin usar la extensión Except durante la comparación. En su lugar, obtener las coincidencias primero, luego hacer la excepción. 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);