la complessità asintotica di classi di insiemi .NET

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

Domanda

Ci sono risorse per circa la complessità asintotica (O-grande e il resto) di metodi di classi di insiemi .NET (Dictionary<K,V>, List<T> ecc ...)?

So che la documentazione della biblioteca C5 include alcune informazioni su di esso ( esempio ), ma mi interessa collezioni di base .NET troppo ... le informazioni (e PowerCollections' sarebbe anche bello).

È stato utile?

Soluzione

MSDN Liste questi:

ecc. Ad esempio:

  

Il SortedList (TKey, TValue) generici   classe è un albero binario di ricerca con   O (log n) di recupero, dove n è il   numero di elementi nel dizionario.   In questo, è simile al   SortedDictionary (TKey, TValue) generici   classe. Le due classi hanno simile   opporsi modelli, ed entrambi hanno O (log n)   recupero. Dove le due classi   differiscono è in uso la memoria e la velocità di   inserimento e rimozione:

     

SortedList (TKey, TValue) utilizza meno   Memoria di SortedDictionary (TKey,   TValue).

     

SortedDictionary (TKey, TValue) ha   veloce inserimento e rimozione   operazioni per dati non ordinati, O (log n)   al contrario di O (n) per   SortedList (TKey, TValue).

     

Se l'elenco è popolato tutto in una volta   da dati ordinati, SortedList (TKey,   TValue) è più veloce di   SortedDictionary (TKey, TValue).

Altri suggerimenti

Questa pagina riassume alcuni dei comlplexities tempo per vari tipi di raccolta con Java, anche se dovrebbe essere esattamente lo stesso per NET.

Ho preso i tavoli da quella pagina e alterata / li esteso per il framework .NET. Vedi anche le pagine di MSDN per SortedDictionary e SortedList , che illustrano la complessità di tempo necessari per varie operazioni.

Ricerca 

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.

recupero e inserimento 

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.

Soppressione dovrebbe avere la stessa complessità di inserimento per la raccolta associata.

SortedList ha alcune caratteristiche notevoli per l'inserimento e il recupero.

Inserimento (Aggiungi metodo):

  

Questo metodo è un'operazione O (n) per   dati non ordinati, dove n è il conte. È   un'operazione O (log n) se il nuovo   elemento viene aggiunto alla fine del   elenco. Se inserimento provoca un ridimensionamento,   l'operazione è O (n).

Recupero (proprietà Item):

  

Recuperare il valore di questa proprietà   è un'operazione O (log n), dove n è   Contare. L'impostazione della proprietà è un   O (log n) se la chiave è   già nella SortedList <(Of <(TKey,   TValue>)>). Se la chiave non è in   lista, l'impostazione della proprietà è un O (n)   operazione per dati non ordinati, oppure O (log   n) se il nuovo elemento si aggiunge al   fine della lista. Se inserimento provoca una   ridimensionare, l'operazione è O (n).

Si noti che ArrayList equivale a List<T> in termini di complessità di tutte le operazioni.

Non so in generale (l'altra risposta appena pubblicato forse ti dà esattamente quello che stai dopo) - ma è possibile riflettere questo ed altri metodi, naturalmente utilizzando ILSpy (un po 'imbarazzante con il codice di FSharp, vero) e questo alla fine produce questa funzione come 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;
}

Va bene così questo non è esattamente il codice 'corretto' in C # termini - ma la presenza del while(true) ciclo implica che non può essere O (1), almeno; Quanto a ciò che effettivamente è ... beh, la mia testa fa male troppo da scoprire:)

Questa pagina presenta brevi note su alcuni pro e contro chiave per la maggior parte Collezioni NET:

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

Non esiste una cosa come "la complessità delle classi di raccolta". Piuttosto, diverse operazioni su queste collezioni hanno diverse complessità. Ad esempio, l'aggiunta di un elemento in un Dictionary<K, V> ...

  

... si avvicina ad un O (1) il funzionamento. Se la capacità deve essere aumentata per accogliere il nuovo elemento, questo metodo diventa un O (n) funzionamento, dove n è Count.

considerando che il recupero di un elemento da un <=> ...

  

... si avvicina ad un (1) il funzionamento O.

La documentazione dice che è costruita su un albero binario, e non menziona il monitoraggio l'elemento massimo. Se la documentazione è corretta, il che significa che dovrebbe essere O (log n). Ci deve essere utilizzato almeno un errore nella documentazione collezioni (riferendosi ad un array-backed come un albero binario di ricerca), ma che è stato corretto.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top