Baixe o app para aproveitar ainda mais
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 esteja mais apontandopara 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 é gerado um 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.
Compartilhar