MATRIZES ESPARSAS
A R M A Z E N A ME N T O D E M A T R I Z E S E S P A R S A S
PAULO CÉSAR BARBOSA FERNANDES – 2011/1
[email protected]
AGENDA
• Introdução
• Objetivo
• Tipos de armazenamento
• Índice
• Linha
• Coluna
• Comparação entre as abordagens
• Estudo de caso
• Conclusão
INTRODUÇÃO
•
Uma matriz é dita esparsa quando a maioria de seus
elementos são iguais a zero. Por exemplo:
•
Muito espaço em memória seria economizado se apenas os
elementos não nulos fossem armazenados.
INTRODUÇÃO
•
42 posições na matriz;
•
7 posições com valor diferente de zero;
•
Supondo 4 bytes para cada posição, temos:
 42 * 4 = 168 bytes
 7 * 4 = 28 bytes
 Uma economia de 83%
INTRODUÇÃO
• A elaboração de uma representação para matrizes
esparsas deve levar em consideração:
 Facilidade de acesso tanto para linhas como para colunas
(preservar a natureza bidimensional da matriz).
 Eficiência nas operações (soma, multiplicação, etc.)
OBJETIVO
• Diminuir a quantidade de memória necessária para
armazenar as informações;
 Armazenando valores zero: 48 posições ocupadas
10
0
2
3
5
0
2
0
6
0
5
0
0
2
5
6
0
2
6
0
1
0
3
0
0
2
0
0
0
5
0
8
1
0
2
0
0
3
0
0
5
0
5
0
6
0
7
0
3
2
5
 Não armazenando valores zero: 24 posições ocupadas
10
2
3
5
2
6
5
2
8
1
2
3
5
5
6
7
5
6
2
6
1
ARMAZENAMENTO POR ÍNDICE
STOREGE-BY-INDICES
𝟏𝟏 𝟎 𝟏𝟑 𝟎
𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟑𝟔
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎
𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟔𝟓
𝟎
𝟎
𝟎
𝟒𝟓
𝟎
𝟔𝟔
A
11
13
21
22
24
32
33
36
43
44
45
61
62
65
66
I
1
1
2
2
2
3
3
3
4
4
4
6
6
6
6
J
1
3
1
2
4
2
3
5
3
4
5
1
2
5
6
STOREGE-BY-INDICES
 Espaço necessário:
3 x Elementos não nulos
𝟏𝟏 𝟎 𝟏𝟑 𝟎
𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟑𝟔
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎
𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟔𝟓
Elementos matriz: 36
Elementos não nulos: 15
Para armazenamento: 45
𝟎
𝟎
𝟎
𝟒𝟓
𝟎
𝟔𝟔
A
11
13
21
22
24
32
33
36
43
44
45
61
62
65
66
I
1
1
2
2
2
3
3
3
4
4
4
6
6
6
6
J
1
3
1
2
4
2
3
5
3
4
5
1
2
5
6
ARMAZENAMENTO POR LINHA
STOREGE-BY-ROWS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Armazenando linha por linha
AR
IA
JA
11
13
21
22
24
32
33
43
44
46
61
62
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
66
STOREGE-BY-ROWS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Primeiro índice de cada linha
AR
11
13
21
22
24
32
33
IA
1
3
6
8
11
11
14
JA
43
44
46
61
62
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
66
STOREGE-BY-ROWS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Índice do elemento na coluna
AR
11
13
21
22
24
32
33
IA
1
3
6
8
11
11
14
JA
1
3
1
2
4
2
3
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
43
44
46
61
62
66
3
4
6
1
2
6
STOREGE-BY-ROWS
(4,3)
 Espaço necessário:
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
2 x Elementos não nulos + Nº Linhas + 1
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
Elementos matriz: 36
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
Elementos não nulos: 13
𝟎
𝟎
𝟎
𝟎 𝟎
Para armazenamento: 33
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
AR
11
13
21
22
24
32
33
IA
1
3
6
8
11
11
14
JA
1
3
1
2
4
2
3
43
44
46
61
62
66
3
4
6
1
2
6
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
ARMAZENAMENTO POR COLUNA
STOREGE-BY-COLUMNS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Armazenando coluna por coluna
AR
IA
JA
11
21
61
22
32
62
13
33
43
24
44
46
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
66
STOREGE-BY-COLUMNS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Preenchendo índice da linha
de cada elemento
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
AR
11
21
61
22
32
62
13
33
43
24
44
46
66
IA
1
2
6
2
3
6
1
3
4
2
4
4
6
JA
STOREGE-BY-COLUMNS
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
 Primeiro índice de cada coluna
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
AR
11
21
61
22
32
62
13
33
43
24
44
46
66
IA
1
2
6
2
3
6
1
3
4
2
4
4
6
JA
1
4
7
10
12
12
14
STOREGE-BY-COLUMNS
(4,3)
 Espaço necessário:
