Índice >
Lista >
Matriz Esparsa e Lista Cruzada >
Avaliação de Desempenho
Instituto de Ciências Matemáticas de São Carlos
Departamento de
Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina
Usabilidade - Matriz Esparsa
Quando a representação de listas cruzadas é vantajosa em relação à
representação convencional (bidimensional) ?
Fator Espaço
Suponhamos o caso de:
- uma matriz esparsa que armazena inteiros
- um ponteiro que ocupa o mesmo espaço que um inteiro
Matriz Esparsa
Espaço ocupado por uma matriz esparsa de nl linhas, nl colunas e n valores
não-nulos:
- 5 * n espaços para ponteiros para os registros (um para cada campo do
registro: linha, coluna, valor, PL, PC)
- nl espaços para ponteiros para o vetor L
- nc espaços para ponteiros para o vetor C
- espaço total de 5n + nl + nc
Representação bidimensional
o espaço ocupado seria nl * nc
Conclusão:
Em termos de espaço ocupado, há vantagem em utilizar-se a representação de
listas cruzadas quando:
5n + nl + nc < nl * nc
ou seja, quando: n < [(nl - 1) * (nc - 1) -1] / 5
Como (nl - 1) * (nc - 1) é aproximadamente o tamanho da matriz, pode-se
dizer, de uma maneira geral que, há ganho em termos de espaço, quando um número
inferior a 1/5 dos elementos da matriz forem não nulos.
Fator Tempo
As operações sobre listas cruzadas podem ser mais lentas e complicadas que
para o caso bidimensional.
Portanto, para algumas aplicacões, deve ser feita
uma reavaliação de tempo-espaço.
Matriz Esparsa