number - using array in c#




Estruturas de dados.NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary-Velocidade, memória e quando usar cada uma delas? (10)

Estruturas de dados .NET:

Mais para conversar sobre por que ArrayList e List são realmente diferentes

Matrizes

Como um usuário afirma, Arrays é a coleção "old school" (sim, arrays são considerados uma coleção, embora não façam parte de System.Collections ). Mas, o que é "old school" sobre arrays em comparação com outras coleções, ou seja, aquelas que você listou em seu título (aqui, ArrayList e List (Of T))? Vamos começar com o básico olhando para Arrays.

Para começar, Arrays no Microsoft .NET são "mecanismos que permitem tratar vários itens [logicamente relacionados] como uma única coleção" (consulte o artigo vinculado). O que isso significa? Arrays armazenam membros individuais (elementos) sequencialmente, um após o outro na memória com um endereço inicial. Usando o array, podemos acessar facilmente os elementos armazenados seqüencialmente, começando naquele endereço.

Além disso e contrariamente à programação de 101 concepções comuns, os Arrays podem ser bastante complexos:

Os arrays podem ser de dimensão única, multidimensionais ou jadded (os arrays irregulares valem a pena ser lidos). Os próprios arrays não são dinâmicos: uma vez inicializados, um array de tamanho n reserva espaço suficiente para conter um número n de objetos. O número de elementos na matriz não pode aumentar ou diminuir. Dim _array As Int32() = New Int32(100) reserva espaço suficiente no bloco de memória para a matriz conter 100 objetos do tipo primitivo Int32 (nesse caso, a matriz é inicializada para conter 0s). O endereço desse bloco é retornado para _array .

De acordo com o artigo, o Common Language Specification (CLS) requer que todos os arrays sejam baseados em zero. Matrizes no .NET suportam matrizes não baseadas em zero; no entanto, isso é menos comum. Como resultado do "common-ness" dos arrays baseados em zero, a Microsoft gastou muito tempo otimizando seu desempenho ; portanto, as matrizes de dimensão única, baseadas em zero (SZs) são "especiais" - e realmente a melhor implementação de uma matriz (em oposição a multidimensional, etc.) - porque as SZs têm instruções específicas de linguagem intermediária para manipulá-las.

Os arrays são sempre passados ​​por referência (como um endereço de memória) - uma peça importante do quebra-cabeça do Array para saber. Enquanto eles fazem verificação de limites (lançará um erro), a verificação de limites também pode ser desabilitada em matrizes.

Novamente, o maior obstáculo para as matrizes é que elas não são redimensionáveis. Eles têm uma capacidade "fixa". Apresentamos ArrayList e List (Of T) à nossa história:

ArrayList - lista não genérica

A ArrayList (junto com List(Of T) - embora existam algumas diferenças críticas, aqui, explicadas posteriormente) - talvez seja melhor considerada como a próxima adição a coleções (no sentido amplo). ArrayList herda da interface IList (um descendente de 'ICollection'). ArrayLists, eles próprios, são bulkier - exigindo mais overhead - do que as listas.

IList permite que a implementação trate ArrayLists como listas de tamanho fixo (como Arrays); entretanto, além da funcionalidade adicional adicionada por ArrayLists, não há vantagens reais em usar ArrayLists com tamanho fixo, pois ArrayLists (over Arrays) nesse caso são marcadamente mais lentos.

De minha leitura, ArrayLists não pode ser irregular: "Usando matrizes multidimensionais como elementos ... não é suportado". Mais uma vez, outro prego no caixão de ArrayLists. ArrayLists também não são "tipados" - o que significa que, abaixo de tudo, uma ArrayList é simplesmente uma Array dinâmica de objetos: Object[] . Isso requer muito boxe (implícito) e unboxing (explícito) ao implementar o ArrayLists, adicionando novamente a sua sobrecarga.

Pensamento não substanciado: acho que me lembro de ler ou ter ouvido de um de meus professores que ArrayLists são uma espécie de filho conceitual bastardo da tentativa de mudar de Arrays para Coleções do tipo List, ou seja, uma vez tendo sido uma grande melhoria para Arrays, eles não são mais a melhor opção, já que um maior desenvolvimento foi feito em relação às coleções

List (Of T): O que ArrayList se tornou (e esperava ser)

A diferença no uso de memória é significativa o suficiente para onde uma List (Of Int32) consumiu 56% menos memória do que uma ArrayList contendo o mesmo tipo primitivo (8 MB vs. 19 MB na demonstração vinculada acima cavalheiro: novamente, vinculado overhead ) - embora este é um resultado composto pela máquina de 64 bits. Essa diferença realmente demonstra duas coisas: primeiro (1), um "objeto" do tipo Int32 encaixotado (ArrayList) é muito maior que um tipo primitivo Int32 puro (List); segundo (2), a diferença é exponencial como resultado do funcionamento interno de uma máquina de 64 bits.

Então, qual é a diferença e o que é uma List (Of T) ? MSDN define uma List(Of T) como "... uma lista fortemente tipificada de objetos que podem ser acessados ​​por índice." A importância aqui é o bit "fortemente tipado": uma List (Of T) "reconhece" os tipos e armazena os objetos como seu tipo. Portanto, um Int32 é armazenado como um Int32 e não como um tipo de Object . Isso elimina os problemas causados ​​pelo boxe e pelo unboxing.

MSDN especifica essa diferença só entra em jogo ao armazenar tipos primitivos e não tipos de referência. Além disso, a diferença realmente ocorre em grande escala: mais de 500 elementos. O que é mais interessante é que a documentação do MSDN lê, "É vantajoso para usar a implementação específica do tipo da classe List (Of T) em vez de usar a classe ArrayList ...."

Essencialmente, List (Of T) é ArrayList, mas melhor. É o "equivalente genérico" de ArrayList. Como o ArrayList, não é garantido que ele seja classificado até que seja classificado (veja figura). List (Of T) também tem alguma funcionalidade adicional.

O .NET tem muitas estruturas de dados complexas. Infelizmente, alguns deles são bastante semelhantes e nem sempre tenho certeza de quando usar um e quando usar outro. A maioria dos meus livros em C # e Visual Basic fala sobre eles até certo ponto, mas eles nunca entram em detalhes reais.

Qual é a diferença entre Array, ArrayList, List, Hashtable, Dictionary, SortedList e SortedDictionary?

Quais são enumeráveis ​​(IList - pode fazer 'foreach' loops)? Quais usam pares chave / valor (IDict)?

E quanto a pegada de memória? Velocidade de inserção? Velocidade de recuperação?

Existem outras estruturas de dados que merecem ser mencionadas?

Ainda estou procurando mais detalhes sobre o uso de memória e velocidade (notação Big-O).


Aqui estão algumas dicas gerais para você:

  • Você pode usar foreach em tipos que implementam IEnumerable . IList é essencialmente um IEnumberable com propriedades Count e Item (acessando itens usando um índice baseado em zero). IDictionary por outro lado significa que você pode acessar itens por qualquer índice hashable.

  • Array , ArrayList e List todos implementam IList . Dictionary , SortedDictionary e Hashtable implementam IDictionary .

  • Se você estiver usando o .NET 2.0 ou superior, é recomendável usar contrapartes genéricas dos tipos mencionados.

  • Para complexidade de tempo e espaço de várias operações nesses tipos, você deve consultar sua documentação.

  • Estruturas de dados .NET estão no namespace System.Collections . Existem bibliotecas de tipos, como PowerCollections que oferecem estruturas de dados adicionais.

  • Para obter uma compreensão completa das estruturas de dados, consulte recursos como o CLRS .


Eles são muito bem soletrados em intellisense. Basta digitar System.Collections. ou System.Collections.Generics (preferencial) e você obterá uma lista e uma breve descrição do que está disponível.


Em cima da minha cabeça:

  • Array * - representa um array de memória old-school - como um alias para um array type[] normal. Pode enumerar. Não pode crescer automaticamente. Eu diria que a inserção e a velocidade de retrocesso são muito rápidas.

  • ArrayList - matriz crescente automaticamente. Adiciona mais sobrecarga. Pode enum., Provavelmente mais lento que uma matriz normal, mas ainda bem rápido. Estes são muito usados ​​no .NET

  • List - um dos meus favs - pode ser usado com genéricos, então você pode ter uma matriz fortemente tipada, por exemplo List<string> . Fora isso, age muito como ArrayList

  • Hashtable - simples hashtable antigo. O (1) para O (n) o pior caso. Pode enumerar as propriedades value e keys e fazer pares key / val

  • Dictionary - mesmo que acima, apenas fortemente tipado via genéricos, como Dictionary<string, string>

  • SortedList - uma lista genérica classificada. Retardado na inserção desde que tem que descobrir onde colocar as coisas. Pode enum., Provavelmente o mesmo na recuperação, uma vez que não tem que recorrer, mas a exclusão será mais lenta do que uma simples lista antiga.

Eu costumo usar List e Dictionary o tempo todo - uma vez que você comece a usá-los fortemente tipado com genéricos, é realmente difícil voltar aos padrões não-genéricos.

