Como e quando abandonar o uso de arrays em C#?

https://stackoverflow.com/questions/75976

09-06-2019
|

Pergunta

Sempre me disseram que adicionar um elemento a um array acontece assim:

Uma cópia vazia da matriz+1Element é criada e, em seguida, os dados da matriz original são copiados nela, então os novos dados para o novo elemento são então carregados

Se isso for verdade, então usar um array em um cenário que requer muita atividade de elemento é contra-indicado devido à utilização de memória e CPU, correto?

Se for esse o caso, você não deveria tentar evitar o máximo possível o uso de um array quando estiver adicionando muitos elementos?Você deveria usar iStringMap?Em caso afirmativo, o que acontece se você precisar de mais de duas dimensões E precisar adicionar muitas adições de elementos.Você apenas sofre o impacto no desempenho ou há algo mais que deveria ser usado?

Solução

Veja o genérico List<T> como um substituto para matrizes.Eles suportam a maioria das mesmas coisas que os arrays fazem, incluindo a alocação de um tamanho de armazenamento inicial, se desejar.

Outras dicas

Isso realmente depende do que você quer dizer com "adicionar".

Se você diz:

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

Então, não, isso não cria um novo array e é de fato a maneira mais rápida de alterar qualquer tipo de IList no .NET.

Se, no entanto, você estiver usando algo como ArrayList, List, Collection, etc.em seguida, chamando o método "Adicionar" poderia crie um novo array - mas eles são espertos, eles não apenas redimensionam em 1 elemento, eles crescem geometricamente, então se você estiver adicionando muitos valores apenas de vez em quando, será necessário alocar um novo array .Mesmo assim, você pode usar a propriedade "Capacidade" para forçá-la a crescer de antemão, se souber quantos elementos está adicionando (list.Capacity += numberOfAddedElements)

Em geral, prefiro evitar o uso de array.Basta usar Lista<T>.Ele usa internamente um array de tamanho dinâmico e é rápido o suficiente para a maior parte do uso.Se você estiver usando matrizes multidimensionais, use List<List<List<T>>> se for necessário.Não é muito pior em termos de memória e é muito mais simples de adicionar itens.

Se você estiver com 0,1% de uso que requer velocidade extrema, certifique-se de que os acessos à sua lista sejam realmente o problema antes de tentar otimizá-los.

Se você for adicionar/remover muitos elementos, basta usar uma Lista.Se for multidimensional, você sempre pode usar List<List<int>> ou algo assim.

Por outro lado, as listas são menos eficientes que os arrays se o que você está fazendo principalmente é atravessando a lista, porque os arrays estão todos em um só lugar no cache da CPU, onde os objetos em uma lista estão espalhados por todo o lugar.

Se você deseja usar um array para uma leitura eficiente, mas vai "adicionar" elementos com frequência, você tem duas opções principais:

1) Gere-o como uma Lista (ou Lista de Listas) e então use ToArray() para transformá-lo em uma estrutura de array eficiente.

2) Aloque o array para ser maior do que o necessário e, em seguida, coloque os objetos nas células pré-alocadas.Se você precisar de ainda mais elementos do que os pré-alocados, basta realocar o array quando ele for preenchido, dobrando o tamanho a cada vez.Isso fornece desempenho de redimensionamento O (log n) em vez de O (n), como seria com uma matriz realocada uma vez por adição.Observe que é assim que o StringBuilder funciona, oferecendo uma maneira mais rápida de anexar continuamente a uma string.

Quando abandonar o uso de arrays

Em primeiro lugar, quando semântica de arrays não combine com sua intenção - Precisa de uma coleção em crescimento dinâmico?Um conjunto que não permite duplicatas?Uma coleção que deve permanecer imutável?Evite matrizes em todos esses casos.Isso é 99% dos casos.Apenas afirmando o ponto básico óbvio.
Em segundo lugar, Quando você é não codificação para criticidade absoluta de desempenho - Isso é cerca de 95% dos casos. Matrizes têm melhor desempenho marginalmente, especialmente em iteração.Quase sempre nunca importa.
Quando você é não forçado por uma discussão com params palavra-chave - Eu só queria params aceitou qualquer IEnumerable<T> ou melhor ainda, uma linguagem se constrói para denotar um seqüência (e não um tipo de estrutura).
Quando você é não escrevendo código legado ou lidando com interoperabilidade

