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

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Aula 16
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 40
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 / 40
Ordenando Arquivos Grandes
Desvantagem
Depois de ordenar a chaves, existe um custo substancial de seeking para ler e
reescrever cada registro no arquivo novo.
O tamanho do arquivo e´ limitado pelo nu´mero de pares chave/ponteiro que pode ser
armazenado na RAM. Invia´vel para arquivo realmente grandes.
3 / 40
Ordenando Arquivos Grandes
Exemplo
Caracter´ısticas do arquivo a ser ordenado:
8.000.000 de registros.
Tamanho do registro: 100 bytes.
Tamanho da chave: 10 bytes.
Memo´ria dispon´ıvel para o trabalho: 10 MB (Sem contar memo´ria para manter o
programa, SO, buffer de I/O, etc.)
Tamanho total do arquivo: 800 MB.
Nu´mero total de bytes para todas as chaves: 80 MB.
Na˜o e´ possivel fazer Internal Sorting nem Keysorting!
Observac¸a˜o
Para facilitar as contas estamos utilizando o padra˜o do Sistema Internacional de
Unidades, onde 1 MB = 1000 KB = 1000000Bytes. (Sendo que o normal em sistemas de
computac¸a˜o e´ utilizar o padra˜o potencia de 2).
4 / 40
Ordenando Arquivos Grandes
Soluc¸a˜o
Soluc¸a˜o ⇒ Mergesort.
Criar sub-arquivos chamados “runs”:
Trazer o ma´ximo de registros poss´ıveis para a memo´ria.
Fazer o Internal Sorting e salvar num arquivo menor.
Repetir este processo ate´ que todos os registros do arquivo original tenham sido lidos.
Fazer o Multi-way Merge (Intercalac¸a˜o Mu´ltipla) dos arquivos ordenados.
5 / 40
Ordenando Arquivos Grandes
Exemplo
No exemplo em questa˜o, qual seria o tamanho de cada run?
Memo´ria dispon´ıvel = 10 MB = 10.000.000 bytes
Tamanho do registro = 100 bytes
Nu´mero de registros que cabem na memo´ria dispon´ıvel = 100.000 registros.
Se o nu´mero total de registros e´ 8.000.000, o nu´mero total de runs e´ = 80 runs.
6 / 40
Ordenando Arquivos Grandes
7 / 40
Ordenando Arquivos Grandes
Ordenando Arquivos Grandes
A soluc¸a˜o “criar runs” + “intercalac¸a˜o mu´ltipla” tem as seguintes caracter´ısticas:
Pode-se, de fato, ordenar arquivos grandes, e e´ extens´ıvel para arquivos de qualquer
tamanho. Leitura do arquivo input durante o passo de criac¸a˜o do run e´ sequencial.
A leitura do run durante o processo de merge e escrita dos reg ordenados tambe´m e´
sequencial.
Acesso randoˆmico e´ necessa´rio somente quando alternamos de um run para outro
durante o merge.
8 / 40
Ordenando Arquivos Grandes
Operac¸o˜es de I/O
Operac¸o˜es de I/O sa˜o realizadas 4 vezes:
Durante a fase do Sort:
1) Leitura de cada registro na memo´ria para ordenar e criar os runs.
2) Escrita dos runs ordenados no disco.
Durante a fase do Merge:
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
3) Escrita do arquivo ordenado no disco.
9 / 40
Ordenando Arquivos Grandes
1) Leitura de cada registro na memo´ria para ordenar e criar os runs.
2) Escrita dos runs ordenados no disco.
Os passos 1 e 2 sa˜o feitos da seguinte forma:
Leˆ blocos de 10MB e escreve blocos de 10MB.
Repete isto 80 vezes.
Em termos de operac¸o˜es ba´sicas em disco:
Para leitura: 80 seeks + tempo de transfereˆncia p/ 800MB
Para escrita: idem
10 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
3) Leitura dos runs ordenados na memo´ria para realizar o merge.
8.000.000 reg
ordenados
1° run = 80 blocos (80 acessos)
2° run = 80 blocos (80 acessos)
80° run = 80 blocos (80 acessos)
11 / 40
Ordenando Arquivos Grandes
Passo 3
O passo 3 e´ feito da seguinte forma:
Para minimizar o nu´mero de seeks, leia um bloco de cada run, ou seja, 80 blocos.
Uma vez que a memo´ria dispon´ıvel e´ 10MB cada bloco pode ter
10.000.000 bytes
80 blocos
= 125.000 bytes = 1.250 reg.
Quantos blocos sera˜o lidos para cada run?
Tamanho do run/tamanho do bloco = 10.000.000
125.000
= 80
Nu´mero total de seeks = nu´mero total de blocos.
Nu´mero total de blocos = nro runs × nro blocos por run.
80 runs × 80 blocos / run = 802 blocos = 6.400 seeks .
12 / 40
Ordenando Arquivos Grandes
4) Escrita do arquivo ordenado no disco.
Passo 4
Para escrever o arquivo ordenado no disco, o nu´mero de seeks depende do tamanho
do buffer de sa´ıda (output buffer): Bytes no arquivo / bytes no buffer de sa´ıda.
Observac¸a˜o
O passo 3 domina o tempo de execuc¸a˜o, ou seja, e´ o gargalo deste me´todo.
13 / 40
Ordenando Arquivos Grandes
Maneiras de reduzir o tempo do passo 3 (gargalo)
1) Alocar mais hardware
2) Realizar o merge em mais de um passo (reduz a ordem do merge e aumenta o
tamanho dos runs).
3) Aumentar algoritimicamente o tamanho de cada run.
4) Encontrar maneiras de sobrepor operac¸o˜es de I/O.
14 / 40
Ordenando Arquivos Grandes
1) Alocar mais Hardware
Aumentar a quantidade de memo´ria RAM:
Uma memo´ria maior significa menos e maiores runs na fase do sort, e menos seek
por run durante a fase do merge.
Aumentar o nu´mero de discos:
Se tive´ssemos dois discos dedicados para o merge, poder´ıamos designar um para
input e outro para output, portanto leitura e escrita poderia se sobrepor sempre que
ocorressem simultaneamente.
Aumentar o nu´mero de canais de I/O:
Se existir um canal de I/O para cada disco, I/O pode-se sobrepor completamente.
15 / 40
Ordenando Arquivos Grandes
2) Realizar o merge em mais de um passo
Uma das maneiras de reduzir seeking e´ reduzir o nu´mero de runs que no´s temos que
fazer o merge, portanto, dandopara cada run uma parcela maior do espac¸o
dispon´ıvel do buffer.
Multiple-step Merging: quebramos o conjunto original de runs em grupos menores
e fizemos o merge dos runs nestes grupos, separadamente.
Em cada um destes merges menores, mais espac¸o do buffer fica dispon´ıvel para
cada run, portanto menos seeks sa˜o necessa´rio por run.
16 / 40
Ordenando Arquivos Grandes
Figura: 5 conjuntos de 16 runs cada um ( = 80 runs)
17 / 40
Ordenando Arquivos Grandes
Multiple-step Merging
Temos menos seeks na primeira passada, mas ainda ha´ uma segunda passada.
Existe vantagem em ler cada registro duas vezes?
80-way merge original: 6.400 seeks.
Multiple-step merging:
Primeira passada:
nro total de seeks = nro total de blocos,
16 runs x 16 blocos/run = 162 blocos = 256 seeks.
5 conjuntos × 256 = 1280 seeks.
Segunda passada:
temos 5 runs finais, enta˜o 15 do espac¸o do buffer e´ alocado para cada run (Cabem 100.000
reg por vez na RAM, logo os blocos devem ser de 20.000 reg cada)
Cada run tem 8.000.0005 = 1.600.000 reg.
Para ler cada run precisamos 80 blocos. Portanto, na segunda passada temos 80 seeks × 5
= 400 seeks.
Total: 1280 + 400 = 1680 seeks.
18 / 40
Ordenando Arquivos Grandes
Multiple-step Merging
Encontramos uma maneira de aumentar o espac¸o dispon´ıvel no buffer para cada run.
Trocamos passadas extras sobre os dados por uma diminuic¸a˜o significativa no acesso
randoˆmico.
Se fizermos um merge em 3 passos, podemos obter resultados ainda melhores?
Talvez na˜o, pois temos que considerar o tempo de transmissa˜o dos dados. No
merge original, os dados eram transmitidos apenas 2 vezes, no merge com 2
passos, sa˜o 4 vezes.
19 / 40
Ordenando Arquivos Grandes
3) Aumentar Algoritimicamente o Tamanho de Cada Run
Se pudermos, de alguma maneira, aumentar o tamanho dos runs iniciais:
Diminu´ımos o trabalho necessa´rio durante a passo do merge, durante o processo de
ordenac¸a˜o:
Runs iniciais maiores, significam menos runs no total, e um merge de baixa ordem.
Consequentemente, buffers maiores, e menos seeks.
Sem a possibilidade de comprarmos o dobro de memo´ria, como podemos criar runs
iniciais que sejam duas vezes maiores do que o nu´mero de registros que no´s
podemos armazenar na RAM?
Replacement Selection
20 / 40
Ordenando Arquivos Grandes
Algoritmo 1 Replacement Selection
1: Leia uma colec¸a˜o de registros e ordene-os usando o heapsort. Isto cria uma heap de
valores ordenados. Chame esta heap de heap prima´ria.
2: while Existir registros na heap prima´ria do
3: Ao inve´s de escrever (output) toda a heap prima´ria ordenada (como fazemos num
heapsort normal), escreva (output) somente o registro cuja chave tem o menor valor.
4: Traga um novo valor e compare sua chave com aquela que acabara de ser escrita
5: if Se a nova chave tem uma valor maior then
6: insira o novo registro no local apropriado dentro da heap prima´ria juntamente
com os outros registros que esta˜o sendo selecionados para output.
7: else
8: Se a nova chave tem um valor menor, coloque aquele registro numa heap se-
cunda´ria de registros cujas chaves tem valores menores do que aquela chave que
ja´ foi escrita (output).
9: end if
10: if Se a heap prima´ria estiver vazia then
11: fac¸a a heap secunda´ria ser a heap prima´ria.
12: end if
13: end while
21 / 40
Ordenando Arquivos Grandes
Exemplo do Funcionamento do Replacement Selection
Input: 21, 67, 12, 5, 47, 16 ← frente da string de input.
Input remanescente Memo´ria (P=3) Output run
21, 67, 12 5 47 16 -
21, 67 12 47 16 5
21 67 47 16 12, 5
- 67 47 21 16, 12, 5
- 67 47 - 21, 16, 12, 5
- 67 - - 47, 21, 16, 12, 5
- - - - 67, 47, 21, 16, 12, 5
O processo produz uma lista de seis chaves usando apenas treˆs posic¸o˜es de memo´ria.
22 / 40
Ordenando Arquivos Grandes
“Replacement selection” Formando Dois Runs Ordenados
Input: 33, 18, 24, 58, 14, 17, 7, 21, 67, 12, 5, 47, 16 ← frente da string de input.
Input remanescente Memo´ria (P=3) Output run
33, 18, 24, 58, 14, 17, 7, 21, 67, 12 5 47 16 -
33, 18, 24, 58, 14, 17, 7, 21, 67 12 47 16 5
33, 18, 24, 58, 14, 17, 7, 21 67 47 16 12, 5
33, 18, 24, 58, 14, 17, 7 67 47 21 16, 12, 5
33, 18, 24, 58, 14, 17 67 47 (7) 21, 16, 12, 5
33, 18, 24, 58, 14 67 (17)(7) 47, 21, 16, 12, 5
33, 18, 24, 58 (14)(17)(7) 67, 47, 21, 16, 12, 5
1◦ run completo!
23 / 40
“Replacement selection” Formando Dois Runs Ordenados.
Comec¸a a construc¸a˜o do 2◦ run.
Input remanescente Memo´ria (P=3) Output run
33, 18, 24, 58 14 17 7 -
33, 18, 24 14 17 58 7
33, 18 24 17 58 14, 7
33 24 18 58 17, 14, 7
- 24 33 58 18, 17, 14, 7
- - 33 58 24, 18, 17, 14, 7
- - - 58 33, 24, 18, 17, 14, 7
- - - - 58, 33, 24, 18, 17, 14, 7
24 / 40
Ordenando Arquivos Grandes
Comparando
No procedimento anterior t´ınhamos:
Ler as chaves na memo´ria
Ordena´-las
Escrever (output) um run que e´ o tamanho do espac¸o em memo´ria dispon´ıvel para
esse procedimento.
No exemplo das 13 chaves, ter´ıamos 5 runs.
Com “replacement selection”, temos:
No exemplo das 13 chaves, temos apenas 2 runs utilizando o mesmo espac¸o de
memo´ria.
Utilizando o procedimento de “replacement selection” temos runs mais
longos, diminuindo assim o nu´mero total de runs necessa´rios.
25 / 40
Ordenando Arquivos Grandes
Utilizando Replacement Selection
Dadas P locac¸o˜es de memo´ria, qual o tamanho me´dio do run que o procedimento
produz?
Na me´dia podemos esperar um de tamanho igual a 2P .
Quais sa˜o os custos de se utilizar “Replacement Selection”?
Sabemos que o custo de buscar cada registro individualmente no disco e´ proibitivo.
Ao inve´s disto, temos que carregar um input num buffer, o que significa que na˜o
temos toda a memo´ria para a operac¸a˜o de “Replacement Selection”. Parte da
memo´ria tem que ser usada para os buffer de input e output.
Observac¸a˜o
Para obter mais eficieˆncia, podemos combinar:
Replacement Selection.
Multi-step Merge.
26 / 40
Ordenando Arquivos Grandes
Ferramentas para melhorar a performance do External Sorting
1) Para o sorting em RAM, podemos usar por exemplo o heapsort (com multibuffering)
formando as listas ordenadas de cada run.
2) Usar o ma´ximo de RAM poss´ıvel. Fazer os runs mais longos e proporcionar mais, ou
maiores, buffers durante a fase do merge.
3) Se o nro de runs iniciais e´ muito grande, usar um multi-step merge. Pode diminuir o
nro de seeks consideravelmente.
4) Considerar a utilizac¸a˜o de “replacement selection” para formar os runs iniciais,
especialmente se existe a possibilidade que os runs estejam parcialmente ordenados.
5) Usar mais do que um disco e canal de I/O de modo que leitura e escrita possam se
sobrepoˆr. Isto e´ especialmente verdade se na˜o existem outros usua´rios no sistema.
6) Ter em mente os elementos fundamentais para o External Sorting e seus custos.
Buscar maneiras de tirar vantagem de novas arquiteturas e sistemas, como
processamento paralelo e redes locais de alta velocidade.
27 / 40
Pro´xima Aula
Pro´xima Aula
A´rvores B.
28 / 40
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.
matching.cpp: Descreve o algoritmo de intersec¸a˜o (matching).
matchingClass.cpp: Classe que descreve os principais me´todos e membros necessa´rios para executarmos a
operac¸a˜o de matching.
stringListProcess: Subclasse que suporta listas, e suas operac¸o˜es, que sa˜o arquivos de strings,uma por linha.
merge.cpp: Descreve o algoritmo de unia˜o (merge).
masterTransactionProcess.cpp: Classe que descreve o processo de transac¸a˜o mestre.
postTransactions.cpp: Implementac¸a˜o dome´todo PostTransactions da classe MasterTransactionProcess.
processMaster.cpp: Implementac¸a˜o dos me´todos ProcessNewMaster, ProcessCurrentMaster e
ProcessEndMaster.
heap.cpp: Descreve uma Heap e o me´todo insert.
heapRemove.cpp: Descreve o me´todo remove para remover elemento de uma heap.
29 / 40
Co´digos
1 // c o s e q u e n t i a l match f u n c t i o n based on a s i n g l e d l oop
2
3 i n t Match ( char∗ List1Name , char∗ List2Name , char∗ OutputListName ) ;
4 {
5 i n t MoreItems ; // t r u e i f i t ems rema ins i n both o f the l i s t s
6 // i n i t i a l i z e i n pu t and output l i s t s
7 I n i t i a l i z e L i s t ( 1 , List1Name ) ; // i n i t i a l i z e L i s t 1
8 I n i t i a l i z e L i s t ( 2 , List2Name ) ; // i n i t i a l i z e L i s t 2
9 I n i t i a l z i e O u t p u t ( OutputListName ) ;
10
11 // get f i r s t i tem from both l i s t s
12 MoreItems = N e x t I t e m I n L i s t ( 1 ) && N e x t I t e m I n L i s t ( 2 ) ;
13 w h i l e ( MoreItems ){ // loop u n t i l no i t ems i n on o f the l i s t s
14 i f ( I tem ( 1 ) < I tem ( 2 ) ){
15 MoreItems = N e x t I t e m I n L i s t ( 1 ) ;
16 }
17 e l s e i f ( I tem (1)== Item ( 2 ) ){ // Item (1) == Item (2)
18 P r o c e s s I t e m ( 1 ) ; //match found
19 MoreItems = N e x t I t e m I n L i s t ( 1 ) && N e x t I t e m I n L i s t ( 2 ) ;
20 }
21 e l s e { // Item (1) > I tem (2)
22 MoreItems = N e x t I t e m I n L i s t ( 2 ) ;
23 }
24 }
25 F i n i s h U p ( ) ;
26 r e t u r n 1 ;
27 }
Co´digo 1: matching.cpp
30 / 40
Co´digos
1 //Main members and methods o f a g e n e r a l c l a s s f o r c o s e q u e n t i a l
2 // p r o c e s s i n g
3
4 template <c l a s s itemType>
5 c l a s s C o s e q u e n t i a l P r o c e s s
6 // base c l a s s f o r c o s e q u e n t i a l p r o c e s s i n g
7 {
8 p u b l i c :
9 // the f o l l o w i n g methods p r o v i d e b a s i c l i s t p r o c e s s i n g
10 // These must be d e f i n e d i n s u b c l a s s e s
11 v i r t u a l i n t I n i t i a l i z e L i s t ( i n t ListNumber , char∗ ListName )=0;
12 v i r t u a l i n t I n i t i a l i z e O u t p u t ( char∗ OutputListName )=0;
13 v i r t u a l i n t N e x t I t e m I n L i s t ( i n t ListNumber )=0;
14 // advance to next i tem i n t h i s l i s t
15 v i r t u a l ItemType Item ( i n t ListNumber ) = 0 ;
16 // r e t u r n c u r r e n t i tem from t h i s l i s t
17 v i r t u a l i n t P r o c e s s I t e m ( i n t ListNumber )=0;
18 // p r o c e s s the i tem i n t h i s l i s t
19 v i r t u a l i n t F i n i s h U p ()=0; // complete the p r o c e s s i n g
20
21 //2−way c o s e q u e n t i a l match method
22 v i r t u a l i n t M a t c h 2 L i s t s
23 ( char∗ List1Name , char∗ List2Name , char∗ OutputListName ) ;
24 } ;
Co´digo 2: matchingClass.cpp
31 / 40
Co´digos
1 //A s u b c l a s s to suppo r t l i s t s t ha t a r e f i l e s o f s t r i n g s , one pe r l i n e
2
3 c l a s s S t r i n g L i s t P r o c e s s : p u b l i c C o s e q u e n t i a l P r o c e s s<S t r i n g&>
4 // C l a s s to p r o c e s s l i s t s t ha t a r e f i l e s o f s t r i n g s
5 {
6 p u b l i c :
7 S t r i n g L i s t P r o c e s s ( i n t NumberOfLists ) ; // c o n s t r u c t o r
8 // Bas i c l i s t p r o c e s s i n g methods
9 i n t I n i t i a l i z e L i s t ( i n t ListNumber , char∗ ListName ) ;
10 i n t I n i t i a l i z e O u t p u t ( char∗ OutputListName ) ;
11 i n t N e x t I t e m I n L i s t ( i n t ListNumber ) ; // get nex t
12 S t r i n g& item ( i n t ListNumber ) ; // r e t u r n c u r r e n t
13 i n t P r o c e s s I t e m ( i n t ListNumber ) . // p r o c e s s the i tem
14 i n t F i n i s h U p ( ) ; // complete the p r o c e s s i n g
15 p r o t e c t e d :
16 i f s t r e a m ∗ L i s t ; // a r r a y o f l i s t f i l e s
17 S t r i n g ∗ I t e m s . // a r r a y o f c u r r e n t Item from each l i s t
18 o f s t r e a m O u t p u t L i s t ;
19 s t a t i c const char∗ LowValue ;
20 s t a t i c const char∗ HighValue ;
21 } ;
Co´digo 3: stringListProcess.cpp
32 / 40
Co´digos I
1 // Co s e qu en t i a l merge p rocedu r e based on s i n g l e l oop
2
3 template <c l a s s ItemType>
4
5 i n t C o s e q u e n t i a l P r o c e s s<ItemType > : : M e r g e 2 L i s t s
6 ( char∗ List1Name , char∗ List2Name , char∗ OutputListName )
7 {
8 i n t MoreItems1 , MoreItems2 ; // t r u e i f more i t ems i n l i s t
9 I n i t i a l i z e L i s t ( 1 , List1Name ) ;
10 I n i t i a l i z e L i s t ( 2 , List2Name ) ;
11 I n i t i a l i z e O u t p u t ( OutputListName ) ;
12 MoreItems1 = N e x t I t e m I n L i s t ( 1 ) ;
13 MoreItems2 = N e x t I t e m I n L i s t ( 2 ) ;
14
15 w h i l e ( MoreItems1 | | MoreItems2 ){ // i f e i t h e r f i l e has more
16 i f ( I tem ( 1 ) < I tem ( 2 ) ){ // l i s t 1 has nex t i tem to be p r o c e s s e d
17 P r o c e s s I t e m ( 1 ) ;
18 MoreItems1 = N e x t I t e m I n L i s t ( 1 ) ;
19 }
20 e l s e i f ( I tem (1)== Item ( 2 ) ){ // l i s t s have the same item , p r o c e s s
21 P r o c e s s I t e m ( 1 ) ; // from l i s t 1
22 MoreItems1 = N e x t I t e m I n L i s t ( 1 ) ;
23 MoreItems2 = N e x t I t e m I n L i s t ( 2 ) ;
24 }
25
26
27
33 / 40
Co´digos II
28 e l s e { // Item (1)> I tem (2)
29 P r o c e s s I t e m ( 2 ) ;
30 MoreItems2 = N e x t I t e m I n L i s t ( 2 ) ;
31 }
32 }
33 F i n i s h U p ( ) ;
34 r e t u r n 1 ;
35 }
Co´digo 4: merge.cpp
34 / 40
Co´digos
1 // C l a s s Mas t e rT ran s a c t i onP roc e s s
2
3 template <c l a s s ItemType>
4 c l a s s M a s t e r T r a n s a c t i o n P r o c e s s : p u b l i c C o s e q u e n t i a l P r o c e s s<itemType>
5 //a c o s e q u e n t i a l p r o c e s s t ha t s uppo r t s
6 //master / t r a n s a c t i o n p r o c e s s i n g
7 {
8 p u b l i c :
9 M a s t e r T r a n s a c t i o n P r o c e s s ( ) ; // c o n s t r u c t o r
10 v i r t u a l i n t ProcessNewMaster ( ) = 0 ;
11 // p r o c e s s i n g when new master r ead
12 v i r t u a l i n t P r o c e s s C u r r e n t M a s t e r ()=0;
13 // p r o c e s s i n g f o r each t r a n s a c t i o n f o r a master
14 v i r t u a l i n t ProcessEndMaster ()=0;
15 // p r o c e s s i n g a f t e r a l l t r a n s a c t i o n s f o r a master
16 v i r t u a l i n t P r o c e s s T r a n s a c t i o n E r r o r ()=0;
17 //no master f o r t r a n s a c t i o n
18 // c o s e q u e n t i a l p r o c e s s i n g o f master and t r a n s a c t i o n r e c o r d s
19 i n t P o s t T r a n s a c t i o n s ( char∗ MasterFi leName , char∗ T r a n s a c t i o n F i l e N a m e ,
20 char∗ OutputListName ) ;
21 } ;
Co´digo 5: masterTransactionProcess.cpp
35 / 40
Co´digos
1 //Three−way−t e s t l oop f o r method Po s tT r an s a c t i o n s o f c l a s s
2 //Mas t e rT ran s a c t i onP roc e s s
3
4 w h i l e ( MoreMasters | | M o r e T r a n s a c t i o n s )
5 i f ( I tem (1)< I tem ( 2 ) ){ // f i n i s h t h i s master r e c o r d
6 ProcessEndMaster ( ) ;
7 MoreMasters = N e x t I t e m I n L i s t ( 1 ) ;
8 i f ( MoreMasters ) ProcessNewMaster ( ) ;
9 }
10 e l s e i f ( I tem ( 1 ) == Item ( 2 ) ){ // t r a n s a c t i o n matches master
11 P r o c e s s C u r r e n t M a s t e r ( ) ; // ano the r t r a n s a c t i o n f o r master
12 P r o c e s s I t e m ( 2 ) ; // output t r a n s a c t i o n r e c o r d
13 M o r e T r a n s a c t i o n s = N e x t I t e m I n L i s t ( 2 ) ;
14 }
15 e l s e { // Item (1) > I tem (2) t r a n s a c t i o n wi th no master
16 P r o c e s s T r a n s a c t i o n E r r o r ( ) ;
17 M o r e T r a n s a c t i o n s = N e x t I t e m I n L i s t ( 2 ) ;
18 }
Co´digo 6: postTransactions.cpp
36 / 40
Co´digos
1 //Master r e c o r d p r o c e s s i n g f o r l e d g e r o b j e c t s
2
3 i n t L e d g e r P r o c e s s : : ProcessNewMaster ( )
4 { // p r in t the heade r and se tup l a s t month ’ s ba l ance
5 l e d g e r . P r i n t H e a d e r ( O u t p u t L i s t ) ;
6 l e d g e r . B a l a n c e s [ MonthNumber ] = l e d g e r . B a l a n c e s [ MonthNumber−1];
7 }
8
9 i n t L e d g e r P r o c e s s : : P r o c e s s C u r r e n t M a s t e r ( )
10 {// add the t r a n s a c t i o n amount to the ba l anc e f o r t h i s month
11 l e d g e r . B a l a n c e s [ MonthNumber]+= j o u r n a l . Amount ;
12 }
13
14 i n t L e d g e r P r o c e s s : : ProcessEndMaster ( )
15 { // p r i n t the ba l a n c e s l i n e to output
16 P r i n t B a l a n c e s ( O u t p u t L i s t , l e d g e r . B a l a n c e s [ MonthNumber−1] ,
17 l e d g e r . B a l a n c e s [ MonthNumber ] ) ;
18 }
Co´digo 7: processMaster.cpp
37 / 40
Co´digos I
1 // C l a s s Heap and Method In se r t
2 c l a s s Heap
3 {
4 p u b l i c :
5 Heap ( i n t maxElements ) ;
6 i n t I n s e r t ( char∗ newKey ) ;
7 char∗ Remove ( ) ;
8
9 p r o t e c t e d :
10 i n t MaxElements ; i n t NumElements ;
11 char∗∗ HeapArray ;
12 v o i d Exchange ( i n t i , i n t j ) ; // exchange e l ement i and j
13 i n t Compare ( i n t i , i n t j ){ // compare e l ement i and j
14 r e t u r n st rcmp ( HeapArray [ i ] , HeapArray [ j ] ) ;
15 }
16 } ;
17
18 i n t Heap : : I n s e r t ( char∗ newKey )
19 {
20 i f ( NumElements == MaxElements ) r e t u r n f a l s e ;
21 NumElements++; //add the new key at the l a s t p o s i t i o n
22 HeapArray [ NumElements ] = newKey ;
23 // re−o r d e r the heao
24 i n t k = NumElements ; i n t p a r e n t ;
25 w h i l e ( k>1) // k has a pa r en t
26 {
27 p a r e n t = k / 2 ;
38 / 40
Co´digos II
28 i f ( Compare ( k , p a r e n t )>=0) break ;
29 //HeapArray [ k ] i s i n the r i g h t p l a c e
30 // e l s e exchange k and pa r en t
31 Exchange ( k , p a r e n t ) ;
32 k = p a r e n t ;
33 }
34 r e t u r n t r u e ;
35 }
Co´digo 8: heap.cpp
39 / 40
Co´digos
1 //MethodRemove o f c l a s s Heap removes the sm a l l e s t e l ement and r e o r d e r s the heap
2 char∗ Heap : : Remove ( )
3 { // remove the sm a l l e s t e lement , r e o r d e r the heap
4 // and r e t u r n the sm a l l e s t e l ement
5 // put the sm a l l e s t v a l u e i n t o ’ v a l ’ f o r use i n r e t u r n
6 char∗ v a l = HeapArray [ 1 ] ;
7
8 // put the l a r g e s t v a l u e i n t o r oo t
9 HeapArray [ 1 ] = HeapArray [ NumElements ] ;
10 // d e c r e a s e the number o f e l ement s
11 NumElements−−;
12
13 // r e o r d e r the heap by exchang ing and moving down
14 i n t k=1; // node o f heap tha t c o n t a i n s the l a r g e s t v a l u e
15 i n t newK ; // node to exchange wi th l a r g e s t v a l u e
16 w h i l e (2∗k <= NumElements ) //k has at l e a s t one c h i l d
17 { // s e t newK to the i ndex o f sm a l l e s t c h i l d o f k
18 i f ( Compare (2∗k ,2∗ k+1)<0) newK=2∗k ;
19 e l s e newK = 2∗k+1;
20 //done i f k and newK are i n o r d e r
21 i f ( Compare ( k , newK)<0) break ; // i n o r d e r
22 Exchange ( k , newK ) ; //k and newK out o f o r d e r
23 k = newK ; // con t i nu e down the t r e e
24 }
25 r e t u r n v a l ;
26 }
Co´digo 9: heapRemove.cpp
40 / 40