C# - Escolhendo a classe de coleção correta para sua necessidade

 A .NET Base Class Library (BCL) tem uma grande variedade de classes de coleção à sua disposição e isso faz com que gerenciar coleções de objetos seja uma tarefa tranquila.

Embora seja bom ter tantas classes disponíveis, pode ser complicado ter que escolher a coleção certa para usar em uma determinada situação.

Por mais difícil que seja, escolher a coleção correta pode ser fundamental para que o desempenho e a manutenção da sua aplicação sejam otimizados.

Para você ter uma ideia a seguir temos uma lista das classes que tratam coleções na plataforma .NET :

Dictionary<TKey,TVale>, SortedDictionary<TKey,TValue>, SortedList<TKey,TValue>, List<T>, LinkedList<T>,
HashSet<T>, SortedSet<T>, Stack<T>, Queue<T>, Array, ArrayList, HashTable

Então antes de decidir qual coleção usar primeiro você deve decidir se vale a pena usar uma coleção.

Você deve usar uma coleção quando pelo menos uma das seguintes afirmações for verdadeira:

- Elementos individuais servem a propósitos semelhantes e são de igual importância.
- O número de elementos é desconhecido ou não está fixado em tempo de compilação.
- Você precisa dar suporte à iteração sobre todos os elementos.
- Você precisa dar suporte a ordenação dos elementos.
- Você precisa expor os elementos de uma biblioteca em que o consumidor vai esperar um tipo de coleção.

E então !!! você sabe escolher entre as classes acima qual a melhor para uma determinada situação ?

Neste artigo eu procuro dar um visão geral sobre essas coleções e qual classe é adequada para determinada situação.

As coleções genéricas

As coleções genéricas foram introduzidos a partir da versão 2.0 da plataforma .NET no namespace System.Collections.Generic.

Estas coleções em geral atendem a 90% das necessidades quando precisamos gerenciar coleções de objetos e você deve dar uma atenção especial a elas quando precisar escolher uma classe para realizar esta tarefa.

É importante notar que as coleções genéricas são não sincronizadas. Esta decisão foi tomada por razões de desempenho, porque dependendo de como você está usando as suas coleções é possível que a sincronização não seja necessária ou pode ser que ela seja necessária em um nível superior ao nível de método de sincronização simples. Além disso, o acesso simultâneo de leitura (gravar tudo no início) é sempre seguro, mas para acesso concorrente misto você deverá sincronizar a coleção ou usar uma das coleções concorrentes.

Vamos então analisar cada uma destas coleções, seus prós e seus contras e depois fazer um resumo para ajudar a fazer uma comparação entre elas.

1- Classes de coleções associativas

As coleções associativas armazenam um valor na coleção fornecendo uma chave que é usada para adicionar/remover/procurar o item.

Assim, o recipiente associa o valor com a chave. Essas coleções são mais úteis quando você precisa procurar/manipular uma coleção usando um valor de chave. Por exemplo, se você quiser procurar um pedido em uma coleção de pedidos por um código de pedido, você pode ter uma coleção associativa onde chave é o id do pedido e o valor é o pedido.

A classe Dictionary<TKey,TVale> é provavelmente a classe associativa mais utilizada visto ser a classe mais rápida para realizar operações de pesquisa/inclusão/exclusão. Isso é devido a utilização de uma hashtable; como as chaves são um hash, o tipo da chave deve implementar GetHashCode() e Equals() de forma apropriada ou deve fornecer um um IEqualityComparer externo para o dicionário em construção.

As operações de inclusão/exclusão/pesquisa de itens no dicionário consomem um tempo constante amortizado - O(1) - o que significa que não importa quão grande o dicionário fica, o tempo gasto para encontrar algo permanece relativamente constante.

Isso é altamente desejável para realizar pesquisas com ótimo desempenho. A única desvantagem é que o dicionário, por usar uma hashtable, não esta ordenado, de forma que você não pode facilmente atravessar os itens de um dicionário em ordem.

A coleção SortedDictionary<TKey,TValue> é semelhante à classe Dictionary<TKey,TValue> na forma de usar mas muito diferente em sua execução.

A classe SortedDictionary<TKey,TValye> usa uma árvore  binária para manter os itens em ordem pela chave. Como consequência desta ordenação, o tipo usado para a chave deve implementar a interface IComparable<TKey> de modo que as chaves possam ser corretamente ordenadas.

O dicionário ordenado gasta um pouco de tempo a mais na pesquisa devido a capacidade de manter os itens em ordem, assim as operações de inclusão/exclusão/pesquisa em um dicionário ordenado são logarítmicas : O(log n).

Uma recomendação para usar a classe SortedDictionary<TKey,TValue> é quando você quiser realizar pesquisas rápidas, mas também quer ser capaz de manter a coleção em ordem pela chave.

As duas classes têm modelos de objeto semelhantes, e ambos têm recuperação O(log n). A diferença entre as duas classes está no uso da memória e na velocidade de inclusão e remoção de itens. Assim :

A classe SortedList<TKey,TValue> é uma classe associativa ordenada. Da mesma forma que SortedDictionary<TKey,TValue>, esta classe usa uma chave para classificar os pares chave-valor.

Ao contrário da classe SortedDictionary, no entanto, os itens em uma SortedList são armazenados como uma array ordenado de itens. Isto significa que inserções e deleções são lineares - O(n) - porque apagar ou adicionar um item pode implicar a transferência de todos os itens para cima ou para baixo na lista.

O tempo de pesquisa, porém, é O(log n) porque a coleção SortedList pode usar uma busca binária para encontrar qualquer item na lista por sua chave.

Então uma recomendação de uso para esta coleção é quando você deseja realizar pesquisas rápidas, quer manter a coleção ordenada e deseja realizar poucas operações de inclusão e remoção de itens.

2- Classes não associativas

As outras classes de contêineres são não associativas. Eles não usam chaves para manipular a coleção, mas contam com o próprio objeto a ser armazenado ou alguns outros meios (como índice) para manipular a coleção.

a- List<T>

A classe List<T> é um recipiente de armazenamento básico contíguo. Algumas pessoas podem chamar isso de um vetor ou matriz dinâmica. Essencialmente ela é uma série de itens que crescem uma vez que sua capacidade atual for excedida.

Como os itens são armazenados de forma contígua como uma matriz, você pode acessar os itens na coleção List<T> usando um índice de forma muito rápida. No entanto inserir e remover no início ou no meio da List<T> leva mais tempo porque você deve mudar todos os itens para cima ou para baixo quando for excluir ou inserir.

No entanto, a adição e remoção no final de uma List<T> é uma operação amortizada constante - O(1). Normalmente uma List<T> é uma coleção padrão para uso quando você não tem quaisquer outras restrições e, normalmente, você deve dar preferência a utilização da coleção List<T> mesmo sobre matrizes, a menos quando temos a certeza que o tamanho continuará a ser absolutamente fixo.

b- LinkedList<T>

A classe LinkedList<T> é uma implementação básica de uma lista duplamente ligada. Isso significa que você pode adicionar ou remover itens no meio de uma lista ligada muito rapidamente (porque não há nenhum item para mover para cima ou para baixo na memória contígua), mas você também perde a capacidade de indexar itens pela posição rapidamente.

Na maioria das vezes, tendemos a favorecer o uso da classe List<T> sobre LinkedList<T> a menos que você está fazendo um monte de inclusões e exclusões de itens na coleção, caso em que usar a classe LinkedList<T> pode fazer mais sentido.

c- HashSet<T>

A coleção HashSet<T> é uma coleção ordenada de itens exclusivos. Isto significa que a coleção não pode ter itens duplicados e nenhuma ordem é mantida.

Logicamente, isso é muito semelhante a ter um coleção Dictionary<TKey,TValue> onde o TKey e TValue referem-se ao mesmo objeto.

A classe HashSet<T> baseia-se no modelo de conjuntos matemáticos e fornece operações de conjuntos de alto desempenho semelhantes a acessar as chaves das coleções Dictionary<TKey, TValue> ou Hashtable. Em termos simples, a classe HashSet<T> pode ser considerada como uma coleção Dictionary<TKey, TValue> sem valores.

Por exemplo, se você receber um pedido para um determinado código de fornecedor, você pode querer verificar para garantir que o código do fornecedor pertence ao conjunto de códigos de fornecedores. Nesses casos, o HashSet<T> é útil para realizar consultas super-rápidas onde a ordem não é importante.

d- SortedSet<T>

A coleção SortedSet<T> representa uma coleção de objetos que é mantida em ordem classificada.

Uma coleção SortedSet<T> mantém uma ordem classificada quando elementos são inseridos e excluídos sem afetar o desempenho. Elementos duplicados não são permitidos.

Uma coleção SortedSet<T> é uma árvore binária em que a chave e o valor são o mesmo objeto. Isso significa que as operações de inclusão/remoção/pesquisas são logarítmica - O(log n) - mas existe um ganho na habilidade de iterar sobre os itens em ordem. Para esta coleção ser eficaz, o tipo T deve implementar a interface IComparable<T> ou você precisa fornecer um IComparer<T> externo.

e- Stack<T> e Queue<T>

As coleções Stack<T> e Queue <T> são duas coleções que permitem lidar com uma coleção sequencial de objetos de forma muito específica.

A coleção Stack<T> é um recipiente LIFO(last in first out) onde os itens são adicionados e removidos do topo da pilha. Normalmente, isso é útil em situações onde você quer empilhar ações e, em seguida, ser capaz de desfazer essas ações em ordem inversa, conforme necessário.

