Existe alguma razão para usar uma matriz quando as listas estão disponíveis? [fechadas]

30

Parece que o List<T>C # pode fazer tudo o que uma matriz pode fazer e muito mais, além de parecer tão eficiente em memória e desempenho quanto uma matriz.

Então, por que eu iria querer usar uma matriz?

Obviamente, não estou perguntando sobre casos em que uma API ou outra restrição externa (ou seja, a função Main) exige que eu use uma matriz ... Estou apenas perguntando sobre a criação de novas estruturas de dados no meu próprio código.

JoelFan
fonte
56
Para implementarList<T>
ratchet freak
43
is also just as efficient in memory and performance as an array- hum. De onde você tirou essa noção?
Oded
12
Várias dimensões como var test = new string[5,5];)
Knerd
7
Há também a matriz de bytes [] comumente usada.
SBoss
11
Para C # especificamente, Eric Lippert escreveu sobre isso em blogs.msdn.com/b/ericlippert/archive/2008/09/22/… .
Mephy

Respostas:

26

A mesma razão que eu não dirijo um caminhão quando vou trabalhar. Eu não uso algo que não usarei os recursos.

Antes de tudo, uma matriz é uma construção primitiva; portanto, uma matriz é mais rápida e eficiente que uma Lista <>, com certeza, portanto seu argumento não é verdadeiro. A matriz também está disponível em todos os lugares e é conhecida pelos desenvolvedores que usam diferentes idiomas e plataformas.

O motivo mais importante de eu usar uma matriz em vez de uma Lista <> é sugerir que os dados são de comprimento fixo . Se não adicionar ou remover nenhum item dessa coleta de dados, quero garantir que o tipo reflita isso.

Outra coisa é dizer que você está implementando uma nova estrutura de dados e que leu alguns documentos sobre ela. Agora, ao implementar algoritmos específicos, você nem sempre pode confiar na implementação de outro tipo de um objetivo geral. Ele muda do .NET para o Mono e até entre diferentes versões da estrutura.

E às vezes é mais fácil portar um pedaço de código que usa uma matriz em vez de um tipo dependente da estrutura.

Mert Akcakaya
fonte
4
Como uma matriz é "mais rápida" que uma lista, considerando que List<T>é implementada usando uma matriz? Se você conhece a contagem de elementos de antemão (o que você precisa saber ao usar uma matriz), pode usar esse conhecimento ao inicializar a lista.
Theodoros Chatzigiannakis
11
@TheodorosChatzigiannakis Ao usar uma matriz, alocamos a memória e simplesmente fazemos atribuições, simples malloc (), sem sobrecarga. Ao usar a Lista <>, você "Adicionará" itens e ao adicionar os itens Lista <> fará algumas verificações de limites e chamará o método GuaranteCapacity, que copiará o conteúdo para outra matriz recém-alocada, se a capacidade atual não for suficiente. Isso significa que, se você não precisar alocar dinamicamente nova memória, o desempenho da Lista não será tão bom quanto o array.
Mert Akcakaya
4
O que você está dizendo é correto, mas ele assume que quer que nós não sabemos a contagem de elemento de antemão (caso em que, matrizes não são de qualquer maneira útil) ou que faça saber a contagem de elementos de antemão mas nós deliberadamente não fazer uso no caso da lista. Se nós fazer usar a contagem de elementos para inicializar a lista com a capacidade desejada, temos apenas uma alocação array (até chegar a essa capacidade), assim que pagar os mesmos custos de desempenho. Todas as outras operações comuns são iguais (pesquisa, recuperação por índice, atribuição por índice), exceto para mais adições (que as matrizes não possuem).
Theodoros Chatzigiannakis
3
@TheodorosChatzigiannakis: as matrizes são mais rápidas que as listas. Basta executar uma referência simples para verificar.
Mehrdad
11
@TheodorosChatzigiannakis, Sim, mas ainda há verificações de limite.
Mert Akcakaya
18

