SortedList contre SortedDictionary vs. Sort()

Question

Ceci est une suite de questions comme this one.

Y a-t-il des instructions pour peaufiner la performance? Je ne parle pas de gains en big-O, mais d'un gain de temps linéaire. Par exemple, combien le pré-tri peut-il enregistrer sur SortedList ou SortedDictionary? Dites que j'ai une classe de personne avec 3 propriétés à trier, l'un d'eux est l'âge en années. Dois-je d'abord seau les objets sur l'âge?

Dois-je d'abord trier sur une propriété, puis utiliser la liste/dictionnaire résultant pour trier sur deux propriétés et ainsi de suite?

D'autres optimisations qui vous viennent à l'esprit?

Answer 1

Eh bien, c'est une victoire facile sur SortedList. L'insertion d'un élément nécessite une recherche binaire (O (log (n)) pour trouver le point d'insertion, puis un List.Insert (O (n)) pour insérer l'élément.Instant() domine, le remplissage de la liste nécessite O (n^2) Si les éléments d'entrée sont déjà triés, alors l'insertion se réduit à O (1) mais n'affecte pas la recherche Remplir est maintenant O (nlog (n)) Vous ne vous inquiétez pas de la taille de l'Oh, Le tri en premier est toujours plus efficace, en supposant que vous pouvez vous permettre de doubler les besoins de stockage

SortedDictionary est différent, il utilise un arbre rouge-noir, le point d'insertion doit être O (log (n)). Le remplissage du dictionnaire prend donc O (nlog (n)). L'utilisation de l'entrée triée ne change pas l'effort pour trouver le point d'insertion ou le rééquilibrage, c'est toujours O (nlog (n)). Maintenant, l'Oh compte, l'insertion d'une entrée triée nécessite que l'arbre soit consta Nt se rééquilibrer. Cela fonctionne mieux si l'entrée est aléatoire, vous ne voulez pas d'entrée triée.

Remplir SortedList avec une entrée triée et remplir SortedDictionary avec une entrée non triée est à la fois O (nlog (n)). En ignorant le coût de fournir une entrée triée, l'Oh de SortedList est plus petit que l'Oh de SortedDictionary. C'est un détail d'implémentation en raison de la façon dont la liste alloue la mémoire. Il doit seulement faire O (log (n)) fois, un arbre rouge-noir doit allouer O (n) fois. Très petit Oh btw. Il est à noter que ni l'un ni l'autre ne se compare favorablement à la simple remplissage d'une liste, puis en appelant Sort(). C'est aussi O (nlog (n)). En fait, si l'entrée est déjà triée accidentellement, vous pouvez ignorer l'appel Sort(), qui se réduit à O (n). L'analyse des coûts doit maintenant passer à l'effort nécessaire pour trier les entrées. Il est difficile de contourner la complexité fondamentale de Sort(), O (nlog (n)). Il peut ne pas être facilement visible, vous pouvez obtenir l'entrée triée par, disons, une requête SQL. Cela prendra juste plus de temps pour terminer.

Le point d'utilisation de SortedList ou de SortedDictonary est de conserver la collection triée après les insertions. Si vous ne vous souciez que de remplir mais pas de muter, vous ne devriez pas utiliser ces collections.