Organização de Arquivos - Organizando Arquivos para Desempenho (Parte 3)

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Aula 11
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 27
Suma´rio
Organizand Arquivos para Desempenho
1 Conceitos em Teoria da Informac¸a˜o
2 Compressa˜o de dados
3 Recuperando espac¸o em disco
4 Uma introduc¸a˜o a ordenac¸a˜o interna e busca bina´ria
5 Ordenac¸a˜o de chaves (Keysorting ou Tag Sort)
6 Ordenac¸a˜o de arquivos grandes
2 / 27
Encontrando as Coisas Mais Rapidamente
Relembrando
No in´ıcio falamos do custo de acesso a` memo´ria secunda´ria × custo de acesso a
memo´ria RAM.
No entanto, ate´ agora na˜o prestamos muita atenc¸a˜o neste custo!
3 / 27
Encontrando as Coisas Mais rapidamente
Vamos Mudar o Foco!
Organização
Fundamental
Busca de um pedaço 
específico de informação 
num determinado 
arquivo.
O custo de seek passa
a ser um fator determinante!
De:
Para:
4 / 27
Encontrando as Coisas Mais Rapidamente
Sorting and Searching
Um algoritmo de ordenac¸a˜o normalmente envolve fazer muitas comparac¸o˜es.
Cada uma dessas comparac¸o˜es, no caso de memo´ria secundaria, envolve um seek.
Sorting and searching: Desenvolveremos abordagens para minimizar o nu´mero de
acessos a disco e portanto, minimizar o tempo gasto. Dados ordenados permitem
uma busca mais ra´pida. Objetivo: Minimizar o nu´mero de seeks
5 / 27
Busca por PRR e Chave
Problema
Ate´ o momento vimos que a recuperac¸a˜o de dados mais ra´pida e´ o acesso direto,
que e´ poss´ıvel via a PRR.
A PRR apenas indica o byte inicial de um registro mas na˜o da´ nenhuma informac¸a˜o
sobre o conteu´do do registro.
E se no´s na˜o conhecemos a PRR do registro que estamos buscando?
Soluc¸a˜o
Busca atrave´s de uma chave!
6 / 27
Busca por PRR e Chave
Busca por Chave
E se nenhum registro conte´m a chave buscada? No pior caso, temos que olhar
cada registro no arquivo.
E se existir mais de um registro contendo a chave buscada, e no´s queremos
encontrar todos eles? No pior caso, temos que olhar cada registro no arquivo
Isto sugere que para buscar por chave precisamos fazer busca sequencial.
E se os Dados Estiverem Ordenados?
Busca Bina´ria!
7 / 27
Relembrando a Busca Bina´ria
Observac¸a˜o
Note que em ambos os casos a pesquisa sequeˆncial levaria a muito mais comparac¸o˜es, no
primeiro caso 13 comparac¸o˜es ate´ se chegar no 24, e no segundo 5 ate´ se chegar no 8.
8 / 27
Busca Bina´ria
Algoritmo 1 Busca Bina´ria
Input: arq, n, chaveB
Output: Ocorreˆncia de chaveB no Arquivo, caso exista
1: inicio← 0
2: fim← 0
3: while inicio ≤ fim do
4: meio← ⌊ inicio+fim
2
⌋
5: Posiciona(arq,meio)
6: Leia(arq,meio)
7: if chaveB < reg.chave then
8: fim← meio− 1
9: else if chaveB > reg.chave then
10: inicio← meio+ 1
11: else
12: return meio
13: end if
14: end while
15: return NotFound
9 / 27
Busca Bina´ria
Complexidade da Busca Bina´ria
A cada paso do lac¸o da busca bina´ria a quantidade de dados reduz pela metade.
Pergunta: Dado um nu´mero n de dados, quantas comparac¸o˜es no ma´ximo preciso
para achar um determinado valor utilizando a busca bina´ria?
Dado um inteiro n, quantas vezes preciso dividir ele pela metade ate´ chegar ou ficar
abaixo de 1.
Ou seja n
2k
≤ 1, o que significa que k > log2 n.
Logo, no pior caso, ma busca bina´ria sera˜o feitas:
blog2 nc+ 1 = O(log2 n)
comparac¸o˜es.
10 / 27
Busca Bina´ria
Busca Bina´ria Vs Busca Sequencial
O arquivo deve estar ordenado para executarmos a busca bina´ria.
Complexidade:
Suponha um Arquivo de n registros.
Busca Bina´ria = O(log2 n)
Busca Sequencial = O(n)
Isto e´, se o arquivo dobra de tamanho:
a busca sequencial dobra!
a busca bina´ria aumenta de um (assumindo que o arquivo esteja ordenado)!
se n = 1000, blog2 1000c = 9.
se n = 2000, blog2 1000c = 10.
11 / 27
Problemas da Busca Bina´ria
Problema 1
Os acessos ao arquivo ocorrem em registros diferentes do arquivo.
Requer movimentac¸a˜o constante do cabec¸ote (seek).
Em um arquivo com 100.000 registros tem no ma´ximo 17 acessos.
Com o PRR se faz um u´nico acesso.
Poss´ıvel Soluc¸a˜o
conjugar o acesso por chave e PRR: isto pode ser feito usando um arquivo de ı´ndice
(´ındice e´ um ponteiro para um registro, e portanto diferente de chave).
12 / 27
Problemas da Busca Bina´ria
Problema 2
Manter um arquivo ordenado e´ caro.
A cada adic¸a˜o de registro:
Deve-se pesquisar a sua posic¸a˜o e depois deslocar todos os registros posteriores de
uma posic¸a˜o.
Se as adic¸o˜es sa˜o pouco frequ¨entes, enta˜o pode-se fazer atualizac¸o˜es em lote.
Poss´ıveis Soluc¸o˜es
Na˜o reordenar todo o arquivo quando novos registros forem inclu´ıdos (utilizando
ı´ndices).
Usar estruturas de dados que permitam reordenac¸a˜o mais ra´pida e eficiente do
arquivo (uso de estruturas como a´rvore-B).
13 / 27
Problemas da Busca Bina´ria
Problema 3
Sort em memo´ria (“Internal Sorting”) so´ e´ via´vel para arquivos pequenos.
Se o arquivo for grande e´ melhor usar um sort externo (i.e. em disco).
Poss´ıvel Soluc¸a˜o
Usar outras te´cnicas de ordenac¸a˜o (Keysorting!).
Keysorting
Keysorting (ou Tag Sort) e´ uma variac¸a˜o do “Internal Sorting”.
O tamanho do arquivo que o Keysorting pode ordenar e´ limitado, mas seu limite e´
maior que o “Internal Sorting”.
14 / 27
Busca Bina´ria: Resumo
Vantagens
Muito mais ra´pida que a busca sequencial!
Desvantagens
O arquivo deve estar ordenado pela chave.
Incluir dados em arquivo, mantendo a ordenac¸a˜o da chave e´ caro.
15 / 27
Keysorting
Keysorting
Utiliza-se para ordenar um arquivo que e´ muito grande para caber na memo´ria RAM.
Para ordenar um arquivo, precisamos apenas das chaves!!!
Me´todo:
1 Abra o arquivo leia e coloque num vetor de tags somente a chave e a PRR de cada
registro (se o registro tem tamanho fixo enta˜o podemos utilizar NRR em lugar da
PRR).
2 Na˜o e´ necessario manter em memo´ria todos os registros inteiros.
3 Ordene o vetor em memo´ria (“Internal Sorting”).
4 Reescrever os arquivo segundo a ordem dada pelo vetor ordenado.
16 / 27
Keysorting
1
2
Main Memory
Internal Sorting
in main memory
keynodes array
keynodes array
records
Disk
records
No change in Disk
17 / 27
Keysorting
3
Internal Sorting
in main memory
keynodes array
records
Create new sorted file
to replace previous
18 / 27
Keysorting
Problemas
Ler registros na ordem do vetor implica tempo alto
Sa˜o lidas porc¸o˜es dispersas em disco, gerando tempos elevados de seek, lateˆncia e
transfereˆncia.
Soluc¸a˜o
Usar o vetor de chaves para criar um arquivo de ı´ndices e NA˜O mover os registros.
index file records
Leave file unchanged
19 / 27
Keysorting
Keysorting
Ao inve´s de regravar o arquivo, conforme mapeado pelo vetor de tags, grave apenas
o vetor de tags!
Use esse arquivo como um arquivo ı´ndice.
Use pesquisa bina´ria nele, talvez na memo´ria.
use PRR associado a chave encontrada para acesso.
O arquivo passa a ser acess´ıvel pela chave com um u´nico acesso, via PRR.
Inclusa˜o de registros no arquivo ba´sico.
Reuse o espac¸o de registros eliminados logicamente.
Inclua o registro no final do arquivo.
Observac¸a˜o
Se algumas partes do processo comec¸am a se tornar um gargalo (bottleneck), considere
“pular” tudo. Pense: “posso fazer sem isso”?
20 / 27
Ordenac¸a˜o: Registros Eliminados
Ordenac¸a˜o: Registros Eliminados
Registros com:
Campo para indicar status de va´lido ou eliminado.
Ponteiro para outros registros eliminados.
Ordenar arquivos com registros eliminados e´ problema´tico ou mesmo imposs´ıvel:
Registro eliminado na˜o pode ser mudado de lugar.
Ele e´ apontado por outro registrodeste arquivo ou de outros arquivos (´ındices).
A ide´ia e´ manter o arquivo com atualizac¸o˜es fazendo reuso dos registros eliminados:
O acesso por chave pode ser feito via arquivo ı´ndice.
Tais arquivos ı´ndices devem ser atualizados a cada inclusa˜o de novos registros no
arquivo ba´sico.
Discutiremos isso no Cap´ıtulo 6!
21 / 27
Pro´xima Aula
Pro´xima Aula
Indexac¸a˜o.
22 / 27
Co´digos
Co´digos
Os co´digos foram retirados de File Structures: An Object-Oriented Approach with C ++, 3rd Edition e
apresentam a descric¸a˜o das principais classes.
Para a versa˜o escrita em C, consulte File Structures, 2nd Edition.
buscaBinaria.cpp: Descreve o algoritmo gene´rico de busca bina´ria.
keyType.cpp: Descric¸a˜o da classe, me´todos e operadores que devem ser implementados para suportar
uma busca bina´ria gene´rica]
fixedRecordFile.cpp: Descric¸a˜o da classe que trabalha com registros fixos e os me´todos necessa´rios para
implementar o algoritmo keysort de maneira adequada.
keysort.cpp: Algoritmo Keysort.
23 / 27
Co´digos
1 //A b i n a r y s e a r c h a l g o r i t hm
2
3 i n t B i n a r y S e a r c h ( F i x e d R e c o r d F i l e & f i l e , RecType & obj , KeyType & key
4 // b i n a r y s e a r c h f o r key
5 // i f key found , ob j c o n t a i n s c o r r e s p ond i n g reco rd , 1 r e t u r n e d
6 // i f key not found , 0 r e t u r n e d
7 {
8 i n t low =0; i n t h i g h = f i l e . NumRecs ()−1;
9 w h i l e ( low<=h i g h ){
10 i n t g u e s s = ( h i g h − low ) / 2 ;
11 f i l e . ReadByRRN ( obj , g u e s s ) ;
12 i f ( o b j . Key()==key ) r e t u r n 1 ; // r e c o r d found
13 i f ( o b j . Key ( ) < key ) h i g h = g u e s s −1; // s e a r c h b e f o r e gue s s
14 e l s e low = g u e s s +1; // s e a r c h a f t e r gue s s
15 }
16 r e t u r n 0 ; // loop ended w i thout f i n d i n g key
17 }
Co´digo 1: buscaBinaria.cpp
24 / 27
Co´digos
1 // C l a s s e s and methods tha t must be implemented to suppo r t the
2 // b i n a r y s e a r c h a l g o r i t hm
3
4 c l a s s KeyType
5 {
6 p u b l i c :
7 i n t o p e r a t o r == ( KeyType &); // e q u a l i t y o p e r a t o r
8 i n t o p e r a t o r < ( KeyType &); // l e s s than op e r a t o r
9 } ;
10
11 c l a s s RecType{ p u b l i c : KeyType Key ( ) ; } ;
12
13 c l a s s F i x e d R e c o r d F i l e
14 {
15 p u b l i c :
16 i n t NumRecs ( ) ;
17 i n t ReadByRRN ( RecType & r e c o r d , i n t RRN ) ;
18 } ;
Co´digo 2: keyType.cpp
25 / 27
Co´digos
1 //min imal f u n c t i o n a l i t y r e q u i r e d f o r c l a s s e s used by the k e y s o r t a l g o r i t hm
2
3 c l a s s F i x e d R e c o r d F i l e
4 {
5 p u b l i c :
6 i n t NumRecs ( ) ;
7 i n t ReadByRRN ( RecType & r e c o r d , i n t RRN ) ;
8 // a d d i t i o n a l methods r e q u i r e d f o r k e y s o r t
9 i n t C r e a t e ( char∗ f i l e N a m e ) ;
10 i n t Append ( RecType & r e c o r d ) ;
11 } ;
12
13 c l a s s KeyRRN
14 // c o n t a i n s a p a i r (KEY, RRN)
15 {
16 p u b l i c :
17 KeyType KEY ; i n t RRN;
18 KeyRRN ( ) ;
19 KeyRRN ( KeyType key , i n t r r n ) ;
20 } ;
21
22 i n t S o r t (KeyRRN [ ] , i n t numKeys ) . // s o r t a r r a y by key
Co´digo 3: fixedRecordFile.cpp
26 / 27
Co´digos
1 // A lgo r i thm f o r Keyso r t
2
3 i n t K e y S i r t ( F i x e d R e c o r d F i l e & i n F i l e , char∗ outFi leName )
4 {
5 RecType o b j ;
6 KeyRRN∗ KEYNODES = new KeyRRN [ i n F i l e . NumRecs ( ) ] ;
7 // read f i l e and l oad Keys
8 f o r ( i n t i =0; i< i n F i l e . NumRecs ( ) ; i ++){
9 i n F i l e . ReadByRRN ( obj , i ) ; // read r e c o r d u
10 KEYNODES[ i ] = KeyRRN( o b j . key ( ) , i ) ; // put key and RRN i n t o Keys
11 }
12 S o r t (KEYNODES, i n F i l e . NumRecs ( ) ) ; // s o r t Keys
13 F i x e d R e c o r d F i l e o u t F i l e ; // f i l e to ho ld r e c o r d s i n key o r d e r
14 o u t F i l e . C r e a t e ( outFi leName ) ; // c r e a t e a new f i l e
15 // w r i t e a new f i l e i n key o r d e r
16 f o r ( i n t j =0; j< i n F i l e . NumRecs ( ) ; j ++){
17 i n F i l e . ReadByRRN ( obj ,KEYNODES[ j ] . RRN ) ; // read i n key o r d e r
18 o u t f i l e . Append ( o b j ) ; // w r i t e i n key o r d e r
19 }
20 r e t u r n 1 ;
21 }
Co´digo 4: keysort.cpp
27 / 27