Você precisa de matrizes para gerenciar sua coleção de estruturas mutáveis , é claro, e o que faríamos sem elas.

struct EvilMutableStruct { public double X; } // don't do this

EvilMutableStruct[] myArray = new EvilMutableStruct[1];
myArray[0] = new EvilMutableStruct()
myArray[0].X = 1; // works, this modifies the original struct

List<EvilMutableStruct> myList = new List<EvilMutableStruct>();
myList.Add(new EvilMutableStruct());
myList[0].X = 1; // does not work, the List will return a *copy* of the struct

(observe que pode haver alguns casos em que uma matriz de estrutura mutável é desejável, mas geralmente esse comportamento diferente de estruturas mutáveis ​​dentro de matrizes versus outras coleções é uma fonte de erros que devem ser evitados)


Mais a sério, você precisa de uma matriz se quiser passar um elemento por referência . ie

Interlocked.Increment(ref myArray[i]);  // works
Interlocked.Increment(ref myList[i]);   // does not work, you can't pass a property by reference

Isso pode ser útil para código seguro de thread sem bloqueio.


Você precisará de uma matriz se desejar, rápida e eficientemente, inicializar sua coleção de tamanho fixo com o valor padrão .

double[] myArray = new double[1000]; // contains 1000 '0' values
                                     // without further initialisation

List<double> myList = new List<double>(1000) // internally contains 1000 '0' values, 
                                             // since List uses an array as backing storage, 
                                             // but you cannot access those
for (int i =0; i<1000; i++) myList.Add(0);   // slow and inelegant

(observe que seria possível implementar um construtor para a lista que faz o mesmo, mas o c # não oferece esse recurso)


você precisa de uma matriz se quiser copiar com eficiência partes da coleção

Array.Copy(array1, index1, array2, index2, length) // can't get any faster than this

double[,] array2d = new double[10,100];
double[] arraySerialized = new double[10*100];
Array.Copy(array2d, 0, arraySerialized, 0, arraySerialized.Length);
// even works for different dimensions

(novamente, isso também pode ser implementado para a lista, mas esse recurso não existe no c #)

HugoRune
fonte
Se um tipo deve representar um grupo de variáveis ​​relacionadas, mas independentes, coladas com fita adesiva (por exemplo, as coordenadas de um ponto), uma estrutura de campo exposto é a melhor representação. Se uma variável deve conter vários desses grupos, uma matriz desse tipo de estrutura é a melhor representação. Não se deve usar estruturas mutáveis ​​em locais onde se deseja um objeto, mas isso não significa que se deva usar objetos ou coisas que fingem ser objetos em locais onde se deseja que um monte de variáveis ​​coladas à fita adesiva.
Supercat 10/14 /
Existem algumas situações em que você pode querer uma estrutura mutável, como quando você precisa do último bit de desempenho e não pode permitir alocações e referências de heap e, nesse caso, uma matriz de estruturas é sua melhor aposta. Bom ensaio aqui . Mas eu discordo que uma classe não deve representar "um monte de variáveis ​​reunidas". Estruturas e classes conceitualmente são as mesmas, as diferenças são principalmente devido aos detalhes da implementação.
HugoRune
Se alguém deseja usar uma coleção de referências a objetos mutáveis ​​como uma coleção de grupos independentes de variáveis ​​independentes, deve-se estabelecer e manter uma invariância de que cada elemento identifique um objeto ao qual nenhuma outra referência não-efêmera existe em nenhum lugar do universo. Certamente isso pode ser feito (e geralmente é), mas não há nada na linguagem ou estrutura que ajude o programador a defender essa invariante. Por outro lado, uma matriz de tamanho 100 de um tipo de estrutura com quatro campos de instância encapsulará automática e permanentemente 400 variáveis ​​independentes.
Supercat
Acho que esses comentários são o lugar errado para discutirmos mais esse assunto e, como você adicionou sua própria resposta , não parece haver necessidade de duplicar essas informações aqui. Basta dizer que matrizes podem ser usadas para gerenciar estruturas mutáveis. Se e quando usar o comportamento de implementação dessas estruturas para impor determinadas restrições de dados realmente vai além do escopo da minha resposta.
HugoRune
15

Então, por que eu iria querer usar uma matriz?

Raramente , você terá um cenário em que sabe que precisa de um número fixo de elementos. Da perspectiva do design, isso deve ser evitado. Se você precisar de três coisas, a natureza dos negócios significa que muitas vezes precisará de quatro no próximo lançamento.

Ainda assim, quando esse cenário raro realmente ocorre, é útil usar uma matriz para impor essa invariante de tamanho fixo. Ele fornece um sinal para outros programadores de que é um tamanho fixo e ajuda a evitar o uso indevido onde alguém adiciona ou remove um elemento - quebrando as expectativas em outras partes do código.

Telastyn
fonte
23
O tamanho das matrizes não é definido como pedra no momento em que se escreve o código. Pode, e geralmente é, uma variável de tempo de execução. Isso nunca muda após a criação da matriz .
11
Não é incomum lidar com um número fixo de elementos. Se você estiver trabalhando com pontos 3D, provavelmente não estará trabalhando com pontos 5D em nenhum momento no futuro. O maior problema das matrizes é que elas são mutáveis ​​e não têm rótulos convenientes anexados aos seus elementos.
Doval
3
As listas do @JanDvorak podem diminuir ou crescer e, portanto, não fazem sentido em nenhum contexto que envolva um número fixo de elementos.
Doval
9
Raramente? Nem todo mundo trabalha em monstruosidades corporativas ultra-configuráveis ​​e super complicadas.
whatsisname
3
É muito comum ter um número fixo de elementos. Apenas certifique-se de que o comprimento seja definido por uma constante; assim, quando a próxima versão aumentar o número de elementos de 3 para 4, basta alterar a constante e tudo o que depende disso é adaptado.
10114 Hans
9

Sua pergunta já foi respondida antes .

e também parece tão eficiente em memória e desempenho quanto uma matriz.

Não é. Da pergunta que eu vinculei:

List/foreach:  3054ms (589725196)
Array/foreach: 1860ms (589725196)

As matrizes são duas vezes mais rápidas em certos casos importantes. Estou certo de que o uso da memória também difere de maneira não trivial.

Como a principal premissa de sua pergunta foi derrotada, presumo que isso responda à sua pergunta. Além disso, algumas vezes as matrizes são impostas a você pela API do Win32, ou pelo sombreador da sua GPU ou por outra biblioteca que não seja da DotNet.

Mesmo no DotNet, alguns métodos consomem e / ou retornam matrizes (como String.Split). O que significa que agora você deve comer o custo de ligar ToListeToArray o tempo todo, ou deve conformar e usar a matriz, possivelmente continuando o ciclo propagando isso para usuários ruins do seu código.

Mais perguntas e respostas sobre o estouro de pilha sobre este tópico:

Superbest
fonte
Curiosamente, essa resposta indica que, se você usar loops indexados à moda antiga ( em vez de foreach ), a diferença de desempenho será mínima.
user949300
3

Além dos motivos listados em outras respostas, o array literal leva menos caracteres para declarar:

var array = new [] { "A", "B", "C" };
var list = new List<string>() { "A", "B", "C" };

O uso da matriz em vez de Listtorna o código um pouco mais curto e um pouco mais legível nos casos em que (1) você precisa passar qualquer IEnumerable<T>literal ou (2) onde outras funcionalidades deList não importam e você precisa usar algum tipo de lista literal.

Fiz isso ocasionalmente em testes de unidade.

ikh
fonte
11
Sim apenas para adicionar. Também funciona de que você precisa passar um IList <T>
Esben Skov Pedersen
+1, muitas vezes tenho alguma operação para alguns objetos do mesmo tipo que não estão em uma coleção. É fácil, curto e claro de escrever foreach( var x in new []{ a, b, c ) ) DoStuff( x )ou new []{ a, b, c ).Select( ... )etc #
stijn
3

Isso é estritamente da perspectiva do OO.

Embora eu não consiga pensar em um motivo para transmitir apenas uma matriz, certamente vejo situações em que uma representação de matriz interna à classe é provavelmente a melhor escolha.

Embora existam outras opções que oferecem características semelhantes, nenhuma parece tão intuitiva quanto uma matriz para problemas ao lidar com permutações de processamento, aninhadas para loops, representação de matrizes, bitmaps e algoritmos de intercalação de dados.

Há um número substancial de campos científicos que dependem extensivamente da matemática matricial. (por exemplo, processamento de imagem, correção de erro de dados, processamento de sinal digital, uma resma de problemas matemáticos aplicados). A maioria dos algoritmos nesses campos é escrita em termos do uso de matrizes / matrizes multidimensionais. Portanto, seria mais natural implementar os algoritmos conforme eles são definidos, em vez de torná-los mais amigáveis ​​ao "software" à custa de perder os vínculos diretos com os papéis nos quais os algoritmos se baseiam.

Como eu disse, nesses casos, você provavelmente pode usar listas, mas isso adiciona mais uma camada de complexidade sobre o que já são algoritmos complexos.

Dunk
fonte
3

Na verdade, isso vale para outras linguagens que também possuem listas (como Java ou Visual Basic). Há casos em que você precisa usar uma matriz porque um método retorna uma matriz em vez de uma Lista.

Em um programa real, não acho que uma matriz seja usada com muita frequência, mas às vezes você sabe que os dados terão um tamanho fixo e você gosta do pequeno ganho de desempenho obtido ao usar uma matriz. A micro-otimização seria um motivo válido, assim como um método para retornar uma lista ou a necessidade de uma estrutura de dados multidimensional.

Dylan Meeus
fonte
11
Muitos idiomas nem têm coleções separadas de listas e matrizes. Por outro lado, usar list<T>where vector<T>will work é uma péssima idéia em C / C ++.
Gort the Robot
11
"Como um método retorna uma matriz" - esta é uma característica incorreta do Java, forçando os programadores a codificar o código com "Arrays.asList (x)". T [] deve pelo menos implementar Iterable <T>
kevin Cline
4
@StevenBurnap - certamente é desastrosamente ruim em C, porque não há como compilar esse código.
Pete Becker
@PeteBecker A expressão vector<T> x compila muito bem para mim no C . :-)
svick
Desculpe, eu quis dizer o equivalente C enrolado à mão list<T>. Basicamente, eu já vi muitos problemas de desempenho causados ​​por desenvolvedores apenas usando listas por padrão quando uma matriz era uma escolha melhor.
Gort the Robot
1

Bem, encontrei um uso para matrizes em um jogo que escrevi. Usei-o para criar um sistema de inventário com um número fixo de slots. Isso teve vários benefícios:

  1. Eu sabia exatamente quantos slots de inventário aberto o objeto de jogo tinha ao observar e ver quais slots eram nulos.
  2. Eu sabia exatamente em qual índice cada item estava.
  3. Ainda era uma matriz "digitada" (Item [] Inventory), para que eu pudesse adicionar / remover os objetos do tipo "Item".

Imaginei que, se alguma vez precisasse "aumentar" o tamanho do inventário, poderia fazê-lo transferindo os itens antigos para a nova matriz, mas como o inventário foi corrigido pelo espaço na tela e não era necessário aumentá-lo dinamicamente / menor, funcionou bem para o propósito para o qual eu estava usando.

mt
fonte
1

Se você estiver percorrendo todos os elementos de uma lista, não, uma matriz não é necessária; a seleção 'próxima' ou 'arbitrária sem substituição' será adequada.

Mas se o seu algoritmo precisar de acesso aleatório aos elementos da coleção, sim, uma matriz será necessária.

Isso é um pouco análogo a "é necessário ir?". Em uma linguagem moderna razoável, isso não é necessário. Mas se você separar as abstrações, em algum momento, isso é tudo o que está realmente disponível para você, ou seja, a única maneira de implementar essas abstrações é com o recurso 'desnecessário'. (É claro que a analogia não é perfeita, acho que ninguém diz que matrizes são uma prática ruim de programação; são fáceis de entender e pensar).

Mitch
fonte
A lista <T> também oferece acesso aleatório. Claro, é implementado com uma matriz, mas isso não precisa incomodar você, o usuário. Portanto, na melhor das hipóteses, você ofereceu um único motivo para usar matrizes: para implementar List<T>.
@ delnan Acho que esse é o meu ponto com relação às abstrações. Às vezes, é melhor pensar em termos de uma matriz, não apenas por razões de eficiência. (é claro que às vezes é muito melhor pensar em uma lista vinculada e muito melhor do que pensar em uma lista (sem se preocupar com links ou de outra forma como ela é implementada), e muito melhor apenas com uma coleção.
Mitch
0

Compatibilidade herdada.

Todos formam experiência pessoal:

Programadores legados - meu colega usa matrizes em todos os lugares, já faz mais de 30 anos, boa sorte mudando de idéia com suas novas idéias fangled.

Código legado - foo (barra de matriz []), certifique-se de que você pode usar uma função de matriz de lista / vetor / coleção, mas se você não estiver usando nenhum desses recursos adicionais, é mais fácil usar uma matriz para começar, geralmente mais legível sem a alternância de tipos.

Chefe legado - meu chefe era um bom programador antes de ingressar na administração há muitos anos e ainda acha que está atualizado: "estava usando matrizes" pode encerrar uma reunião, explicando o que é uma coleção e pode custar o almoço de todos.

Skeith
fonte
3
colegas que estão 20 anos atrás da curva e um chefe que quer saber quais os tipos de dados que você está usando ... Eu amo este site para me lembrando o quanto pior o meu trabalho poderia ser
JoelFan
11
cerca de 40% do que fazemos é incorporado projeto onde as discussões são realizadas em KB, ele gosta de mim, não hes hes ultrapassadas specalised dizer lol
Skeith
0

1) Não existe uma versão multidimensional da lista. Se seus dados tiverem mais de uma dimensão, será muito ineficiente usar listas.

2) Quando você lida com um grande número de pequenos tipos de dados (por exemplo, um mapa em que tudo o que você tem é um byte para o tipo de terreno), pode haver diferenças consideráveis ​​de desempenho devido ao armazenamento em cache. A versão do array carrega vários itens por leitura de memória, a versão da lista carrega apenas um. Além disso, a versão do array contém várias vezes mais células no cache que a versão da lista - se você estiver processando repetidamente os dados, isso pode fazer uma grande diferença se a versão do array se encaixar no cache, mas a versão da lista não.

