Efficienza nell'uso di IEqualityComparer nel dizionario vs HashCode ed Equals()

Question

Il titolo è abbastanza chiaro, penso.

Mi chiedevo se c'è un certo overhead di efficienza quando si utilizza IEqualityComparer in un Dictionary<K,V> come funziona tutto quando ne fornisce uno?

Grazie

Answer 1

È più veloce?

Venendo da un punto di vista gamedev, se la tua chiave è un tipo di valore (struct, primitiva, enum, ecc) fornire il proprio EqualityComparer<T> è significativamente più veloce - a causa del fatto i EqualityComparer<T>.Default caselle il valore.

Come esempio del mondo reale, l'esempio del tabellone per le affissioni Direct DirectX veniva eseguito a circa il 30% della velocità della versione C++; dove tutti gli altri campioni erano in esecuzione a ~ 90%. La ragione di ciò era che i tabelloni pubblicitari venivano ordinati usando il comparatore di default (e quindi in box), in quanto risulta che 4MB di dati venivano copiati su ogni frame grazie a questo.

Come funziona?

Dictionary<K,V> fornirà EqualityComparer<T>.Default a se stesso tramite il costruttore di default. Quello che il confronto uguaglianze predefinito fa è (in pratica, notare quanto la boxe si verifica):

public void GetHashCode(T value) 
{ 
    return ((object)value).GetHashCode(); 
} 

public void Equals(T first, T second) 
{ 
    return ((object)first).Equals((object)second); 
} 

Perché mai dovrei usarlo?

E 'abbastanza comune vedere questo tipo di codice (quando si cerca di avere le chiavi case-insensitive):

var dict = new Dictionary<string, int>(); 
dict.Add(myParam.ToUpperInvariant(), fooParam); 
// ... 
var val = dict[myParam.ToUpperInvariant()]; 

Questo è davvero uno spreco, è meglio utilizzare solo uno StringComparer sul costruttore:

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); 

È più veloce (redux)?

In questo scenario specifico è molto più veloce, perché i confronti di stringhe ordinali sono il tipo di confronto di stringhe più veloce che si possa fare. Un rapido riferimento:

static void Main(string[] args) 
{ 
    var d1 = new Dictionary<string, int>(); 
    var d2 = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); 

    d1.Add("FOO", 1); 
    d2.Add("FOO", 1); 

    Stopwatch s = new Stopwatch(); 
    s.Start(); 
    RunTest1(d1, "foo"); 
    s.Stop(); 
    Console.WriteLine("ToUpperInvariant: {0}", s.Elapsed); 

    s.Reset(); 
    s.Start(); 
    RunTest2(d2, "foo"); 
    s.Stop(); 
    Console.WriteLine("OrdinalIgnoreCase: {0}", s.Elapsed); 

    Console.ReadLine(); 
} 

static void RunTest1(Dictionary<string, int> values, string val) 
{ 
    for (var i = 0; i < 10000000; i++) 
    { 
     values[val.ToUpperInvariant()] = values[val.ToUpperInvariant()]; 
    } 
} 

static void RunTest2(Dictionary<string, int> values, string val) 
{ 
    for (var i = 0; i < 10000000; i++) 
    { 
     values[val] = values[val]; 
    } 
} 

// ToUpperInvariant: 00:00:04.5084119 
// OrdinalIgnoreCase: 00:00:02.1211549 
// 2x faster. 

prenotazioni

È possibile eliminare l'overhead boxe implementando un'interfaccia su una struttura (ad esempio IEquatable<T>). Tuttavia, ci sono molte regole sorprendenti per quando il pugilato si verifica in queste circostanze, quindi consiglio di utilizzare l'interfaccia accoppiata (ad esempio IEqualityComparer<T> in questo caso) se possibile.

Answer 2

Dictionary<,>sempre utilizza un IEqualityComparer<TKey> - se non si passa uno, utilizza EqualityComparer<T>.Default. L'efficienza dipenderà quindi dall'efficienza della tua implementazione rispetto a EqualityComparer<T>.Default (che si limita a delegare a Equals e GetHashCode).

Answer 3

Jonathan ha una great answer che fa notare come, utilizzando il diritto di confronto di uguaglianza migliora le prestazioni e Jon chiarisce in his great answer che Dictionary<K, V> utilizza sempre un IEqualityComparer<T> che è EqualityComparer<T>.Default se non si specifica un altro.

La cosa che vorrei toccare è il ruolo dell'interfaccia IEquatable<T> quando si utilizza il confronto di uguaglianza predefinito.

