complexidade assintótica de classes de coleção .NET

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

Pergunta

Existem recursos sobre a complexidade assintótica (big-O e o resto) de métodos de classes de coleção .NET (Dictionary<K,V>, List<T> etc ...)?

Eu sei que a documentação da biblioteca C5 inclui algumas informações sobre ele ( exemplo ), mas eu estou interessado em coleções padrão NET também ... (e as informações dos PowerCollections também seria bom).

Foi útil?

Solução

MSDN lista estes:

etc. Por exemplo:

O SortedList (TKey, TValue) genérico classe é uma árvore de busca binária com O (N log N) de recuperação, onde n é o número de elementos no dicionário. Neste, é semelhante ao SortedDictionary (TKey, TValue) genérico classe. As duas classes têm semelhante modelos de objecto, e ambos têm O (N log N) recuperação. Onde as duas classes diferem está em uso de memória e velocidade de inserção e remoção:

SortedList (TKey, TValue) usa menos memória do que SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) possui inserção mais rápida e remoção operações para dados não ordenados, O (N log N) em oposição a O (n) para SortedList (TKey, TValue).

Se a lista é preenchida de uma só vez a partir de dados classificados, SortedList (TKey, TValue) é mais rápido do que SortedDictionary (TKey, TValue).

Outras dicas

Esta página resume alguns dos comlplexities tempo para vários tipos de coleção com Java, embora eles devem ser exatamente o mesmo for .NET.

Eu tomei as tabelas a partir dessa página e alterou / expandiu-los para o .NET framework. Veja também as páginas MSDN para SortedDictionary e SortedList , que detalham as complexidades de tempo necessário para várias operações.

Pesquisa 

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.

Recuperação e Inserção 

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.

A supressão deve ter a mesma complexidade como a inserção para a coleção associada.

SortedList tem algumas particularidades notáveis ??para inserção e recuperação.

inserção (Add método):

Este método é uma operação O (n) para dados não ordenados, em que n é Count. Isto é um O (N log N) operação, se o novo elemento é adicionado no final do Lista. Se a inserção provoca um redimensionamento, o funcionamento é O (n).

Retrieval (propriedade de item):

Recuperando o valor desta propriedade é uma operação de O (N log N), onde N é Contagem. Definir a propriedade é um O (N log N) operação, se a chave é já no SortedList <(Of <(TKey, TValue>)>). Se a chave não está no lista, definindo a propriedade é um O (n) operação para dados não triados, ou O (log n) se o novo elemento é adicionado ao fim da lista. Se a inserção faz com que um redimensionar, o funcionamento é O (n).

Note que ArrayList é equivalente a List<T> em termos de complexidade de todas as operações.

Eu não sei em geral (a outra resposta só postou talvez lhe dá exatamente o que você está depois) - mas você pode refletir este e outros métodos de curso usando ILSpy (um pouco estranho com código FSharp, true) e Isto eventualmente produz essa função como 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;
}

A aprovação assim que este não é exatamente o código 'bom' em C # termos - mas a presença do loop while(true) implica que não pode ser O (1), pelo menos; como por aquilo que ele realmente é ... bem, minha cabeça dói muito para descobrir:)

Esta página apresenta notas curtas sobre alguns prós e contras chave para a maioria .NET Colecções:

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

Não há tal coisa como "complexidade de classes de coleção". Em vez disso, diferentes operações sobre estas coleções têm diferentes complexidades. Por exemplo, adicionando um elemento a um Dictionary<K, V> ...

... se aproxima de um O (1) operação. Se a capacidade tem de ser aumentada para acomodar o novo elemento, este método torna-se um O (n) operação, onde n é Count.

Considerando que a recuperação de um elemento de uma Dictionary<K, V> ...

... se aproxima de um O (1) operação.

A documentação diz que é construir em uma árvore binária, e não menciona rastrear o elemento máximo. Se a documentação é correcta, o que significa que deve ser O (N log N). Costumava haver pelo menos um erro na documentação coleções (referindo-se a uma estrutura de dados lastreados em matriz como uma árvore de busca binária), mas que foi corrigido.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top