Optimisation de la lecture: Dictionnaire vs recherche de clé d'index de recherches tableau

Question

J'écris un évaluateur de main de poker carte 7 comme l'un de mes projets pour animaux de compagnie. Tout en essayant d'optimiser sa vitesse (j'aime le défi), j'ai été choqué de constater que les performances de recherche de clé Dictionary est assez lent par rapport à l'indice de lookups tableau.

Par exemple, j'ai couru cet exemple de code qui énumère sur les 52 choisir 7 = 133,784,560 possibles 7 mains cartes:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

sorties qui:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

Ce type de comportement attendu (diminution de la performance d'un facteur 8)? IIRC, un dictionnaire a, en moyenne, O (1) lookups, tandis qu'un tableau a le pire des cas O (1) lookups, donc je ne vous attendez les recherches de tableau pour être plus rapide, mais pas par autant!

Je stocke actuellement le classement des mains de poker dans un dictionnaire. Je suppose que si cela est aussi rapide que les recherches du dictionnaire peut être, je dois repenser va obtenir un peu délicat à la place de mes tableaux d'approche et l'utilisation, bien que l'indexation des classements et je vais probablement poser une autre question à ce sujet.

Answer 1

Ne pas oublier que les notations Big-O dit que la façon dont la complexité augmente par rapport à la taille (etc) - il ne donne aucune indication des facteurs constants impliqués. Voilà pourquoi parfois même linéaire recherche pour les clés est plus rapide qu'une recherche de dictionnaire, quand il y a des touches suffisamment peu. Dans ce cas, vous ne faites même une recherche avec le tableau que - juste une opération d'indexation droite

.

Pour de recherches d'index droites, les tableaux sont essentiellement idéal - il est juste un cas de

pointer_into_array = base_pointer + offset * size

(Et puis un déréférencement de pointeur.)

Effectuer une recherche dans le dictionnaire est relativement compliquée - très rapide par rapport à (disons) une recherche linéaire par clé quand il y a beaucoup de clés, mais beaucoup plus compliqué qu'une recherche de tableau droite. Il doit calculer le hachage de la clé, puis élaborer un seau qui qui devrait être dans, peut-être traiter hash en double (ou en double seaux), puis vérifier l'égalité.

Comme toujours, choisir la structure de données pour le travail -. Et si vous ne pouvez vraiment sortir avec l'indexation juste dans un tableau (ou List<T>) alors oui, ce sera rapide aveuglante

Answer 2

  

Ce type de comportement attendu (diminution de la performance d'un facteur 8)?

Pourquoi pas? Chaque recherche de tableau est presque intantaneous / négligeable, alors qu'une recherche dans le dictionnaire peut avoir besoin d'au moins un appel de sous-programme supplémentaire.

Le point de leurs deux étant O (1) signifie que même si vous avez 50 fois plus d'articles dans chaque collection, la diminution de la performance est encore seulement un facteur de quoi que ce soit (8).

Answer 3

Quelque chose pourrait prendre un millenium, et être toujours O (1).

Si vous en une seule étape grâce à ce code dans la fenêtre de démontage, vous arriverez rapidement à comprendre ce que la différence est.

Answer 4

structures de dictionnaire sont les plus utiles lorsque l'espace clé est très grande et ne peut pas être mis en correspondance dans un ordre stable, séquencés. Si vous pouvez convertir vos clés en un simple entier dans une plage relativement petite, vous serez aux abois pour trouver une structure de données qui interprétera mieux qu'un tableau.

Sur une note de mise en œuvre; .NET, les dictionnaires sont essentiellement hashables. Vous pouvez améliorer quelque peu leur performance clé recherche en veillant à ce que vos clés de hachage dans un grand espace de valeurs uniques. On dirait que dans votre cas, vous utilisez un simple entier comme une clé (que je crois hash à sa propre valeur.) - de sorte que peut-être le meilleur que vous pouvez faire

Answer 5

Une recherche de tableau est de la plus rapide chose que vous pouvez faire - essentiellement tout ce qu'il est est un seul bit de l'arithmétique de pointeur pour aller dès le début du tableau à l'élément que vous voulez trouver. D'autre part, la recherche dans le dictionnaire est susceptible d'être un peu plus lent car il doit faire et se préoccuper hash de trouver le seau correct. Bien que le temps d'exécution prévu est O (1) - les constantes sont algorithmiques plus il sera plus lent

.

Answer 6

Bienvenue à la notation Big-O. Vous devez toujours considérer qu'il ya un facteur constant impliqué.

Faire un Dict-Lookup est bien sûr beaucoup plus cher qu'une recherche de tableau.

Big-O vous indique seulement comment l'échelle des algorithmes. Doublez la quantité de voir comment et lookups les chiffres changent. Les deux devraient prendre environ deux fois le temps

Answer 7

Le coût de la récupération d'un élément à partir d'un Dictionary est O (1) , mais c'est parce qu'un dictionnaire est mis en œuvre en tant que Hashtable - donc vous devez d'abord calculer la valeur de hachage de savoir quel élément pour revenir. Hashtables sont souvent pas efficaces - mais ils sont bons pour grands ensembles de données, ou des ensembles de données qui ont beaucoup de valeurs uniques-hachage

.

La liste (en plus d'être un mot utilisé pour les déchets dercribe un tableau plutôt qu'une liste chaînée!) Sera plus rapide car elle renvoie la valeur en calculant directement l'élément que vous souhaitez renvoyer.