Para um caso extremo, considere o Minecraft. (Sim, não está escrito em C #. O mesmo motivo se aplica.)

Loren Pechtel
fonte
0

Uma matriz de 100 elementos de algum tipo T encapsula 100 variáveis ​​independentes do tipo T. Se T for um tipo de valor que possui um campo público mutável do tipo Q e um do tipo R, cada elemento da matriz encapsulará variáveis ​​independentes dos tipos Q e R. A matriz como um todo encapsulará 100 variáveis ​​independentes do tipo Q e 100 variáveis ​​independentes do tipo R; qualquer uma dessas variáveis ​​pode ser acessada individualmente sem afetar nenhuma outra. Nenhum tipo de coleção além de matrizes pode permitir que os campos de estruturas sejam usados ​​como variáveis ​​independentes.

Se T passou a ser um tipo de classe com campos mutáveis ​​públicos do tipo Q e R, cada elemento da matriz mantém a única referência, em qualquer lugar do universo, a uma instância de T, e se nenhum dos elementos da matriz jamais ser modificado para identificar um objeto para o qual existe qualquer referência externa, o array efetivamente encapsulará 100 variáveis ​​independentes do tipo Q e 100 variáveis ​​independentes do tipo R. Outros tipos de coleções podem imitar o comportamento de uma matriz, mas se o único objetivo da matriz é encapsular 100 variáveis ​​do tipo Q e 100 do tipo R, encapsular cada par de variáveis ​​em seu próprio objeto de classe é uma maneira cara de fazer isso. Mais distante,o uso de uma matriz ou coleção do tipo de classe mutável cria a possibilidade de que as variáveis ​​identificadas pelos elementos da matriz não sejam independentes .

Se um tipo deve se comportar como algum tipo de objeto, deve ser um tipo de classe ou uma estrutura de campo privado que não oferece outro meio de mutação além da substituição. Se, no entanto, um tipo deve se comportar como um monte de variáveis ​​relacionadas, mas independentes, coladas com fita adesiva, deve-se usar um tipo que é um monte de variáveis ​​coladas com fita adesiva - uma estrutura de campo exposto . Matrizes desse tipo são muito eficientes para trabalhar e possuem semânticas muito limpas. O uso de qualquer outro tipo levará a semântica confusa, desempenho inferior ou ambos.

supercat
fonte
0

Uma diferença importante é a alocação de memória. Por exemplo, atravessar uma lista vinculada pode resultar em muitas falhas de cache e desempenho mais lento, enquanto uma matriz representa um pedaço contíguo de memória contendo várias instâncias de algum tipo de dados específico, e atravessá-la para ter mais chances de atingir a CPU cache.

Obviamente, uma matriz de referências a objetos pode não se beneficiar tanto dos acertos no cache, pois a desreferenciação ainda pode levá-lo a qualquer lugar na memória.

Depois, há implementações de lista, como ArrayList, que implementam uma lista usando uma matriz. Eles são primitivos úteis para ter.

Rory Hunter
fonte
2
A pergunta pergunta especificamente sobre o tipo .Net List<T>, que não é implementado usando uma lista vinculada, mas usando uma matriz (é essencialmente equivalente a ArrayList<T>em Java).
precisa
-2

Aqui estão algumas orientações que você pode usar para selecionar Arraye quando selecionar List.

  • Use Arrayao retornar de um método.
  • Use Listcomo a variável ao construir o valor de retorno (dentro do método). Em seguida, use .ToArray()ao retornar do método.

Em geral, use um Arrayquando você não pretende que o consumidor adicione itens à coleção. Use Listquando você pretende que o consumidor adicione itens à coleção.

Arraydestina-se a lidar com coleções "estáticas", enquanto Listdestina-se a lidar com coleções "dinâmicas".

Daniel Lidström
fonte
2
A regra que você sugere é arbitrária e provavelmente resultará em código ineficiente que executa cópias desnecessárias. No mínimo, você precisa de alguma forma de justificativa para isso.
Jules
@Jules Eu achei a experiência do desenvolvedor muito mais importante do que as micro-otimizações. Eu nunca tenho problemas de desempenho nesse nível.
Daniel Lidström
No entanto, não vejo como a experiência do desenvolvedor é aprimorada por essa regra. Requer que você adivinhe o que os clientes do seu código vão querer fazer com os valores retornados e torne seu código menos conveniente quando você errar, e ainda assim não vejo nenhuma vantagem nisso. O desempenho pode ser uma preocupação secundária, mas eu não a sacrificaria para seguir uma regra que não ganha nada.
Jules
@ Jules Acho que se resume a sua preferência então. Prefiro tratar os valores de retorno como constantes; portanto, prefiro usar em Arrayvez de List. É bom ouvir seus pensamentos!
Daniel Lidström
Você já pensou em usar UmmodifiableLists?
Jules