Complexité asymptotique de .NET les classes de collection

Sont des ressources à propos de la complexité asymptotique (big-O et le reste) de méthodes d' .NET les classes de collection (Dictionary<K,V>, List<T> etc...)?

Je sais que la C5, la bibliothèque de documentation comprend quelques informations à ce sujet (exemple), mais je suis intéressé par la norme .NET des collections de la... (et PowerCollections' information serait bien aussi).

Par la complexité de la classe, je voudrais examiner la complexité cyclomatique plutôt que asymptotique de l'espace/temps-de la complexité. J'avais attribut de ce dernier pour les opérations au sein d'une classe.
Vous pouvez toujours écrire un programme de l'horloge de la fonction particulière qui vous intéresse, de tracer les résultats en fonction de N pour les différents modèles d'entrée. Je pense que la principale raison de leur complexité temporelle n'est pas documentée, c'est que c'est un détail d'implémentation, de sorte que le .NET de l'équipe réserve le droit de modifier les spécificités de la mise en œuvre dans l'avenir. En tant que tel, le cahier des charges pour l'utilisation de ces classes en fonction de leur fonctionnalité et de ne pas leur performance. Si une caractéristique est très importante pour vos besoins, alors il est probablement mieux de le mettre en œuvre l'algorithme de vous-même.

InformationsquelleAutor Igor Brejc | 2009-05-12

26

MSDN ces Listes:
- Dictionnaire<,>
- List<>
- SortedList<,> (edit: mauvais lien; voici le version générique)
- SortedDictionary<,>
etc. Par exemple:

La SortedList(TKey, TValue) générique
la classe est un arbre de recherche binaire avec
O(log n) de récupération, où n est le
nombre d'éléments dans le dictionnaire.
En cela, il est semblable à l'
SortedDictionary(TKey, TValue) générique
classe. Les deux classes ont les mêmes
modèles d'objet, et les deux ont O(log n)
de la récupération. Où les deux classes
diffèrent, c'est dans l'utilisation de la mémoire et de la vitesse de
l'insertion et le retrait:

SortedList(TKey, TValue) utilise moins de
de mémoire que SortedDictionary(TKey,
TValue).

SortedDictionary(TKey, TValue) a
plus vite l'insertion et le retrait
opérations pour des données non triées, O(log n)
contrairement à O(n) pour
SortedList(TKey, TValue).

Si la liste est remplie tout à la fois
à partir de données triées, SortedList(TKey,
TValue) est plus rapide que
SortedDictionary(TKey, TValue).
- Dans ce (vieux, supprimé) citation d'un arbre de recherche binaire est confondu avec un tableau trié collection. en.wikipedia.org/wiki/Binary_search_tree
- Note de l'endroit où ils énumèrent les O la notation. "Le Dictionnaire<TKey, TValue> classe générique fournit une cartographie à partir d'un ensemble de clés à un ensemble de valeurs. Chaque plus le dictionnaire est constitué d'une valeur et de ses clés associés. Récupérer une valeur en utilisant sa clé est très rapide, proche de O(1), parce que le Dictionnaire<TKey, TValue> classe est implémentée comme une table de hachage."
InformationsquelleAutor Marc Gravell
26

Cette page résume quelques temps comlplexities pour les différents types de collection avec Java, mais ils doivent être exactement de la même façon .NET.

J'ai pris les tableaux de la page et modifiée ou agrandie pour l' .NET framework.
Voir aussi les pages MSDN pour SortedDictionary et SortedList, qui décrivent en détail le temps de complexité requis pour les diverses opérations.

Recherche
```
Type de Recherche/Types de Collection de la Complexité des Commentaires 
La recherche linéaire Tableau/liste de tableaux/LinkedList O(N) données non Triées. 
Binaire de recherche triés Tableau/liste de tableaux/O(log N) Nécessite des données triées. 
Recherche table de hachage/Dictionnaire<T> O(1) Utilise la fonction de hachage. 
Binaire de recherche SortedDictionary/SortedKey O(log N) le Tri est automatisé. 
```
D'extraction et d'Insertion
```
Tableau d'Opération/ArrayList, LinkedList SortedDictionary SortedList 
Accès en O(1) O(1) O(log N) O(log N) 
Avant un accès en O(1) O(1) N. A. N. A. 
Accès moyen O(1) O(N) N. A. N. A. 
Insérer à l'arrière O(1) O(1) O(log N) O(N) 
Insérer à l'avant O(N) O(1) N. A. N. A. 
Insérer dans le milieu O(N) O(1) N. A. N. A. 
```
Suppression doit avoir la même complexité que l'insertion de la collection.

SortedList a quelques particularités notables pour l'insertion et l'extraction.

D'Insertion (méthode Add):

Cette méthode est un O(n) opérations pour
des données non triées, où n est le Comte. Il est
un O(log n) opération si la nouvelle
l'élément est ajouté à la fin de la
liste. Si l'insertion des causes de redimensionnement,
l'opération est O(n).

De recherche (propriété d'Élément):

Récupération de la valeur de cette propriété
est un O(log n), où n est
Le comte. La définition de la propriété est un
O(log n) opération si la clé est
déjà dans le SortedList<(De <(TKey,
TValue>)>). Si la clé n'est pas dans le
liste, la définition de la propriété est un O(n)
opération pour des données non triées, ou O(log
n) si le nouvel élément est ajouté à la
fin de la liste. Si l'insertion provoque une
redimensionner, l'opération est O(n).

Noter que ArrayList est équivalent à List<T> en termes de complexité de toutes les opérations.
- Êtes-vous sûr que la complexité doit être la même pour .NET? Je pense que c'est plus subtil que cela: par exemple, il y a une différence entre SortedDictionary, SortedList et dans la table de hachage .NET.
- Ouais, il n'y a pas de différence fondamentale - la base d'algorithmes et structures de données vont être pratiquement identiques. Je n'ai pas détaillé SortedDictionary/SortedList, mais je vais ajouter-le maintenant. Table de hachage doit avoir la même complexité que le Dictionnaire, je crois (c'est un peu un non-générique version de celui-ci).
- Il n'y a aucune garantie que l'implémentation sous-jacente est comparable.
- Non, mais ce est dans le cas de l'officiel .NET mise en œuvre.
InformationsquelleAutor Noldorin
2

Je ne sais pas en général (l'autre réponse vient de poster peut-être vous donne exactement ce que vous êtes après) - mais vous pouvez en tenir compte, et d'autres méthodes de cours à l'aide de ILSpy (un peu maladroit avec FSharp code, vrai) et cela donne finalement une fonction C#:
```
internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}
```
Ok, donc ce n'est pas exactement " bon " code en C# sur les termes, mais la présence de la while(true) boucle implique qu'il ne peut pas être O(1) au moins; que pour ce qu'elle est réellement... eh bien, ma tête me fait mal trop de choses à découvrir 🙂
- FYI: fusionnées à partir de stackoverflow.com/questions/6313896/...
InformationsquelleAutor Andras Zoltan
2

Cette page présente de courtes notes sur les principaux avantages & cons pour la plupart .NET Collections :

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

InformationsquelleAutor WholeLifeLearner
0

Il n'y a pas une telle chose comme "la complexité de la collecte des classes". Plutôt, différentes opérations sur ces collections ont différentes complexités. Par exemple, l'ajout d'un élément à un Dictionary<K, V>...

...s'approche d'un O(1) opération. Si la capacité doit être augmenté pour tenir compte de ce nouvel élément, cette méthode devient un O(n) opération, où n est Count.

Alors que la récupération d'un élément à partir d'un Dictionary<K, V>...

...s'approche d'un O(1) opération.
- Je voulais parler de leurs opérations, j'ai édité la question pour la rendre plus claire.
InformationsquelleAutor Anton Gogolev
0

La documentation dit qu'elle est construite sur un arbre binaire, et ne mentionne pas le suivi de l'élément maximal. Si la documentation est correcte, cela signifie qu'il doit être: O( log n). Il y avait au moins une erreur dans la documentation des collections (en se référant à un tableau adossés à une structure de données comme un arbre de recherche binaire), mais cela a été corrigé.
- Pour être juste, un tableau est parfaitement raisonnable magasin pour un arbre binaire. Voir: webdocs.cs.université de l'alberta.ca/~holte/T26/tree-as-array.html
- Oui et non. Oui, tant que c'est bien sûr tous les mappé à la mémoire principale, qui offre une gamme-comme l'interface (mais très biaisée de préférer l'accès aux données dans la même ligne de cache). Non, car cela ne permet pas une mise en œuvre raisonnable pour tout, mais le plus petit (et équilibré), des arbres. Un multiway arbre correspond beaucoup mieux avec processeur en cours de conception
- FYI: fusionnées à partir de stackoverflow.com/questions/6313896/...
InformationsquelleAutor Stephan Eggermont

Vous devez vous connecter pour publier un commentaire.

Recherche

D'extraction et d'Insertion