LINQ Tranne e personalizzato IEqualityComparer

Question

Sto cercando di implementare un operatore di confronto personalizzato su due liste di stringhe e utilizzare il metodo LINQ .Except() per ottenere quelli che non sono uno uno degli elenchi. La ragione per cui sto facendo un confronto personalizzato è perché ho bisogno di fare un confronto "fuzzy", cioè una stringa su una lista potrebbe essere incorporata all'interno di una stringa sull'altro elenco.

Ho fatto il seguente di confronto

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

Quando il debug, l'unico punto di interruzione che colpisce è nel metodo GetHashCode(). The Equals() non viene mai toccato. Qualche idea?

Answer 1

Se tutti i codici hash restituiti sono diversi, non è mai ha la necessità di confrontare per l'uguaglianza.

In sostanza il problema è che il vostro hash e uguaglianza concetti sono molto diversi. Non sono del tutto sicuro di come lo correggeresti, ma fino a quando non lo avrai fatto, sicuramente non funzionerà.

È necessario assicurarsi che se Equals(a, b) restituisce true, quindi GetHashCode(a) == GetHashCode(b). (Il rovescio non deve essere vero - le collisioni di hash sono accettabili, anche se ovviamente si vuole avere il minor numero possibile di esse.)

Answer 2

Come Jon ha sottolineato, è necessario assicurarsi che il codice hash di due stringhe uguali (in base alla regola di comparazione). Questo è sfortunatamente abbastanza difficile.

Per dimostrare il problema, Equals(str, "") restituisce true per tutte le stringhe str, che significa essenzialmente che tutte le stringhe sono uguali a una stringa vuota e, di conseguenza, tutte le stringhe devono avere lo stesso codice hash di una stringa vuota. Pertanto, l'unico modo per implementare IEqualityComparer correttamente è quello di restituire sempre lo stesso hash-code:

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

quindi è possibile utilizzare il metodo Except e si comporterà in modo corretto. L'unico problema è che (probabilmente) otterrai un'implementazione piuttosto inefficiente, quindi se hai bisogno di prestazioni migliori, potresti dover implementare il tuo Except. Tuttavia, non sono esattamente sicuro di quanto sia inefficace l'implementazione LINQ e non sono sicuro che sia effettivamente possibile avere un'implementazione efficiente per la regola di confronto.

Answer 3

Forse questo problema potrebbe essere risolto senza l'implementazione dell'interfaccia IEqualityComparer. Jon e Thomas hanno buoni punti sull'implementazione di quell'interfaccia e l'uguaglianza non sembra definire il tuo problema. Dalla tua descrizione, penso che potresti farlo senza usare l'estensione Except durante il confronto. Invece, prima prendi le partite, poi fai l'eccezione. Vedere se questo fa il lavoro per voi:

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