Resumindo, é muito raro você realmente precisar de um array.Acrescentarei por que alguém pode evitá-lo?

O maior motivo para evitar arrays é conceitual.Os arrays estão mais próximos da implementação e mais distantes da abstração.Matrizes transmitem mais como isso é feito que o que é feito o que vai contra o espírito das linguagens de alto nível.Isso não é surpreendente, considerando que os arrays estão mais próximos do metal, eles vêm diretamente de um tipo especial (embora internamente o array seja uma classe).Não quero ser pedagógico, mas os arrays realmente se traduzem em um significado semântico muito raramente necessário.A semântica mais útil e frequente é a de coleções com quaisquer entradas, conjuntos com itens distintos, mapas de valores-chave, etc., com qualquer combinação de variantes adicionáveis, somente leitura, imutáveis e que respeitam a ordem.Pense nisso: você pode querer uma coleção adicionável ou uma coleção somente leitura com itens predefinidos sem nenhuma modificação adicional, mas com que frequência sua lógica se parece com "Quero uma coleção adicionável dinamicamente, mas apenas um número fixo deles e eles também devem ser modificáveis "?Muito raro eu diria.

Array foi projetado durante a era pré-genérica e imita a genericidade com muitos hacks de tempo de execução e mostrará suas estranhezas aqui e ali.Algumas das capturas que encontrei:

Covariância quebrada.

string[] strings = ...
object[] objects = strings;
objects[0] = 1; //compiles, but gives a runtime exception.

Matrizes podem fornecer referência a uma estrutura!.Isso é diferente de qualquer outro lugar.Uma amostra:

struct Value { public int mutable; }

var array = new[] { new Value() };  
array[0].mutable = 1; //<-- compiles !
//a List<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
print array[0].mutable // 1, expected or unexpected? confusing surely

Métodos implementados em tempo de execução como ICollection<T>.Contains pode ser diferente para estruturas e classes.Não é grande coisa, mas se você esquecer de substituir não genérico Equals corretamente para tipos de referência que esperam que a coleção genérica procure genérico Equals, você obterá resultados incorretos.

public class Class : IEquatable<Class>
{
    public bool Equals(Class other)
    {
        Console.WriteLine("generic");
        return true;
    }
    public override bool Equals(object obj)
    {
        Console.WriteLine("non generic");
        return true;
    } 
}

public struct Struct : IEquatable<Struct>
{
    public bool Equals(Struct other)
    {
        Console.WriteLine("generic");
        return true;
    }
    public override bool Equals(object obj)
    {
        Console.WriteLine("non generic");
        return true;
    } 
}

class[].Contains(test); //prints "non generic"
struct[].Contains(test); //prints "generic"

O Length propriedade e [] indexador ativado T[] parecem ser propriedades regulares que você pode acessar através de reflexão (o que deve envolver alguma mágica), mas quando se trata de árvores de expressão você tem que cuspir exatamente o mesmo código que o compilador faz.Há ArrayLength e ArrayIndex métodos para fazer isso separadamente.Um desses pergunta aqui.Outro exemplo:
```
Expression<Func<string>> e = () => new[] { "a" }[0];
//e.Body.NodeType == ExpressionType.ArrayIndex

Expression<Func<string>> e = () => new List<string>() { "a" }[0];
//e.Body.NodeType == ExpressionType.Call;
```

Como abandonar o uso de arrays

O substituto mais comumente usado é List<T> que tem uma API mais limpa.Mas é uma estrutura que cresce dinamicamente, o que significa que você pode adicionar a um List<T> no final ou insira em qualquer lugar para qualquer capacidade.Não há substituto para o comportamento exato de um array, mas as pessoas geralmente usam arrays como uma coleção somente leitura, onde você não pode adicionar nada ao seu final.Um substituto é ReadOnlyCollection<T>.Eu carrego este método de extensão:

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}

Quando o array é redimensionado, um novo array deve ser alocado e o conteúdo copiado.Se você estiver modificando apenas o conteúdo do array, será apenas uma atribuição de memória.

Portanto, você não deve usar arrays quando não souber o tamanho do array, ou o tamanho provavelmente mudará.No entanto, se você tiver uma matriz de comprimento fixo, ela será uma maneira fácil de recuperar elementos por índice.

ArrayList e List aumentam o array em mais de um quando necessário (acho que é dobrando o tamanho, mas não verifiquei a fonte).Eles geralmente são a melhor escolha quando você está construindo um array de tamanho dinâmico.