Quando si chiama EqualityComparer<T>.Default, viene utilizzato un confronto memorizzato nella cache, se disponibile. Se è la prima volta che si utilizza l'operatore di confronto uguaglianze predefinito per quel tipo, che definisce un metodo chiamato CreateComparer e memorizza nella cache il risultato per un uso successivo. Ecco l'tagliato e semplificato realizzazione di CreateComparer in .NET 4.5:

var t = (RuntimeType)typeof(T); 

// If T is byte, 
// return a ByteEqualityComparer. 

// If T implements IEquatable<T>, 
if (typeof(IEquatable<T>).IsAssignableFrom(t)) 
    return (EqualityComparer<T>) 
      RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(
       (RuntimeType)typeof(GenericEqualityComparer<int>), t); 

// If T is a Nullable<U> where U implements IEquatable<U>, 
// return a NullableEqualityComparer<U> 

// If T is an int-based Enum, 
// return an EnumEqualityComparer<T> 

// Otherwise return an ObjectEqualityComparer<T> 

Ma cosa significa per i tipi che implementano IEquatable<T>?
Qui, la definizione di GenericEqualityComparer<T>:

internal class GenericEqualityComparer<T> : EqualityComparer<T> 
    where T: IEquatable<T> 
// ... 

La magia avviene nel vincolo di tipo generico (where T : IEquatable<T> parte) perché usando esso non comporta la boxe se T è un tipo di valore, senza fusione come (IEquatable<T>)T sta accadendo qui, che è il principale vantaggio dei generici.

Quindi, diciamo che vogliamo un dizionario che mappa i numeri interi in stringhe.
Cosa succede se inizializziamo uno utilizzando il costruttore predefinito?

var dict = new Dictionary<int, string>(); 

• Sappiamo che un dizionario utilizza EqualityComparer<T>.Default a meno che non specifichiamo un altro.
• Sappiamo che EqualityComparer<int>.Default controllerà se int implementa IEquatable<int>.
• Sappiamo che int (Int32) implementa IEquatable<Int32>.

prima chiamata a EqualityComparer<T>.Default creerà e memorizzare nella cache un operatore di confronto generica che può prendere un po ', ma quando inizializzato, è un digitato fortemente GenericEqualityComparer<T> e usarlo causerà alcun boxe o inutile sovraccarico di sorta.

E tutte le chiamate successive a EqualityComparer<T>.Default restituiranno il confronto memorizzato nella cache, il che significa che il sovraccarico dell'inizializzazione è una tantum solo per ciascun tipo.

---

Che cosa significa tutto questo?

• fare implementare un'uguaglianza di confronto personalizzato se T non implementa IEquatable<T>o la sua implementazione di IEquatable<T> non fa quello che vuoi che faccia.
  (vale a dire obj1.Equals(obj2) doesn`t darvi il risultato desiderato.

L'utilizzo di StringComparer nella risposta di Jonathan è un ottimo esempio del perché si dovrebbe specificare un comparatore di uguaglianza personalizzato.

• non implementano un confronto di uguaglianza personalizzato per il bene della prestazione se T implementa IEquatable<T>e l'attuazione di IEquatable<T> non ciò che si desidera fare.
  (ad esempio obj1.Equals(obj2) fornisce il risultato desiderato).

In quest'ultimo caso, utilizzare invece EqualityComparer<T>.Default.

Answer 4

ho dovuto affrontare problemi enormi per fare un identico EqualityComparer ... sezione critica era GetHashCode che è stato generando chiave duplicata quando si mira object[] e le registrazioni sono più di 20k .. qui di seguito è la soluzione

public class ObJectArrayEqualityComparer : IEqualityComparer<object[]> 
{ 
    public bool Equals(object[] x, object[] y) 
    { 
     if (x.Length != y.Length) 
     { 
      return false; 
     } 
     for (int i = 0; i < x.Length; i++) 
     { 
      var tempX = x[i]; 
      var tempY = y[i]; 
      if ((tempX==null || tempX ==DBNull.Value) 
       && (tempY == null || tempY == DBNull.Value)) 
      { 
       return true; 
      } 

      if (!tempX.Equals(tempY) 
       && !System.Collections.StructuralComparisons.StructuralEqualityComparer.Equals(tempX, tempY)) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 

    public int GetHashCode(object[] obj) 
    { 
     if (obj.Length == 1) 
     { 
      return obj[0].GetHashCode(); 
     } 

     int result = 0; 

     for (int i = 0; i < obj.Length; i++) 
     { 
      result = result + (obj[i].GetHashCode() * (65 + i)); 
     } 

     return result; 
    } 
}