J'ai 2 millions d'articles dans un SortedDictionary<string, MyClass>Amélioration du temps d'accès sur SortedDictionary
J'ai fait les suivants et les âges, toutes Takes idées?
for(int i = 0; i<dic.Count-1; i++)
{
Debug.WriteLine(dic.ElementAt(i).Value.ToString());
}
La classe SortedDictionary<TKey, TValue> ne prend pas directement en charge la récupération (rapide) par index; il est implémenté en interne sous la forme d'un arbre de recherche binaire. Par conséquent, chaque appel à la méthode LINQ Enumerable.ElementAt que vous avez là crée un nouvel énumérateur qui itère chaque valeur de la séquence représentée par les paires clé-valeur dans la collection (triées par clé) depuis le début jusqu'à atteindre la valeur désirée indice. Cela signifie que la boucle va devoir tirer quelque chose comme 1 + 2 + 3 + ... + Count (environ 2 trillions) d'éléments avant qu'elle ne se termine, ce qui la rend (au moins) quadratique dans sa complexité temporelle.
Essayez plutôt, qui devrait fonctionner dans le temps à peu près linéaire:
foreach(var myClass in dic.Values)
Debug.WriteLine(myClass);
Si vous ne voulez vraiment un accès rapide par index (à partir du code fourni, il ne semble pas y avoir de raison d'indiquer), envisagez d'utiliser un SortedList<TKey, TValue> à la place. Il y a des inconvénients à ce choix (insertions et suppressions plus lentes sans ajout) que vous devriez évaluer. Je remarque également que la condition de boucle est i < dic.Count - 1 plutôt que i < dic.Count plus commun. C'est soit un bogue off-by-one, ou peut-être que vous avez l'intention de ne pas considérer la dernière valeur dans le dictionnaire. Dans ce dernier cas, vous pouvez maintenir une variable locale servant de contre ou avec LINQ:
foreach(var myClass in dic.Values.Take(dic.Count - 1))
Debug.WriteLine(myClass);
foreach pourrait être plus rapide, puisque vous n'utilisez pas l'indexeur
foreach (var value in dic.Values)
Debug.Writeline(value)
En outre, dans la mesure qui concerne la vitesse, Debug.Writeline est probablement pas la meilleure option (ce que vous allez faire avec 2 millions d'entrées de trace de débogage de toute façon ??). Pensez à écrire dans un fichier, une base de données, etc.
EDIT regardant réflecteur, trouver une valeur dans un SortedDictionry se résume à une recherche binaire:
internal virtual Node<T> FindNode(T item)
{
int num;
for (Node<T> node = this.root; node != null; node = (num < 0) ? node.Left : node.Right)
{
num = this.comparer.Compare(item, node.Item);
if (num == 0)
{
return node;
}
}
return null;
}
La mise en œuvre de l'itération de SortedDictionary semble un peu plus impliqués:
public bool MoveNext()
{
this.tree.VersionCheck();
if (this.version != this.tree.version)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
}
if (this.stack.Count == 0)
{
this.current = null;
return false;
}
this.current = this.stack.Pop();
SortedSet<T>.Node item = this.reverse ? this.current.Left : this.current.Right;
SortedSet<T>.Node node2 = null;
SortedSet<T>.Node node3 = null;
while (item != null)
{
node2 = this.reverse ? item.Right : item.Left;
node3 = this.reverse ? item.Left : item.Right;
if (this.tree.IsWithinRange(item.Item))
{
this.stack.Push(item);
item = node2;
}
else
{
if ((node3 == null) || !this.tree.IsWithinRange(node3.Item))
{
item = node2;
continue;
}
item = node3;
}
}
return true;
}
Il semble maintenir une pile dont l'élément supérieur est le plus petit (ou plus, selon la direction) un, et donc toujours celui à sauté et est retourné au cours iter ation. Je n'ai fait aucune analyse de complexité, mais il est forcément beaucoup plus efficace que d'exécuter une recherche binaire à chaque fois.
Utilisation foreach:
foreach (var pair in d)
Debug.WriteLine(pair.Value);
Je parie que la sortie de débogage prend plus de temps que les dictionnaires recherche bien.