Quando seus benchmarks indicam que o redimensionamento do array está desacelerando seriamente o seu aplicativo (lembre-se: a otimização prematura é a raiz de todos os males), você pode avaliar a gravação de uma classe de array personalizada com comportamento de redimensionamento ajustado.

Geralmente, se você deseja ter o MELHOR desempenho de pesquisa indexada, é melhor construir uma lista primeiro e depois transformá-la em um array, pagando assim uma pequena penalidade no início, mas evitando qualquer penalidade posterior.Se o problema é que você adicionará continuamente novos dados e removerá dados antigos, convém usar um ArrayList ou List por conveniência, mas lembre-se de que eles são apenas Arrays de casos especiais.Quando eles "crescem", eles alocam um array completamente novo e copiam tudo nele, o que é extremamente lento.

ListaArray é apenas um array que cresce quando necessário.Add é amortizado O(1), apenas tome cuidado para garantir que o redimensionamento não acontecerá em um momento ruim.Inserir é O(n) todos os itens à direita devem ser movidos.Remover é O(n) todos os itens à direita devem ser movidos.

Também é importante ter em mente que List não é uma lista vinculada.É apenas um ArrayList digitado.A lista documentação observa que ele tem melhor desempenho na maioria dos casos, mas não diz por quê.

A melhor coisa a fazer é escolher uma estrutura de dados apropriada ao seu problema.Isso depende de MUITAS coisas e então você pode querer navegar no System.Collections.Generic Espaço para nome.

Neste caso específico, eu diria que se você conseguir encontrar um bom valor-chave Dicionário seria sua melhor aposta.Possui insert e remove que se aproxima de O(1).No entanto, mesmo com um Dicionário você deve ter cuidado para não permitir que ele redimensione seu array interno (uma operação O(n)).É melhor dar-lhes bastante espaço especificando uma capacidade inicial maior do que você espera usar no construtor.

-Rick

Um array padrão deve ser definido com um comprimento que reserve toda a memória necessária em um bloco contíguo.Adicionar um item ao array o colocaria dentro do bloco de memória já reservada.

Matrizes são ótimas para poucas gravações e muitas leituras, especialmente aquelas de natureza iterativa - para qualquer outra coisa, use uma das muitas outras estruturas de dados.

Você está certo, uma matriz é ótima para pesquisas.No entanto, modificações no tamanho do array são caras.

Você deve usar um contêiner que dê suporte a ajustes de tamanho incrementais no cenário em que estiver modificando o tamanho da matriz.Você pode usar um ArrayList que permite definir o tamanho inicial e verificar continuamente o tamanho em relação à capacidade e, em seguida, aumentar a capacidade em uma grande parte para limitar o número de redimensionamentos.

Ou você pode simplesmente usar uma lista vinculada.Então, no entanto, as pesquisas são lentas ...

Esta postagem no fórum pode ou não ser útil para você em relação à eficiência de vários tipos de array:Matrizes C# - multidimensionais vs lexicográficas

Se eu acho que adicionarei muitos itens à coleção ao longo de sua vida útil, usarei uma Lista.Se eu tiver certeza de qual será o tamanho da coleção quando for declarada, usarei um array.

Outra ocasião em que geralmente uso um array sobre uma Lista é quando preciso retornar uma coleção como uma propriedade de um objeto - não quero que os chamadores adicionem itens a essa coleção por meio dos métodos Add da Lista, mas quero que eles adicionem itens à coleção através da interface do meu objeto.Nesse caso, pegarei a Lista interna e chamarei ToArray e retornarei um array.

Se você vai fazer muitas adições, e você não fará acesso aleatório (como myArray[i]).Você pode considerar usar uma lista vinculada (LinkedList<T>), porque nunca terá que "crescer" como o List<T> implementação.Tenha em mente, porém, que você só pode realmente acessar itens em um LinkedList<T> implementação usando o IEnumerable<T> interface.

A melhor coisa que você pode fazer é alocar o máximo de memória necessária antecipadamente, se possível.Isto impedirá .LÍQUIDO de ter que fazer chamadas adicionais para colocar memória na pilha.Caso contrário, faz sentido alocar em pedaços de cinco ou qualquer número que faça sentido para o seu aplicativo.

Esta é uma regra que você pode aplicar a qualquer coisa.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow