quinta-feira, 19 de março de 2015

Programação em C - Matrizes esparsas

Olá pessoal, nesse post iremos falar sobre matrizes esparsas. Uma matriz esparsa é aquela em que nem todos os elementos estão realmente presentes ou são necessários.

Imagine uma matriz muito grande onde a grande maioria dos elementos são repetidos (exemplo: a grande maioria dos elementos é 0 no caso de uma matriz de inteiros). Entenda como elemento repetido como sendo a mesma informação.

Por questão de simplicidade, vamos assumir que o elemento repetido seja um 0. Então pense numa matriz onde a grande maioria dos elementos é igual a 0. Veja a imagem:

Perceba que a grande maioria dos elementos da matriz acima são iguais a 0, pois temos no total 36 elementos (matriz 6x6), mas apenas 6 elementos (aproximadamente 16%) são iguais a 1.

É claro que a matriz anterior é pequena, mas imagine uma matriz muito grande onde a maioria esmagadora dos elementos são repetidos. Matrizes multidimensionais podem consumir uma enorme quantidade de memória (as necessidades de armazenamento estão exponencialmente relacionadas ao tamanho da matriz).

A pergunta é: seria interessante guardarmos essa matriz do jeito que ela está representada? Não, pois teríamos um desperdício muito grande de espaço.

Uma aplicação bem popular que utiliza matrizes esparsas é um programa de uma planilha.

Para ganharmos espaço, temos que implementar esse tipo de matriz de uma outra forma. Você não precisa implementar a matriz anterior do jeito que ela está (os elementos iguais a 0 não precisam está ocupando espaço), ela será apenas uma abstração, também chamada de matriz lógica: a matriz que você pensa que existe no sistema. Já a matriz física é a matriz que realmente existe no computador.

Essa outra forma que falei anteriormente seria guardando as posições dos elementos diferentes de 0. Assim nós teremos uma matriz bem menor, pois o número de elementos diferente de 0 é muito pequeno comparado a quantidade total de elementos da matriz. 

Obviamente como eu estou guardando somente as posições (não estou guardando o valor), assume-se que eu sei qual o valor de cada posição, um exemplo seria uma matriz binária onde ou o elemento é 0 ou é 1 como é o caso da matriz do nosso exemplo.

Mas e se precisar guardar o valor? Ficaria algo desse tipo:

1 2 10
2 3 20
3 4 30

Na matriz acima estou dizendo que na linha 1 e coluna 2 temos o valor 10, na linha 2 e coluna 3 temos o valor 20 e na linha 3 e coluna 4 temos o valor 30. Como ficaria para o nosso exemplo da matriz B ?

1 1 1
2 2 1
3 4 1
4 3 1
5 5 1
6 6 1

Obviamente como trata-se de uma matriz binária, não precisaríamos guardar o valor, mas imagine uma outra matriz que precisasse guardar o valor. Inicialmente tínhamos uma matriz 6x6 e agora temos uma matriz 6x3. A dimensão dessa nova matriz é:

(m*n - z)*3

m*n é o total de elementos da primeira matriz e "z" é a quantidade de zeros. 

Vamos lá: (6*6 - 30)*3 = 6*3 = 18. 18 é a dimensão da nova matriz. A antiga matriz tinha dimensão 36 (6*6). Se a dimensão da nova matriz é menor do que a dimensão da matriz antiga, então vale a pena implementar matriz esparsa.

Resumindo, a nossa nova tabela guarda as posições de cada elemento diferente de 0. Por questões didáticas, colocaremos só duas colunas, ou seja, não guardaremos o valor, pois assumiremos que todos os valores não-nulos serão iguais a 1.

Sendo "i" a linha e "j" a coluna, é interessante que você deixe o "i" ordenado, veja:

1 3
4 6
5 3
7 2
8 1

Caso você queira saber se o elemento da linha 6 e coluna 2 (i=6 e j=2) é 0 ou 1, quando você perceber que da linha 5 foi para a linha 7, quer dizer que o elemento não está na nova matriz, se não está na nova matriz, então é porque ele é 0. Facilitou bastante não é mesmo? Poderia também ter uma matriz ordenada pelo "j" (coluna) ou pelo valor enfim.

Eu posso adicionar apontadores com a informação da ordem, uma lista ligada que seria uma lista de elementos com apontadores que mostram a ordem. Escrevendo a matriz dessa forma ficará bem mais fácil de navegar nela.

Vamos entrar mais na parte do código, iremos implementar matriz esparsa utilizando lista encadeada utilizando a linguagem C.

Criaremos uma estrutura com as seguintes informações:

1) dados que serão armazenados
2) posição lógica dentro da matriz
3) ligações com o elemento anterior e próximo

Cada estrutura é colocada na lista com os elementos inseridos de forma ordenada baseada no índice da matriz. Veja como fica nossa estrutura (struct):


Perceba que definimos uma estrutura chamada "celula" e ela contém um valor, a linha, a coluna, um apontador (ponteiro) para o próximo elemento e um outro apontador para o elemento anterior. Iremos implementar uma lista duplamente ligada (encadeada).

As variáveis globais "primeiro" e "ultimo" apontam para o início e fim da lista respectivamente.

O código que irei colocar está todo comentado, possui várias funções tais como inserir (passando a celula), deletar (passando a posição - linha e coluna) etc.

Veja o código completo:


A grande vantagem de se utilizar lista encadeada é o uso eficiente de memória, a desvantagem fica por conta dela ter que acessar através de uma busca linear as células na lista. Para resolver isso, tente utilizar uma árvore binária.

Referências:


Livro "C Completo e Total" (terceira edição) - Capítulo 21

Numerical Recipes in C (Third Edition) - 2.7

Quaisquer dúvidas, deixem nos comentários, até a próxima!


Nenhum comentário: