Ordenação Externa Intercalação Balanceada e Intercalação

Prévia do material em texto

Ordenação Externa: Intercalação Balanceada e Intercalação 
Polifásica
Luis Paulo M. Freire, Thiago do N. Ferreira, Thiago G. Nepomuceno da Silva 
Universidade Estadual do Ceará (UECE)
Fortaleza, CE – Brasil
Resumo. Este artigo é o resultado do segundo trabalho da disciplina de 
Projeto de Análise de Algoritmo onde é apresentado a ordenação externa com 
duas formas de intercalação de séries: a Intercalação Balanceada e a 
Intercalação Polifásica. Para a sua resolução, foi proposto um algoritmo e 
também foi realizado alguns testes para verificar as diferenças entre cada um 
e que no decorrer do artigo discutiremos mais aprofundado.
1. Introdução
Estamos acostumados a estudarmos métodos de ordenação onde todos os números os 
quais desejamos ordenar, cabem na memória. Assim, a nossa única preocupação com 
esses algoritmos são com o tamanho, velocidade ou quantidade de memória alocado 
extra. A esse tipo de classificação damos o nome de ordenação interna.
Na ordenação externa, os valores que desejamos ordenar, estão guardados em 
fitas ou discos e se quiséssemos colocar esses valores na memória principal para 
ordenar, seriamos impedido pela limitação física da mesma.
Assim, ordenação externa surge como uma alternativa para a resolução desse 
problema, fazendo com que o arquivo original seja dividido em várias séries com 
pequenos registros, onde iremos então intercalar ordenando e no final, teremos então 
esse nosso arquivo final, já ordenado.
2. Ordenação Externa
Um aspecto predominante na escolha de algoritmo de ordenação é o tempo gasto para 
ordenar os números. Para algoritmo de ordenação interna, as medidas de complexidade 
relevantes são: o número de comparações e o número de troca (movimentações) entre as 
chaves. Para esse tipo de ordenação, existem diversos algoritmos que fazem esse 
trabalho onde podemos citar como exemplo o MergeSort, BubbleSorte ou QuickSort.
A ordenação externa envolve arquivos compostos por um número de registros 
que é maior do que a memória principal do computador possa armazenar. Os métodos 
de ordenação externa são muito diferentes dos métodos de ordenação interna. Em 
ambos os casos o problema é o mesmo: rearranjar os registros de um arquivo em ordem 
ascendente ou descendente. Entretanto, na ordenação externa as estruturas de dados têm 
que levar em conta o fato de que os dados estão armazenados em unidades de memória 
externa, são relativamente muito mais lentas do que a memória principal. (Ziviani)
Nas memórias externas, tais como fitas, discos e tambores magnéticos, os dados 
são armazenados como um arquivo sequencial, onde apenas um registro pode ser 
acessado em um dado momento. Esta é uma restrição forte se comparada com as 
possibilidades de acesso da estrutura de dados do tipo vetor. Consequentemente, os 
métodos de ordenação interna apresentados no inicio dessa seção são inadequados para 
ordenação externa, e então técnicas de ordenação completamente diferentes têm que ser 
usadas. Existem três importantes fatores que fazem os algoritmos para ordenação 
externa diferentes dos algoritmos para ordenação interna, a saber: (ZIVIANI, 2004)
1. O custo para acessar um item é algumas ordens de grandeza maior do 
que os custos de processamento na memória interna. 0 custo principal na 
ordenação externa está relacionado com o custo de transferir dados entre 
a memória interna e a memória externa. 
2. Existem restrições severas de acesso aos dados. Por exemplo, os itens 
armazenados em fita magnética só podem ser acessados de forma 
sequencial. Os itens armazenados em disco magnético podem ser 
acessados diretamente, mas a um custo maior do que o custo para acessar 
sequencialmente, o que contraindica o uso do acesso direto. 
3. O desenvolvimento de métodos de ordenação externa é muito dependente 
do estado atual da tecnologia. A grande variedade de tipos de unidades 
de memória externa pode tornar os métodos de ordenação externa 
dependentes de vários parâmetros que afetam seus desempenhos. 
A eficiência de uma classificação externa é medida em termos da quantidade 
total do tempo necessário para que os dados sejam lidos, ordenados e gravados na área 
de trabalho; isto corresponde à fase inicial do processo de ordenação.
Na fase seguinte, as séries ordenadas são lidas e intercaladas duas a duas, três a 
três, etc. O número de séries intercaladas em cada passo corresponde ao número de 
caminhos. Quanto maior for o número de caminhos, mais complexo será o algoritmo de 
intercalação (Merge). Como este processo é utilizado várias vezes para conseguir juntar 
todas as séries, em geral opta-se por trabalhar com 2 ou 3 caminhos.
Os fatores que influem na eficiência de um algoritmo de classificação externa 
são os seguintes:
• Número de séries que serão produzidas;
• O Tamanho de cada série e se possuem o mesmo tamanho;
• A forma de distribuição das séries pelos arquivos de trabalho;
• Características dos blocos e das memórias intermediárias utilizadas na 
fase de classificação.
Com as séries já formadas, podemos então fazer a intercalação entre elas. Para 
isso, precisamos de alguns métodos que sejam responsáveis por fazer esse trabalho. A 
esses métodos, daremos o nome de Merge2, Merge3 e o Mergek, responsáveis por fazer 
a intercalação de duas séries, três séries, e k séries respectivamente.
2.1. Intercalação de 2 Caminhos
Também conhecido como Merge2, esse método é responsável por intercalar 2 
séries. Para exemplificar, iremos considerar que em um arquivo possua o seguinte 
conjunto de valores:
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
3 7 9 11 1 5 8 9 12 13
Iremos então dividir os valores em 2 séries. Com isso, temos o seguinte:
Arq1 → Arq2 →
Com as séries já ordenadas, podemos então fazer a intercalação. Iremos 
considerar que cada série possui uma marcação que será responsável por percorrer toda 
série. Assim, o processo consistem em percorrer toda as séries, do começo até o fim, 
intercalando, ou seja, procurando os menores valores (se o problema foi ordenar por 
ordem crescente). Se a série contiver o menor valor, a marcação avança para a próxima 
casa; caso contrário, a marcação não se move.
No final da intercalação, teremos uma única série ordenada.
S1 S2 S3 S4 S5 S6 S7 S8 S9 S10
1 3 5 7 8 9 9 11 12 13
Com isso, então pseudocódigo do método merge2
PROCEDIMENTO MERGE2(R,S,m,n) 
 ENTRADA: INTEIROS m,n 
 Registro R com duas séries a intercalar 
 
 SAIDA: Registro S com uma única série ordenada 
 
 // R (1:m) (Primeira sérire ordenada) 
 // R (m+1:n) (Seguda série ordenada) 
 
 // S (1:n) (Série ordenada/intercalada) 
 
 //Variáveis auxiliares 
 // K (1:n) Vetor de inteiros 
 // i,j,k,ini,fim: ponteiros/contadores 
 
