Por que usamos matrizes em vez de outras estruturas de dados?

Enquanto programava, não vi uma instância em que uma matriz seja melhor para armazenar informações do que outra forma. Na verdade, eu havia imaginado que os "recursos" adicionados nas linguagens de programação haviam melhorado isso e com isso os substituíam. Vejo agora que eles não são substituídos, mas recebem nova vida, por assim dizer.

Então, basicamente, qual é o sentido de usar matrizes?

Não é tanto por que usamos matrizes do ponto de vista do computador, mas por que usamos matrizes do ponto de vista de programação (uma diferença sutil). O que o computador faz com a matriz não era o ponto da questão.

Hora de voltar no tempo para uma lição. Embora não pensemos muito sobre essas coisas em nossas linguagens gerenciadas sofisticadas de hoje, elas são construídas com a mesma base, então vamos ver como a memória é gerenciada em C.

Antes de mergulhar, uma rápida explicação do significado do termo " ponteiro ". Um ponteiro é simplesmente uma variável que "aponta" para um local na memória. Ele não contém o valor real nesta área da memória, contém o endereço de memória para ele. Pense em um bloco de memória como uma caixa de correio. O ponteiro seria o endereço dessa caixa de correio.

Em C, uma matriz é simplesmente um ponteiro com um deslocamento, o deslocamento especifica a que distância da memória procurar. Isso fornece tempo de acesso O (1) .

  MyArray   [5]
     ^       ^
  Pointer  Offset

Todas as outras estruturas de dados se baseiam nisso ou não usam memória adjacente para armazenamento, resultando em um tempo de pesquisa de acesso aleatório ruim (embora haja outros benefícios em não usar memória seqüencial).

Por exemplo, digamos que tenhamos uma matriz com 6 números (6,4,2,3,1,5), na memória, ficaria assim:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

Em uma matriz, sabemos que cada elemento está próximo um do outro na memória. A matriz CA (chamada MyArrayaqui) é simplesmente um ponteiro para o primeiro elemento:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

Se quiséssemos procurar MyArray[4], internamente seria acessado assim:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

Como podemos acessar diretamente qualquer elemento da matriz adicionando o deslocamento ao ponteiro, podemos procurar qualquer elemento na mesma quantidade de tempo, independentemente do tamanho da matriz. Isso significa que obter MyArray[1000]levaria a mesma quantidade de tempo que obter MyArray[5].

Uma estrutura de dados alternativa é uma lista vinculada. Esta é uma lista linear de ponteiros, cada um apontando para o próximo nó

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

Observe que eu criei cada "nó" em seu próprio bloco. Isso ocorre porque não é garantido que eles sejam (e provavelmente não serão) adjacentes na memória.

Se eu quiser acessar o P3, não posso acessá-lo diretamente, porque não sei onde ele está na memória. Tudo o que sei é onde está a raiz (P1), então, em vez disso, tenho que começar em P1 e seguir cada ponteiro para o nó desejado.

Este é um tempo de pesquisa O (N) (o custo de pesquisa aumenta à medida que cada elemento é adicionado). É muito mais caro chegar ao P1000 do que ao P4.

Estruturas de dados de nível superior, como hashtables, pilhas e filas, podem usar uma matriz (ou várias matrizes) internamente, enquanto Listas Vinculadas e Árvores Binárias geralmente usam nós e ponteiros.

Você pode se perguntar por que alguém usaria uma estrutura de dados que requer passagem linear para procurar um valor em vez de apenas usar uma matriz, mas eles têm seus usos.

Pegue nossa matriz novamente. Desta vez, quero encontrar o elemento da matriz que contém o valor '5'.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

Nessa situação, não sei qual deslocamento adicionar ao ponteiro para encontrá-lo, então tenho que começar em 0 e trabalhar até encontrar. Isso significa que eu tenho que executar 6 verificações.

Por esse motivo, a pesquisa de um valor em uma matriz é considerada O (N). O custo da pesquisa aumenta à medida que a matriz aumenta.

Lembre-se acima, onde eu disse que às vezes o uso de uma estrutura de dados não seqüencial pode ter vantagens? A busca de dados é uma dessas vantagens e um dos melhores exemplos é a Árvore Binária.

Uma Árvore Binária é uma estrutura de dados semelhante a uma lista vinculada, no entanto, em vez de vincular a um único nó, cada nó pode vincular a dois nós filhos.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

Quando os dados são inseridos em uma árvore binária, eles usam várias regras para decidir onde colocar o novo nó. O conceito básico é que, se o novo valor for maior que os pais, ele será inserido à esquerda; se for menor, será inserido à direita.

Isso significa que os valores em uma árvore binária podem ficar assim:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

Ao pesquisar em uma árvore binária pelo valor de 75, precisamos apenas visitar 3 nós (O (log N)) devido a esta estrutura:

• 75 é menor que 100? Olhe o nó direito
• 75 é maior que 50? Olhe para o nó esquerdo
• Há os 75!

Embora existam 5 nós em nossa árvore, não precisamos examinar os dois restantes, porque sabíamos que eles (e seus filhos) não podiam conter o valor que estávamos procurando. Isso nos dá um tempo de pesquisa que, na pior das hipóteses, significa que precisamos visitar todos os nós, mas, na melhor das hipóteses, precisamos apenas visitar uma pequena porção dos nós.

É aí que as matrizes são batidas, elas fornecem um tempo de pesquisa O (N) linear, apesar do tempo de acesso O (1).

Esta é uma visão geral incrivelmente de alto nível sobre estruturas de dados na memória, pulando muitos detalhes, mas espero que ilustre a força e a fraqueza de uma matriz em comparação com outras estruturas de dados.

Para acesso aleatório O (1), que não pode ser derrotado.

Nem todos os programas fazem a mesma coisa ou são executados no mesmo hardware.

Geralmente, é a resposta para a existência de vários recursos de idioma. Matrizes são um conceito básico de ciência da computação. Substituir matrizes por listas / matrizes / vetores / qualquer estrutura de dados avançada impactaria severamente o desempenho e seria absolutamente impraticável em vários sistemas. Há vários casos em que o uso de um desses objetos de coleta de dados "avançados" deve ser usado devido ao programa em questão.

Na programação de negócios (como a maioria de nós faz), podemos atingir hardware relativamente poderoso. Usar uma lista em C # ou vetor em Java é a escolha certa a ser feita nessas situações, porque essas estruturas permitem que o desenvolvedor alcance os objetivos mais rapidamente, o que, por sua vez, permite que esse tipo de software seja mais destacado.

Ao escrever software incorporado ou sistema operacional, uma matriz pode ser a melhor escolha. Enquanto uma matriz oferece menos funcionalidade, ela ocupa menos RAM, e o compilador pode otimizar o código com mais eficiência para pesquisas em matrizes.

Tenho certeza de que estou deixando de fora uma série de benefícios para esses casos, mas espero que você entenda.

Uma maneira de observar as vantagens de matrizes é ver onde é necessário o recurso de acesso O (1) das matrizes e, portanto, colocar em maiúscula:

1. Nas tabelas de consulta do seu aplicativo (uma matriz estática para acessar determinadas respostas categóricas)

2. Memoização (resultados de funções complexas já calculados, para que você não calcule o valor da função novamente, digamos log x)

3. Aplicativos de visão computacional de alta velocidade que requerem processamento de imagem ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )