la complexité des classes de asymptote collection .NET

StackOverflow https://stackoverflow.com/questions/851949

Question

Y a-t-il des ressources sur la complexité asymptotique (grand-O et le reste) des méthodes de classes de collection .NET (Dictionary<K,V>, etc ... List<T>)?

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

Était-ce utile?

La solution

MSDN ces listes:

etc. Par exemple:

  

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

     

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

     

SortedDictionary (TKey, TValue) a   plus rapide insertion et le retrait   opérations de données non triés, O (log n)   par opposition à O (n) pour   SortedList (TKey, TValue).

     

Si la liste est peuplée à la fois   à partir de données triées, SortedList (TKey,   TValue) est plus rapide que   SortedDictionary (TKey, TValue).

Autres conseils

Cette page résume quelques-unes des comlplexities de temps pour divers types de collections avec Java, mais ils doivent être exactement les mêmes pour .NET.

J'ai pris les tableaux de cette page et changeai / les élargi pour le framework .NET. Voir aussi les pages MSDN pour SortedDictionary et SortedList , qui décrivent en détail la complexité du temps requis pour diverses opérations.

Recherche 

Type of Search/Collection Types           Complexity  Comments
Linear search Array/ArrayList/LinkedList  O(N)        Unsorted data.
Binary search sorted Array/ArrayList/     O(log N)    Requires sorted data.
Search Hashtable/Dictionary<T>            O(1)        Uses hash function.
Binary search SortedDictionary/SortedKey  O(log N)    Sorting is automated.

Récupération et insertion 

Operation         Array/ArrayList  LinkedList  SortedDictionary  SortedList
Access back       O(1)             O(1)        O(log N)          O(log N)
Access front      O(1)             O(1)        N.A.              N.A.
Access middle     O(1)             O(N)        N.A.              N.A.
Insert at back    O(1)             O(1)        O(log N)          O(N)
Insert at front   O(N)             O(1)        N.A.              N.A.
Insert in middle  O(N)             O(1)        N.A.              N.A.

La suppression doit avoir la même complexité que l'insertion de la collection associée.

SortedList a quelques particularités notables pour l'insertion et la récupération.

Insertion (méthode Add):

  

Cette méthode est une opération O (n) pour   données non triés, où n est égal à Count. Il est   une opération O (log n) si le nouveau   élément est ajouté à la fin de la   liste. Si l'insertion provoque un redimensionnement,   l'opération est O (n).

Récupération (propriété d'objet):

  

Récupération de la valeur de cette propriété   est une opération O (log n), où n est égal à   Compter. Définition de la propriété est un   opération O (log n) si la clé est   déjà dans le SortedList <(Of <(TKey,   TValue>)>). Si la clé est pas dans la   liste, définissant la propriété est un O (n)   opération pour les données non triés, ou O (log   n) si on ajoute le nouvel élément à la   fin de la liste. Si l'insertion provoque une   redimensionner, l'opération est O (n).

Notez que équivaut à ArrayList en termes de List<T> la complexité de toutes les opérations.

Je ne sais pas en général (l'autre réponse vient peut-être vous donne affichée exactement ce que vous êtes après) - mais vous pouvez en tenir compte et d'autres méthodes de cours à l'aide ILSpy (un peu maladroit avec le code FSharp, true) et on obtient finalement cette 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;
}

Bon alors ce n'est pas exactement le code « bon » en termes de C # - mais la présence de la boucle implique qu'il ne while(true) peut être O (1) au moins; comme pour ce qu'il est réellement ... eh bien, ma tête me fait mal trop savoir:)

Cette page présente des notes courtes sur certains avantages clés et les inconvénients pour la plupart des collections .NET:

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

Il n'y a pas une telle chose que « la complexité des classes de collection ». Au contraire, les différentes opérations sur ces collections ont différentes complexités. Par exemple, l'ajout d'un élément à un Dictionary<K, V> rel="nofollow noreferrer"> ...

  

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

Alors que la récupération d'un élément d'un rel="nofollow noreferrer"> ...

  

... se rapproche d'une opération de O (1).

La documentation indique qu'il est construit 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 référence à une structure de données soutenue par tableau comme un arbre de recherche binaire), mais qui a été corrigé.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top