Aula 17 - OrdMemSecundaria_Intercalacao Polifasica

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Intercalação Polifásica
Lívia N. Andrade
Problema com a intercalação balanceada de vários caminhos:
Necessita de um grande número de fitas.
Faz várias leituras e escritas entre as fitas envolvidas.
Para uma intercalação balanceada de f caminhos são necessárias 2f fitas.
Alternativamente, pode-se copiar o arquivo quase todo de uma única fita de saída para f fitas de entrada, o que reduz o número de fitas para f + 1
porém há um custo de uma cópia adicional do arquivo.
Solução:
Usar intercalação polifásica
 um método que elimina a necessidade de realizar a cópia adicional.
Ziviane, cap 4
2
Estratégia da Intercalação Polifásica
Os blocos ordenados são distribuídos de forma desigual entre as fitas disponíveis, deixando uma fita livre.
Em seguida, a intercalação de blocos ordenados é executada até que uma das fitas esvazie.
Neste ponto, uma das fitas de saída troca de papel com a fita de entrada.
Idéia: deixar sempre uma fita vazia para ser utilizada como uma fita auxiliar.
Ziviane, cap 4
3
Exemplo:
1º Os blocos ordenados são distribuídos de forma desigual entre as fitas disponíveis, deixando uma fita livre.
Fita 1 INRT AACEN
Fita 2 ACEL AAD
Fita 3 AABCLO
Blocos ordenados produzidos por meio da seleção por substituição
Ziviane, cap 4
4
Exemplo:
1º Os blocos ordenados são distribuídos de forma desigual entre as fitas disponíveis, deixando uma fita livre.
Fita 1 INRT AACEN
Fita 2 ACEL AAD
Fita 3 AABCLO
Blocos ordenados produzidos por meio da seleção por substituição
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3
Distribuição dos blocos ordenados de forma desigual
Ziviane, cap 4
5
Exemplo:
Fase de intercalação:
Considere os blocos abaixo ordenados por meio da seleção por substituição
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3
Ziviane, cap 4
6
Exemplo:
Fase de intercalação:
Iniciar a primeira passada da intercalação polifásica
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3 
Auxiliar
Ziviane, cap 4
7
Exemplo:
Fase de intercalação:
Iniciar a primeira passada da intercalação polifásica
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3 AACEINNRT
Auxiliar
Ziviane, cap 4
8
Exemplo:
Fase de intercalação:
Iniciar a primeira passada da intercalação polifásica
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3 AACEINNRT
Auxiliar
Ziviane, cap 4
9
Exemplo:
Fase de intercalação:
Resultado da primeira passada
Fita 1 INRT ACEL AABCLO
Fita 2 AACEN AAD
Fita 3 AACEINNRT AAACDEL
Auxiliar
Ziviane, cap 4
10
Exemplo:
Fase de intercalação:
Utilizar a fita que não contém mais blocos como fita auxiliar
Fita 1 AABCLO
Fita 2
Fita 3 AACEINNRT AAACDEL
Auxiliar
Ziviane, cap 4
11
Exemplo:
Fase de intercalação:
	
Fita 1 AABCLO
Fita 2 AAAABCCILNNORT
Fita 3 AACEINNRT AAACDEL
Auxiliar
Ziviane, cap 4
12
Exemplo:
Fase de intercalação:
	após intercalar, novamente utilizar a fita que não contém mais blocos como fita auxiliar 
Fita 1
Fita 2 AAAABCCILNNORT
Fita 3 AAACDEL
Auxiliar
Ziviane, cap 4
13
Exemplo:
Fase de intercalação:
Fita 1 AAAAAAABCCCDEILLNNORT
Fita 2 AAAABCCILNNORT
Fita 3 AAACDEL
Auxiliar
Ziviane, cap 4
14
Exemplo:
Fase de intercalação:
 A intercalação é realizada em muitas fases.
 As fases não envolvem todos os blocos. 
 Nenhuma cópia direta entre fitas é realizada.
Fita 1 AAAAAAABCCCDEILLNNORT
Fita 2 AAAABCCILNNORT
Fita 3 AAACDEL
Ziviane, cap 4
15
A implementação da intercalação polifásica é simples.
A parte mais delicada está na distribuição inicial dos blocos ordenados entre as fitas.
Distribuição dos blocos nas diversas etapas do exemplo:
Análise:
A análise da intercalação polifásica é complicada.
O que se sabe é que ela é ligeiramente melhor do que a intercalação balanceada para valores pequenos de f.
Para valores de f > 8, a intercalação balanceada pode ser mais rápida.
Exercício 34 da lista
Usando o resultado obtido na primeira fase da intercalação balanceada de vários caminhos implementada por meio da seleção por substituição do exercício anterior, mostre os passos para uma intercalação polifásica com 5 fitas.
Ziviane, cap 4
18
Resolvendo o exercício 34
Fita 1
Fita 2
Fita 3
13 23 45 65 67 89 98
12 12 21 43 43 55 59 61 62 66 99
 4 5 7 8 10 11 20 32 37 40 60 90
0 8 9 13 18 19 21 25 27 37 71 73
Fita 4
 2 3 6 8 23 26 28 30 62 76 98
Fita 5
Auxiliar
Ziviane, cap 4
19
Resolvendo o exercício 34
Fita 1
Fita 2
Fita 3
13 23 45 65 67 89 98
12 12 21 43 43 55 59 61 62 66 99
 4 5 7 8 10 11 20 32 37 40 60 90
0 8 9 13 18 19 21 25 27 37 71 73
Fita 4
 2 3 6 8 23 26 28 30 62 76 98
Fita 5
2 3 4 5 6 7 8 8 10 11 12 12 13 20 21 23 23 26 28 30 32 37 40 43 43 45 55 59 60 61 62 62 65 66 67 76 89 90 98 98 99
Ziviane, cap 4
20
Resolvendo o exercício 34
Fita 1
Fita 2
Fita 3
0 8 9 13 18 19 21 25 27 37 71 73
Fita 4
Fita 5
2 3 4 5 6 7 8 8 10 11 12 12 13 20 21 23 23 26 28 30 32 37 40 43 43 45 55 59 60 61 62 62 65 66 67 76 89 90 98 98 99
Auxiliar
Ziviane, cap 4
21
Resolvendo o exercício 34
Fita 1
Fita 2
Fita 3
0 8 9 13 18 19 21 25 27 37 71 73
Fita 4
Fita 5
2 3 4 5 6 7 8 8 10 11 12 12 13 20 21 23 23 26 28 30 32 37 40 43 43 45 55 59 60 61 62 62 65 66 67 76 89 90 98 98 99
0 2 3 4 5 6 7 8 8 8 9 10 11 12 12 13 13 18 19 20 21 21 23 23 25 26 27 28 30 32 37 37 40 43 43 45 55 59 60 61 62 62 65 66 67 71 73 76 89 90 98 98 99
Ziviane, cap 4
22
Bibliografia consultada
Livro:
Projeto de algoritmos com implementações em PASCAL e C – Nivio Ziviani