Existem muitas outras estruturas de dados também - há o KeyValuePair que você pode usar para fazer algumas coisas interessantes, há um SortedDictionary que pode ser útil também.


Existem diferenças sutis e não tão sutis entre coleções genéricas e não genéricas. Eles simplesmente usam diferentes estruturas de dados subjacentes. Por exemplo, o Hashtable garante um escritor-muitos-leitores sem sincronização. Dicionário não.


Hashtables / Dictionaries são O (1) desempenho, o que significa que o desempenho não é uma função do tamanho. Isso é importante saber.

EDIT: Na prática, a complexidade de tempo médio para consultas de Hashtable / Dictionary <> é O (1).


Primeiro, todas as coleções no .NET implementam IEnumerable.

Segundo, muitas das coleções são duplicadas porque os genéricos foram adicionados na versão 2.0 do framework.

Portanto, embora as coleções genéricas provavelmente adicionem recursos, na maior parte:

  • List é uma implementação genérica do ArrayList.
  • Dicionário é uma implementação genérica do Hashtable

Matrizes são uma coleção de tamanho fixo que você pode alterar o valor armazenado em um determinado índice.

SortedDictionary é um IDictionary que é classificado com base nas chaves. SortedList é um IDictionary que é classificado com base em um IComparer necessário.

Assim, as implementações do IDictionary (aquelas que suportam KeyValuePairs) são: * Hashtable * Dictionary * SortedList * SortedDictionary

Outra coleção que foi adicionada no .NET 3.5 é o Hashset. É uma coleção que suporta operações de conjunto.

Além disso, o LinkedList é uma implementação de lista vinculada padrão (a lista é uma lista de matriz para recuperação mais rápida).


Uma observação importante sobre o Hashtable vs Dictionary para engenharia de negociação sistemática de alta frequência: Thread Safety Issue

Hashtable é thread-safe para uso por vários threads. Os membros estáticos públicos do dicionário são thread-safe, mas não é garantido que os membros da instância o sejam.

Portanto, Hashtable continua sendo a escolha "padrão" nesse sentido.


Estruturas de Dados e Coleções de C # mais populares

  • Matriz
  • ArrayList
  • Lista
  • LinkedList
  • Dicionário
  • HashSet
  • Pilha
  • Fila
  • SortedList

O C # .NET tem muitas estruturas de dados diferentes, por exemplo, uma das mais comuns é uma matriz. No entanto, o C # vem com muitas estruturas de dados mais básicas. Escolher a estrutura de dados correta para usar é parte da escrita de um programa bem estruturado e eficiente.

Neste artigo, irei sobre as estruturas de dados C # internas, incluindo as novas introduzidas no C # .NET 3.5. Observe que muitas dessas estruturas de dados se aplicam a outras linguagens de programação.

Matriz

A estrutura de dados talvez mais simples e mais comum é a matriz. O array AC # é basicamente uma lista de objetos. Suas características definidoras são que todos os objetos são do mesmo tipo (na maioria dos casos) e há um número específico deles. A natureza de uma matriz permite acesso muito rápido aos elementos com base em sua posição na lista (também conhecida como índice). O array AC # é definido assim:

[object type][] myArray = new [object type][number of elements]

Alguns exemplos:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Como você pode ver no exemplo acima, uma matriz pode ser inicializada sem elementos ou a partir de um conjunto de valores existentes. Inserir valores em uma matriz é simples, desde que eles se ajustem. A operação se torna dispendiosa quando há mais elementos do que o tamanho da matriz, ponto no qual a matriz precisa ser expandida. Isso leva mais tempo porque todos os elementos existentes devem ser copiados para a nova matriz maior.

ArrayList

A estrutura de dados C #, ArrayList, é uma matriz dinâmica. O que isso significa é que um ArrayList pode ter qualquer quantidade de objetos e de qualquer tipo. Essa estrutura de dados foi projetada para simplificar os processos de adição de novos elementos em uma matriz. Sob o capô, um ArrayList é um array cujo tamanho é duplicado toda vez que ele fica sem espaço. Dobrar o tamanho da matriz interna é uma estratégia muito eficaz que reduz a quantidade de cópia de elementos a longo prazo. Nós não vamos entrar na prova disso aqui. A estrutura de dados é muito simples de usar:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

A desvantagem da estrutura de dados ArrayList é que é preciso converter os valores recuperados em seu tipo original:

int arrayListValue = (int)myArrayList[0]

Fontes e mais informações você pode encontrar aqui :


Se possível, use genéricos. Isso inclui:

  • Listar em vez de ArrayList
  • Dicionário em vez de HashTable




data-structures