2 x Elementos não nulos + Nº Colunas + 1
Elementos matriz: 36
Elementos não nulos: 13
Para armazenamento: 33
𝟏𝟏 𝟎 𝟏𝟑 𝟎 𝟎
𝟐𝟏 𝟐𝟐 𝟎 𝟐𝟒 𝟎
𝟎 𝟑𝟐 𝟑𝟑 𝟎 𝟎
𝟎
𝟎 𝟒𝟑 𝟒𝟒 𝟎
𝟎
𝟎
𝟎
𝟎 𝟎
𝟔𝟏 𝟔𝟐 𝟎
𝟎 𝟎
AR
11
21
61
22
32
62
13
33
43
24
44
46
66
IA
1
2
6
2
3
6
1
3
4
2
4
4
6
JA
1
4
7
10
12
12
14
𝟎
𝟎
𝟎
𝟒𝟔
𝟎
𝟔𝟔
COMPARANDO
Tipo Armazenamento
Dimensão Matriz
Quantidade
Linhas Colunas
Posições
6
6
100
Percentual
Quantidadede
posições nulas posições não nulas
Linha
Qtd
Redução
36,00
50,00
18,00
200
20.000,00
50,00
10.000,00
20.101,00
-
0,50
20000
1000
20.000.000,00
50,00
10.000.000,00
20.020.001,00
-
0,10
20000
13000
260.000.000,00
50,00
130.000.000,00
260.020.001,00
-
0,01
43,00 - 19,44
Coluna
Qtd
Redução
43,00 - 19,44
Com 50 % de posições nulas
20.201,00
-
1,01
20.001.001,00
-
0,01
260.013.001,00
-
0,01
Indice
Qtd
Redução
54,00 - 50,00
30.000,00 - 50,00
30.000.000,00 - 50,00
390.000.000,00 - 50,00
COMPARANDO
Tipo Armazenamento
Dimensão Matriz
Quantidade
Linhas Colunas
Posições
6
6
100
Percentual
Quantidadede
posições nulas posições não nulas
Linha
Qtd
Redução
36,00
65,00
12,60
32,20
10,56
200
20.000,00
65,00
7.000,00
14.101,00
29,50
20000
1000
20.000.000,00
65,00
7.000.000,00
14.020.001,00
29,90
20000
13000
260.000.000,00
65,00
91.000.000,00
182.020.001,00
29,99
Coluna
Qtd
Com 65 % de posições nulas
Redução
32,20
10,56
14.201,00
29,00
14.001.001,00
29,99
182.013.001,00
29,99
Indice
Qtd
Redução
37,80
-
5,00
21.000,00
-
5,00
21.000.000,00
-
5,00
273.000.000,00
-
5,00
COMPARANDO
Dimensão Matriz
Linhas
Colunas
6
6
100
Quantidade
Posições
Percentual
Quantidadede
posições nulas posições não nulas
Linha
Qtd
Redução
36,00
70,00
10,80
28,60
20,56
200
20.000,00
70,00
6.000,00
12.101,00
39,50
20000
1000
20.000.000,00
70,00
6.000.000,00
12.020.001,00
39,90
20000
13000
260.000.000,00
70,00
78.000.000,00
156.020.001,00
39,99
Coluna
Qtd
Com 70 % de posições nulas
Redução
28,60
20,56
12.201,00
39,00
12.001.001,00
39,99
156.013.001,00
39,99
Indice
Qtd
Redução
32,40
10,00
18.000,00
10,00
18.000.000,00
10,00
234.000.000,00
10,00
ESTUDO DE CASO
• Um sistema de informação que possa auxiliar um
profissional médico na classificação da doença do
paciente;
 Como é feito essa classificação ?
• Através do CID (Classificação Internacional de
Doenças);
• A grande maioria dos diagnósticos médicos pode
ser encontrado e associado a um código;
• O código vale para qualquer país;
• O médico vendo o código já sabe qual é a doença;
EXEMPLO ATESTADO
O REGISTRO ELETRÔNICO
• O profissional faz o diagnóstico do paciente em seu
prontuário;
MODELO VETORIAL
Matriz esparsa
O CALCULO
• Cosseno(d1,q) = 0,71
• Cosseno(d2,q) = 0
• Cosseno(d3,q) = 0,63
O PROBLEMA...
• Mais de 30.000 diagnósticos;
• Mais de 20.000 palavras;
• Sendo mais de 13.000 CID;
 Uma matriz :
 20.000 X 13.000 = 260.000.000
 double (8 bytes)
 Necessário 1.983,64 MB
 Com redução de 40 % - 1.190,18 MB
70 % dos elementos nulos
DEMONSTRAÇÃO
Tipo Armazenamento
Dimensão Matriz
Linhas
Colunas
19909
845
Quantidade
Posições
16.823.105,00
Percentual
Quantidadede
posições nulas posições não nulas
85,00
2.523.465,75
Linha
Qtd
Redução
5.066.841,50
69,88
Coluna
Qtd
5.047.777,50
• 16.823.105 x 8 bytes = 128,35 MB
• 128,35 MB – 69,9 % = 38,63 MB
Redução
69,99
DEMONSTRAÇÃO
DEMONSTRAÇÃO
CONCLUSÃO
• Nem sempre é vantagem utilizar matrizes esparsas;
• Quando utilizado adequadamente o ganho pode ser muito
vantajoso;
• Devemos observar na nova forma de armazenamento, que:
 Diminuímos o espaço necessário para armazenar;
 Aumentamos o custo computacional;
OBRIGADO !!!
Paulo César Barbosa Fernandes – [email protected]
DÚVIDAS