Organização de Arquivos - Processamento Co-sequencial (Parte 1)

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Aula 14
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 1
Suma´rio
Processamento Co-sequencial
1 Descric¸a˜o de uma atividade de processamento, frequentemente utilizada, chamada
de processamento co-sequencial.
2 Apresentac¸a˜o de um modelo gene´rico para implementar todas as variac¸o˜es de
processamento co-sequencial.
3 Ilustrac¸a˜o do uso do modelo para resolver diferentes problemas de processamento
co-sequencial.
4 Apresentac¸a˜o do algoritmo “K-way merge” (intercalac¸a˜o mu´ltipla).
5 Apresentac¸a˜o do heapsort como uma abordagem para sorting em RAM.
6 Mostrar como merging (intercalac¸a˜o) fornece a base para ordenac¸a˜o de arquivos
grandes.
2 / 1
Processamento Co-sequencial
Objetivo
Processamento coordenado de duas ou mais listas sequenciais para produzir uma
u´nica lista como sa´ıda.
Motivac¸a˜o
Como foi visto ao estudar indexac¸a˜o, podemos ter listas ordenadas de diferentes
chaves, logo o processamento co-sequencial pode ser necessa´rio ao querer combinar
as informac¸o˜es obtidas de va´rias litas.
Listas de Entrada
Ordenadas por chave.
Na˜o possuem itens (registros) duplicados por chave.
“Processadas paralelamente”.
Lista de Sa´ıda
Ordenada por chave.
Sem registros duplicados por chave.
3 / 1
Processamento Co-sequencial
Tipos de Listas Resultantes
Intersec¸a˜o (Matching) dos itens das listas:
A lista de sa´ıda e´ formada so´ por itens que ocorrem em todas as listas de entrada.
Unia˜o/Intercalac¸a˜o (Merge) dos itens das listas:
A lista de sa´ıda e´ formada por todos os itens das listas de entrada, sem duplicac¸a˜o de
chave.
Os itens sa˜o intercalados por ordem de chave.
4 / 1
Matching
Suponha que desejamos obter as chaves que
aparecem um duas listas. Podemos utilizar o
seguinte algoritmo:
1 Se a chave da lista 1 e´ menor que a
chave da lista 2, lemos a seguinte chave
da lista 1.
2 Se a chave da lista 1 e´ maior que chave
da lista 2, lemos a seguinte chave da
lista 2.
3 Se as chaves sa˜o iguais, colocamos na
lista de sa´ıda e lemos a chave seguinte
de ambas listas de entrada.
4 Repetimos os passos 1 a 3 ate´ chegar
no final de uma das listas.
5 / 1
Intersec¸a˜o
Intersec¸a˜o
O algoritmo e´ simples, pore´m devemos tomar cuidado com:
Iniciac¸a˜o
Abertura dos arquivos.
Definic¸o˜es de varia´veis auxiliares
Sincronizac¸a˜o dos arquivos.
Condic¸o˜es de parada.
Reconhecimento de erro para cada arquivo de entrada:
Registros duplicados por chave.
Registros na˜o ordenados por chave.
6 / 1
Intersec¸a˜o
Algoritmo 1 Intersec¸a˜o
1: Iniciar(chave1 ant, chave2 ant)
2: reg1← Input(arq1, chave1 ant)
3: reg2← Input(arq2, chave2 ant)
4: while existe registro do
5: if reg1.chave < reg2.chave then
6: reg1← Input(arq1, chave1 ant) { Leˆ pro´ximo item da lista 1 }
7: else if reg1.chave > reg2.chave then
8: reg2← Input(arq2, chave2 ant) { Leˆ pro´ximo item da lista 2 }
9: else
10: escreve(reg1, arq sa´ıda) { Grava o elemento comum a`s listas }
11: reg1← Input(arq1, chave1 ant)
12: reg2← Input(arq2, chave2 ant)
13: end if
14: end while
7 / 1
Intersec¸a˜o
Algoritmo 2 Input(arq, var chave ant)
1: reg ← read(arq)
2: if EOF (arq) then
3: existe registro← false
4: else if reg.chave ≤ chave ant then
5: escreva(arquivo fora de ordem) { na˜o ordenado: erro! }
6: pare!
7: end if
8: chave ant← reg.chave
9: return reg
Observac¸a˜o
O paraˆmetro chave ant esta´ sendo passado por refereˆncia.
8 / 1
Intersec¸a˜o
Algoritmo 3 Iniciar( var chave1 ant, var chave2 ant)
1: chave1 ant← valor mı´nimo
2: chave2 ant← valor mı´nimo
3: abra(arq1)
4: abra(arq2)
5: crie(arqSa´ıda)
6: existe registro← true
Observac¸a˜o
valor mı´nimo e´ uma constante. E´ o menor valor que a chave pode assumir. O uso
dessa constante permite:
9 / 1
Intersec¸a˜o
Observac¸a˜o
O uso da constante valor mı´nimo permite:
Executar Input sem cair na condic¸a˜o de erro:
else if reg.chave ≤ chave ant
Onde:
chave ant e´ paraˆmetro formal.
As varia´veis (chave1 ant ou chave2 ant) sa˜o iniciadas com valor mı´nimo.
10 / 1
Unia˜o/Intercalac¸a˜o
11 / 1
Unia˜o/Intercalac¸a˜o
Algoritmo 4 Intercalac¸a˜o
1: Iniciar(chave1 ant, chave2 ant)
2: reg1← Input(arq1,mı´nimo, chave1 ant)
3: reg2← Input(arq2, reg1.chave, chave2 ant)
4: while existe registro do {Termina execuc¸a˜o quando chegar ao fim das duas listas}
5: if reg1.chave < reg2.chave then
6: escreve(reg1, arq sa´ıda) { Grava item da lista 1 na lista de sa´ıda }
7: reg1← Input(arq1, reg2.chave, chave1 ant) { Leˆ o pro´ximo item da lista 1 }
8: else if reg1.chave > reg2.chave then
9: escreve(reg2, arq sa´ıda) { Grava item da lista 2 na lista de sa´ıda }
10: reg2← Input(arq2, reg1.chave, chave2 ant) { Leˆ o pro´ximo item da lista 2 }
11: else
12: escreve(reg1, arq sa´ıda) { Itens iguais. Grava na lista de sa´ıda }
13: reg1← Input(arq1, reg2.chave, chave1 ant){ Leˆ o pro´ximo item da lista 1 }
14: reg2← Input(arq2, reg1.chave, chave2 ant){ Leˆ o pro´ximo item da lista 2 }
15: end if
16: end while
12 / 1
Unia˜o/Intercalac¸a˜o
Algoritmo 5 Input(arq, chave outra lista, varchave ant)
1: reg ← read(arq)
2: if EOF(arq) then
3: reg.chave← valor ma´ximo
4: if chave outra lista = valor ma´ximo then
5: existe registro← false
6: end if
7: else if reg.chave ≤ chave ant then
8: escreva(arquivo fora de ordem) { na˜o ordenado: erro! }
9: pare!
10: end if
11: chave ant← reg.chave
12: return reg
Observac¸a˜o
chave ant e´ passado por refereˆncia.
Garante que o conteu´do restante da outra lista, sera´ jogado na lista de sa´ıda.
Quando terminar uma lista apenas, existe registro ainda sera´ true.
13 / 1
Unia˜o/Intercalac¸a˜o
Algoritmo 6 Iniciar(varchave1 ant, varchave2 ant)
1: chave1 ant← valor mı´nimo
2: chave2 ant← valor mı´nimo
3: abra(arq1)
4: abra(arq2)
5: crie(arqSa´ıda)
6: existe registro← true
14 / 1
Unia˜o/Intercalac¸a˜o
Valores Constantes
valor mı´nimo:e´ o menor valor que o campo de chave poderia assumir.
valor ma´ximo:e´ o maior valor que o campo de chave poderia assumir.
valor mı´nimo e valor ma´ximo: na˜o ocorrem como valor de chave de nenhum dos
registros dos arquivos de entrada.
15 / 1
Unia˜o/Intercalac¸a˜o
valor ma´ximo
O uso de tal constante permite:
Que seja atribu´ıdo o valor ma´ximo a regx.chave do arquivo x que acabou.
Que o algoritmo intercalac¸a˜o leia e transfira os demais registros do arquivo arqy que
na˜o acabou para o arquivo de sa´ıda, x 6= y.
O valor ma´ximo tambe´m e´ utilizado para verificar se uma das lista acabou. Notar que
pode ser utilizada uma outra varia´vel que:
E´ iniciada com false.
Recebe true quando um dos arquivos chega ao fim.
Na func¸a˜o Input em lugar de verificar o valor da chave do outro arquivo seria
necessa´rio verificar so´ se esta nova varia´vel e´ igual a true.
16 / 1
Unia˜o/Intercalac¸a˜o
existe registro
A varia´vel existe registro:
E´ iniciada com true.
Recebe false quando os dois arquivos chegam ao fim.
Encerra o loop (while existe registro...).
Termina a intercalac¸a˜o
17 / 1
Exemplo
Livro Raza˜o
Livro-Raza˜o: um livro contendo contas a`s quais de´bitos e cre´ditos sa˜o lanc¸ados a partir
de livros originais.
Problema
Desenvolver um programa para o livro-raza˜o (atualizac¸a˜o + listagem), como parte de um
sistema de contabilidade.
18 / 1
Exemplo
Arquivos Envolvidos
Dois arquivos esta˜o envolvidos neste processo:
Arquivo Mestre: arquivo do livro-raza˜o.
Traz o resumo mensal do balanc¸o de cada uma das contas.
Arquivo de Transac¸a˜o: arquivo do dia´rio.
Conte´m as transac¸o˜es mensais que sa˜o colocadas no livro-raza˜o.
Uma vez que o arquivo dia´rio esta´ completopara um determinado meˆs, ele deve ser
lanc¸ado no livro-raza˜o.
Esse lanc¸amento envolve associar cada transac¸a˜o a` sua conta no livro-raza˜o.
19 / 1
Exemplo
Amostra do Livro Raza˜o
20 / 1
Exemplo
Exemplo de Lanc¸amentos no Dia´rio
21 / 1
Exemplo
Exemplo
Exemplo da listagem do livro-raza˜o (o que deve ser apresentado ao usua´rio como resumo
do meˆs):
22 / 1
Exemplo
Implementac¸a˜o
Como implementar o processo de lanc¸amento no livro-raza˜o?
Usar o nu´mero da conta como uma chave para relacionar as transac¸o˜es do dia´rio aos
registros do livro-raza˜o.
Ordenar o arquivo dia´rio pela chave (nro da conta)
Processar o livro-raza˜o e o dia´rio co-sequencialmente (processamos as duas listas
sequencialmente em paralelo).
23 / 1
Exemplo
Tarefas
Tarefas a serem realizadas:
Atualizar o arquivo livro-raza˜o com o saldo correto para cada conta do meˆs corrente.
Produzir uma listagem como no exemplo (lista as contas com seu saldo atual, e
tambe´m as respectivas transac¸o˜es do dia´rio daquele meˆs).
Do ponto de vista das contas do livro-raza˜o:
Merging (ate´ mesmo as contas que na˜o “match” va˜o para a listagem).
Do ponto de vista das contas do dia´rio:
Matching (contas que na˜o “match” constituem um erro).
O me´todo de lanc¸amento e´ uma combinac¸a˜o de merging e matching.
24 / 1
Exemplo
O Algoritmo
item(1) = sempre armazena o reg corrente do arquivo mestre.
item(2) = sempre armazena o reg corrente do arquivo dia´rio.
1: Leia o primeiro registro do arq mestre
2: Imprima a linha t´ıtulo para a primeira conta
3: Leia o primeiro registro do arquivo transac¸o˜es
4: while existirem reg no mestre OU reg no transac¸o˜es do
5: if item(1) < item(2) then
6: Encerre este registro do mestre
7: Imprima o balanc¸o da conta, atualiza o reg mestre
8: Leia o pro´ximo registro do arq mestre
9: Se leitura com sucesso, enta˜o imprima a linha t´ıtulo para a nova conta
10: else if item(1) = item(2) then {Transac¸a˜o “match” o mestre}
11: Adiciona o valor da transac¸a˜o no balanc¸o da conta para o novo meˆs
12: Imprima a descric¸a˜o da transac¸a˜o
13: Leia o pro´ximo reg de transac¸a˜o
14: else {Transac¸a˜o sem registro no mestre}
15: Imprima uma mensagem de erro
16: Leia o pro´ximo reg de transac¸a˜o
17: end if
18: end while
25 / 1
Pro´xima Aula
Pro´xima aula
Processamento Co-sequencial e Ordenac¸a˜o (continuac¸a˜o)
26 / 1