R1 R2 R3 R4
3 7 9 11
R5 R6 R7 R8 R9 R10
1 5 8 9 12 13
 i = 1; 
 k = 1; 
 j = m+1; 
 
 ENQUANTO (i<=m AND j<=n){ 
 SE (Ki <= Kj) 
 Sk = Ri 
 i++; 
 SENÃO 
 Sk = Rj 
 j++; 
 SE (i >m) 
 ini = j 
 fim = n 
 SENÃO 
 ini = i 
 fim = m 
 //Copia o restante da série para a série resultado
 PARA i=ini ATÉ fim 
 Sk = Ri 
 k++ 
 FIM_PARA 
 FIM_ENQUANTO 
Retorna 
2.2. Intercalação de 3 Caminhos
Também conhecida como Merge3, ela é responsável por intercalar três séries. Nesse 
algoritmo, cada série irá conter uma marcação responsável por percorrer todos os 
valores. Assim, será necessário a implementação de método responsável por pegar o 
menor valor dos três número de cada série e com isso, ir colocando no arquivo final. A 
ele daremos o nome de MENOR, que será uma função responsável por retornar o menor 
valor entre três números. 
Caso alguma das séries chegue ao fim, ou seja, a marcação dela não estejamais 
apontando para nenhum dos valores da série, basta então chamar o procedimento 
Merge2 que ele será responsável por intercalar o restante das duas séries.
2.3. Intercalação de K caminhos
Esse tipo de intercalação é muito parecido com o de três caminho. Tomaremos como 
exemplo o k=4; com esse valor, basta que façamos um método MENOR que retorne o 
menor número entre 4 números. Quando a marcação de uma série terminar, basta então 
chamar o método Merge3.
Normalmente, esse tipo de operação não é muito utilizado devido a 
complexidade desse algoritmo, mesmo sabendo que ele pode reduzir o número de 
leituras e de gravações nos arquivos.
3. Intercalação Balanceada
Nesse tipo de intercalação, pretende-se formar séries com valores iguais de elementos. 
Para exemplificar esse tipo de intercalação, consideramos que o arquivo está 
armazenado em fitas magnéticas e que o arquivo contem 22 registros: (VIANA e 
CINTRA, 2011)
 I N T E R C A L A C A O B A L A N C E A D A
Iremos então considerar que a memória interna do computador só tem espaço 
para três registros. O número de fitas magnéticas disponíveis são seis. 
Na primeira etapa o arquivo é lido de três em três registros. Cada bloco de três 
registros é ordenado e escrito em uma das fitas de saída. Nesse exemplo são lidos os 
registros INT e escrito o bloco INT na fita 1, a seguir são lidos os registros ERC e 
escrito o bloco CER na fita 2, e assim por diante, conforme é mostrado mais abaixo. 
Três fitas são utilizadas em uma intercalação de 3 caminhos (Merge3).
Fita 1 → I N T A C O A D E
Fita 2 → C E R A B L A
Fita 3 → A A L A C N 
Na segunda etapa os blocos ordenados devem ser intercalados. 0 primeiro 
registro de cada uma das três fitas é lido para a memória interna, ocupando toda a 
memória interna. A seguir o registro contendo a menor chave dentre as três é retirado e 
o próximo registro da mesma fita é lido para a memória interna, repetindo-se o 
processo. Quando o terceiro registro de um dos blocos é lido aquela fita fica inativa até 
que o terceiro registro das outras fitas também sejam lidos e escritos na fita de saída, 
formando um bloco de 9 registros ordenados. A seguir o segundo bloco de 3 registros 
de cada fita é lido para formar outro bloco ordenado de nove registros, o qual é escrito 
em uma outra fita. Ao final três novos blocos ordenados são obtido:
Fita 4 A A C E I L N R T→
Fita 5 A A A B C C L N O→
Fita 6 A A D E→
A seguir mais uma intercalação de 3 caminhos das fitas 4, 5 e 6 para as fitas 1, 2 
e 3 completa a ordenação. Se o arquivo exemplo tivesse um número maior de registros, 
então vários blocos ordenados de 9 registros seriam formados nas fitas 4, 5 e 6. Neste 
caso, a segunda passada produziria blocos ordenados de 27 registros nas fitas 1, 2 e 3; a 
terceira passada produziria blocos ordenados de 81 registros nas fitas 4, 5 e 6, e assim 
sucessivamente, até obter-se um único bloco ordenado. 
No final, teremos o seguinte resultado:
A A A A A A A B C C C D E E I L L N N R O T
4. Intercalação Polifásica
O objetivo deste tipo de intercalação é distribuir as séries iniciais de forma otimizada, 
de modo que menos passos sejam necessários para a classificação total.
Para ser otimizada, a intercalação polifásica necessita de uma distribuição 
consistente de partições iniciais.
Uma forma de eliminar as cópias de partições sem que elas sejam intercaladas é 
fazer sempre intercalações de ordem F-1. A intercalação polifásica opera dessa forma, 
exigindo, entretanto, que a fase de classificação interna distribua as partições, entre os 
F-1 arquivos disponíveis para entrada, de maneira especialmente determinada para 
otimização do algoritmo. (FERRAZ, 2003)
Em cada fase do algoritmo intercalam-se F-1 arquivos até chegar ao final de 
qualquer uma delas. Nesse pronto, interrompe-se a fase deixando o restante dos 
arquivos para a fase seguinte.
Considere-se, por exemplo, a intercalação de 31 partições com F=4.
Instante Arquivo 1 Arquivo 2 Arquivo 3 Arquivo 4 Nº de Leituras
Inicialmente 13x100 11X100 7x100
Após fase 1 6x100 4x100 7x300 2100
Após fase 2 2x100 4x500 3x300 2000
Após fase 3 2x900 2x500 1x300 1800
Após fase 4 1x1700 1x900 1x500 1700
Após fase 5 1x3100 3100
Total 10700
Considere-se, por exemplo, F=4. Na penúltima fase os três primeiros arquivos 
conterão 1,1,1 partições. Em geral, se em uma fase existem (a,b,c) partições, na fase 
anterior existiam (a+b,a+c,a) partições.
Após a intercalação, são produzidas a partições sendo a = min(a+b,a+c,a). O 
comportamento ótimo do processo ocorre quanto o número total de partições iniciais 
pertence a uma série de Fibonacci generalizada.
Em função do número de arquivos F a serem utilizados é gerada uma tabela de 
distribuição com base na Série de Fibonacci. É necessário então que o algoritmo de 
classificação externa contenha uma tabela desta distribuição em função do valor de F. 
Sabemos que o modo similar à intercalação de múltiplos caminhos, para F arquivos 
devemos ter k = (F-1) caminhos.
Temos logo abaixo a tabela de um dos casos. Caso o número de séries não seja 
esteja contido na tabela, considerar a distribuição imediatamente superior; isso acarreta 
que durante a fase de intercalação as séries complementares sejam vazias, ou seja, já foi 
atingido seu final de arquivo.
Nível T1 T2 T3 Séries
N a b c t
n+1 a+b a+c a t+2a
0 1 0 0 1
1 1 1 1 3
2 2 2 1 5
3 4 3 2 9
4 7 6 4 17
5 13 11 7 31
6 24 18 13 55
7 42 37 24 103
8 79 66 42 187
... .. ... ... ...
Podemos usar o seguinte exemplo para testar essa interpolação:
Vamos classificar por interpolação polifásica 25 séries utilizando F=4 arquivos. 
Consultando a tabela acima, observamos que o número 31 constante é aquele que mais 
se aproxima de 25; no caso seriam distribuídos entre os arquivos 6 séries fictícias 
vazias.
Utilizando o Merge3, a sequência de intercalações seria esta:
Fase T1 T2 T3 T4
1 13x1 11x1 7x1 - 
2 6x1 4x1 - 7x3
3 2x1 - 4x5 3x3
4 - 2x9 2x5 1x3
5 1x17 1x9 1x5 -
6 - - - 1x31
5. Resultados Obtidos
Para a execução dos testes, foram gerados arquivos com valores a serem ordenados 
onde cada número está localizado em uma linha.
5.1. Configuração da Máquina
A máquina em que foram realizados os testes tem a seguinte configuração: 
• Processador: Intel dual core 2.70GHz 2.70GHz 
• 4GB ram DDR2 400mhz 
• Placa de Video ATI HADEON 4850 1GB 
• Windos 7 Ultimate 64bits 
5.2. Resultados
Na realização dos testes, foram gerados três arquivos com números aleatórios a serem 
classificados. Assim, foram gerados arquivos com as seguintes quantidades de números:
• 250.000 elementos
• 500.000 elementos
• 1.000.000 elementos
Cada instância foi executada três vezes. Com o tempo de cada uma, foi tirado a 
média aritmética. Foram utilizados dois como sendo o número de caminhos. Na tabela 
abaixo, podemos ver o tempo médio, juntamente com a quantidades de séries e de 
registro por cada série:
Intercalação Balanceada:
Registros Números de Séries Registros por Séries Tempo (ms)
250000 4 62500 10,09
500000 4 125000 15,72
1000000 4 250000 40,8
Intercalação Polifásica:
Registros Números de Séries Registros por Séries Tempo (ms)
250000 5 50000 9,2
500000 5 100000 18,59
1000000 5 200000 27,7
Logo abaixo, o gráfico com os resultados em relação ao tempo: 
5.3. Melhorias no método Merge
É proposto ainda um novo método, mais simples e que mostrou-se mais eficiente nos 
testes realizados.
No método, os valores são lidos do arquivo a ser ordenados e colocados em um 
vetor de registros, até que os elementos não caibam mais no vetor (limite de memória), 
então esse vetor é ordenado e é gerado um arquivo com os registros desse vetor. 
O processo se repete para os registros que faltam. Então teremos alguns arquivos 
onde em cada um, individualmente, os registros estão ordenados.
É feito um Merge em todos os arquivos de uma vez e é geradoum arquivo de 
saída com o resultado do procedimento Merge.
5.4. Análise da Complexidade
Sobre a complexidade da ordenação externa podemos afirmar: (FERREIRA, 2011)
a) Classificação por Intercalação Balanceada: o tempo de computação 
depende essencialmente do número de passagens sendo feitas sobre os 
dados.O uso de uma intercalação de ordem mais alta resultaria em 
decréscimo do número de passgens a serem feitas, sem uma mudança 
significativa do tempo de intercalação interna . A ordem de intercalação 
é limitada, principalmente pela quantidade de memória interna, 
disponível para o uso como memórias intermediárias de entrada/saída. 
Uma intercalação de k-vias precisará usar 2k + 2 mémorias 
intermediárias. É preciso, adicionalmente, de uma outra fita para a saída 
gerada durante uma intercalação. Portanto, devem estar disponíveis k+1 
fitas, para a intercalação de k-vias com as fitas. Usando k+1 fitas, para 
executar uma intercalação de k-vias, torna-se necessária uma passagem 
adicional sobre a fita de saída, para redistribuir as corridas em k fitas 
para o próximo nível de intercalações. Essa passgem de redistribuição 
pode ser evitada, através do uso de 2k fitas. 
Estratégia k+1 fitas: assume-se que o número de corridas gerado, m é 
uma potência do k. Primeiramente provoca-se uma passagem sobre o 
arquivo inteiro. As passagens de intercalação é log k m e as passagens de 
redistribuição é logkm-1. Então, a quantidade total de passagens feitas 
sobre o arquivo é 2 log km. Se o tempo para rebobinar uma fita de 
entrada inteira for t, então, o tempo de rebobinamento sem sobreposição 
está em torno de 2 logkmt. Usando-se as fitas de saída na ordem cíclica, 
k+1,1,1,2,..,k. Quando isso está sendo feito, a redistribuição da fita de 
saída requer menos do que uma passagem completa sobre o arquivo. A 
única diferença da estratégia k+1 fitas é que cada passagem de 
distribuição lê e grava apena (k-1)/k do arquivo. Portanto o número 
efetivo de passagens sobre os dados é (2-1/k)logkm+1/k 
Estratégia 2k fitas: executa-se logkm passagens de intercalação , além da 
passagem inicial para criação de corridas. Seja t o tempo para rebobinar 
o arquivo de entrada inteiro. O tempo total de rebobinar está então 
limitado dentro de (2+(logkm-1)/k)t 
b) Intercalação Polifásica: a intercalação balanceada de k-vias caracteriza-
se pela distribuição balanceada ou uniforme das corridas a serem 
intercaladas com k fitas de entrada. Em conseqüência disso necessita-se 
2k fitas, para evitar as passagens disperdiçadas sobre os dados, durante 
os quais as corridas são apenas redistribuídas nas fitas, em preparação 
para a próxima passagem de intercalação. Usando-se menos de 2k fitas 
em uma intercalação de k-vias evita-se inteiramente essas passagens de 
redistribuição disperdiçadas, precisa-se somente distribuir a "quantidade 
correta" de corridas em fitas diferentes. O truque deste tipo de 
intercalação consiste em distribuir inicialmente as corridas, de tal 
maneira que em todas as fases, exceto na última, apenas uma fita torne-
se fazia. Nesse caso, como terá duas fitas de entrada não vazias e uma 
fita vazia para a saída, pode-se prosseguir para a fase seguinte sem 
redistribuição de corridas. A intercalação polifásica requer que a 
quantidade inicial de corridas seja exatamente um número de fibonacci. 
Quando isso não for possível, pode-se acrescentar algumas corridas 
ficticías, para obter o número necessário de corridas.
c) Classificação com menos de 3 fitas: As intercalações anteriores, 
polifásica e balanceada, precisam de, pelo menos, 3 fitas para conduzir a 
classificação. Tendo n como a quantidade de registros, constatou-se que 
esses métodos necessitam apenas o tempo O(n log n). Segue abaixo os 
teorema para classificação com 1 e 2 fitas.
Teorema 1: Qualquer algoritmo que classifica n registros, usando uma fita, deve 
levar o tempo>=O(n²).
Teorema 2: n registros podem ser classificados com duas fitas em tempo O(n log 
n) se for possível executar uma regravação de registro no lugar, sem destruir os 
registros adjacentes. 
6. Conclusão
A ordenação externa é uma ótima solução quando se deseja classificar registros em 
sistemas onde a memória principal não tem espaço suficiente para comportar todos os 
registros. 
Mesmo sabendo da dificuldade em relação ao meio físico, o tempo na execução 
se tornou coerente com os resultados esperados mesmo para um método genérico.
Percebemos também que o método de interpolação polifásica, mesmo sendo um 
método mais complexo de implementar, reduz o tempo de ordenação pois evita fazer 
movimentações desnecessárias entre os arquivos.
References
 ZIVIANI, Nivio. Projeto de algoritmos: com implementaões em Pascal e C. 2.ed. rev. e 
ampliada São Paulo: Pioneira Thomson Learning, 2004. 552 p. ISBN 8522103909
FERRAZ, Inhaúma Neves. Programação com Arquivos. São Paulo: Editora Manole 
Ltda, 2003. 345 p.
VIANA, Gerardo Valdisio Rodrigues; CINTRA, Glauber Ferreira. Pesquisa e 
ordenação de dados. Fortaleza: S, 2011. Disponível em: 
<http://www.lia.ufc.br/~valdisio/tg/po3.pdf>. Acesso em: 03 jun. 2011.
FERREIRA, Rejane Apolo. Classificação Externa. Porto Alegre: , 2011. Disponível em: 
<http://www.inf.unisinos.br/~ari/estrut/trab61/estrutura.htm>. Acesso em: 04 jul. 
2011.
	1. Introdução
	2. Ordenação Externa
	2.1. Intercalação de 2 Caminhos
	2.2. Intercalação de 3 Caminhos
	2.3. Intercalação de K caminhos
	3. Intercalação Balanceada
	4. Intercalação Polifásica
	5. Resultados Obtidos
	5.1. Configuração da Máquina
	5.2. Resultados
	5.3. Melhorias no método Merge
	5.4. Análise da Complexidade
	6. Conclusão