Prestazioni scarse impreviste di SortedDictionary rispetto al dizionario

Question

Non capisco perché le prestazioni di SortedDictionary siano circa 5 volte più lente del dizionario per l'impostazione e il recupero dei valori. Mi aspettavo che gli inserimenti e le eliminazioni fossero più lenti ma non aggiornamenti o recuperi. Ho testato il codice compilato .Net 3.5 e .Net 4.0. Una serie di chiavi casuali è stata pre-calcolata per garantire che le variazioni casuali non fossero responsabili delle differenze sull'accesso casuale.

Ecco i seguenti scenari testati.

1. aggiornamento sequenziale di ciascun valore utilizzando [chiave] di accesso
2. accesso sequenziale di ciascun valore utilizzando [chiave] di accesso
3. accesso sequenziale di ciascun valore utilizzando TryGetValue
4. casuale accesso di ogni valore con [chiave ] accessor
5. accesso casuale di ogni valore con TryGetValue

Qualcuno sa il motivo per cui la differenza di prestazioni?

Per favore, se sto facendo qualcosa di sbagliato o stupido, per favore segnalalo.

Codice esempio: basta cambiare dizionario con SortedDictionary per verificare la differenza.

const int numLoops = 100; 
    const int numProperties = 30; 
    const int numInstances = 1000; 

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray) 
    { 
     Stopwatch sw = new Stopwatch(); 
     double total = 0.0d; 

     for (int j = 0; j < numLoops; j++) 
     { 
      //sw.Start(); 
      Dictionary<string, object> original = new Dictionary<string, object>(numValues); 
      for (int i = 0; i < numValues; i++) 
      { 
       original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString()); 
      } 
      List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances); 
      for (int i = 0; i < numInstances; i++) 
      { 
       collectionList.Add(new Dictionary<string, object>(original)); 
      } 
      sw.Start(); 
      //Set values on each cloned instance to uniqe values using the same keys 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString(); 
       } 
      } 

      //Access each unique value 
      object temp; 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        temp = collectionList[k]["Key" + i.ToString()]; 
       } 
      } 
      //Random access 
      //sw.Start(); 
      for (int k = 0; k < numInstances; k++) 
      { 
       for (int i = 0; i < numValues; i++) 
       { 
        collectionList[k].TryGetValue(keyArray[i],out temp); 
       } 
      } 
      sw.Stop(); 
      total += sw.ElapsedMilliseconds; 
      sw.Reset(); 
     } 

Answer 1

SortedDictionary utilizza una ricerca di ricerca binaria, che è O ( registro n).
Dictionary utilizza una tabella hash, che è O (1).

Pertanto, Dictionary offre ricerche più rapide.

La differenza sarà ancora maggiore con le chiavi stringa, che sono costose da confrontare.
A Dictionary solo itererà la stringa due volte (o più se ci sono conflitti di hash) - una volta per calcolare l'hashcode e una volta per assicurarsi che sia una corrispondenza esatta. A SortedDictionary itererà la stringa per il confronto ogni.

Answer 2

Non penso che sia insolito. Others have gotten the same results.

Penso che sia piuttosto semplice perché uno sarebbe più lento dell'altro. SortedDictionary sta facendo di più. Sta smistando. Il dizionario non lo è, quindi è più veloce.

L'unico vero test di ciò che dovrebbe e non dovrebbe essere performante, è il test che viene eseguito sopra. Non penso che tu stia facendo qualcosa di sbagliato qui.