A coleção Queue<T> por outro lado é um recipiente FIFO(firs-in first-out) que adiciona itens no final da fila e remove itens a partir da inicio. Isso é útil para situações onde você precisa processar os itens na ordem em que eles vieram, como um spooler de impressão ou filas de espera.

Resumindo temos :

Coleção

Ordenamento

Armazenamento
Contíguo ?

Acesso
Direto ?

Pesquisa
Eficiente

Manipulação

Eficiente

Notas

Dictionary

Não ordenado

Sim

Via Key

Key: O(1)

O(1)

Melhor para pesquisas de alto desempenho.
SortedDictionary Classificado Não Via Key Key:  O(log n) O(log n)

Compromisso de velocidade do dicionário e ordenação, usa árvore de pesquisa binária

SortedList

Classificado

Sim

Via Key

Key: O(log n)

O(n)

Muito semelhante ao SortedDictionary, exceto que a árvore é implementada em uma matriz, por isso, procura mais rapidamente em dados pré-carregados, mas carrega mais lentamente

List

O usuário tem controle preciso sobre a ordem dos elementos

Sim

Via Index

Index: O(1)

Value: O(n)

O(n)

Melhor para listas menores, onde o acesso direto é necessário e não há classificação.

LinkedList

O usuário tem controle preciso sobre a ordem dos elementos

Não

Não

Value: O(n)

O(1)

Melhor para listas em que inserir / excluir no meio é comum e não é necessário acesso direto.

HashSet

Não ordenado

Sim

 Via Key

Key: O(1)

O(1)

 A única coleção não ordenada, como um dicionário, exceto chave e valor, é o mesmo objeto.

SortedSet

Classificado

Não

Via Key

Key: O(log n)

O(log n)

Coleta classificada exclusiva, como SortedDictionary, exceto chave e valor, são o mesmo objeto.

Stack

LIFO

Sim

Only Top

Top: O(1)

O(1)*

Essencialmente o mesmo que List <T>, exceto apenas o processo como LIFO

Queue

FIFO

Sim

Only Front

Front: O(1)

O(1)

Essencialmente o mesmo que List <T>, exceto apenas o processo como FIFO

As coleções originais

As classes de coleção originais são consideradas obsoletas pelos desenvolvedores e pela própria Microsoft. Na verdade, eles indicam que você deve sempre favorecer as coleções genéricas ou concorrentes, e apenas usar as coleções originais quando você está lidando com o legado. NET.

Como essas coleções estão fora de moda, vamos apenas mencionar brevemente a coleção original e seus equivalentes genéricos:

Em geral, as coleções mais antigas não são type-safe e, em alguns casos, menos eficazes do que os seus homólogos genéricos. Mais uma vez, a única razão que você deve atentar quando for usar essas coleções antigas é verificar a compatibilidade com código legado.

As coleções concorrentes

As coleções concorrentes são novas e existem a partir da versão 4.0 da plataforma .NET; elas estão incluídas no namespace System.Collections.Concurrent. Essas coleções são otimizados para uso em situações onde o acesso de leituras/escritas multi-threaded à uma coleção for desejado.

Se este for o cenário considere a sua utilização.

A seguir um resumo das coleções concorrentes:

ConcurrentQueue - versão Thread-safe da coleção queue(FIFO).
ConcurrentStack - versão Thread-safe da coleção stack (LIFO).
ConcurrentBag - Coleção Thread-safe não ordenada de objetos - Otimizada para situações onde uma thread pode tanto ser lida como escrita;
ConcurrentDictionary - versão Thread-safe de um dictionary. - Otimizada para leituras múltiplas;
BlockingCollection - Os leitores podem bloquear até que os itens estejam disponíveis para leitura. Os escritores podem bloquear até que o espaço esteja disponível para escrever (se limitada).;

Ao utilizar estas coleções considere que o acesso será protected o que afeta bastante o desempenho, neste caso verifique se a utilização de threads sincronizadas não o obteria um melhor desempenho.

As considerações aqui feitas valem tanto para linguagem C# como para a linguagem VB .NET.

Embora a sintaxe usada para as coleções seja a da linguagem C#. Ex: List<T> VB .NET => List(Of T)

Até o próximo artigo.

1Jo 1:5 E esta é a mensagem que dele ouvimos, e vos anunciamos: que Deus é luz, e nele não há trevas nenhumas.

1Jo 1:6 Se dissermos que temos comunhão com ele, e andarmos nas trevas, mentimos, e não praticamos a verdade;

1Jo 1:7 mas, se andarmos na luz, como ele na luz está, temos comunhão uns com os outros, e o sangue de Jesus seu Filho nos purifica de todo pecado.

Referências:

José Carlos Macoratti