Classificação Externa

Classificação Externa

Inhaúma Neves FerrazDepartamento de Ciência da Computação

Universidade Federal [email protected]

2

Sumário

Introdução e ConceitoGeração de Partições ClassificadasIntercalação das Partições Classificadas

Introdução e Conceito

4

Aplicações usando Classificação

Os programas desenvolvidos para algumas áreas de aplicação, como processamento de dados comercial, podem gastar a maior parte do seu tempo de computação em atividades de classificação e/ou pesquisas para produzir relatórios, tabelas formatadas, etc.Calcula-se que cerca da quarta parte de todo o tempo consumido em máquina seja gasto em atividades de classificação

5

Tipos de Classificação

A classificação de registros de um arquivo pode ser de dois tipos:Classificação interna: com utilização exclusiva de memória principalClassificação externa: com utilização de memória secundária

6

Conceito de Classificação Externa

Classificação interna: lista de registros pode ser mantida inteiramente na memória principal durante a classificaçãoClassificação externa: há mais registros a serem classificados do que é possível manter na memória principal em qualquer momentoNa classificação externa o parâmetro fundamental é o número de operações de entrada e saída.Pode-se classificar um arquivo sobre ele mesmo ou utilizar armazenamento auxiliar A classificação sobre ele mesmo poupa espaço porém corre o risco de

inconsistência em caso de término anormal de processamentoA Classificação Externa divide os arquivos em pequenas frações que são ordenadas e intercaladas em dois estágios: Classificação Intercalação.

7

Modelo da Classificação Externa

8

Estágio de Classificação

Uma partição é uma seqüência classificada de n registros.Registros são lidos de arquivos de entrada (não classificados) e de partições (classificadas)Estes registros são classificados e gravados em arquivos de saída ou partições classificadas.

Geração de Partições Classificadas

10

Métodos do Estágio de Classificação

Métodos Classificação interna Seleção com substituição Seleção natural.

Considera-se que a memória principal tenha capacidade para armazenar M registros do arquivo a classificar

Classificação Interna

12

Classificação Interna

Critério fundamental de eficiência da classificação interna: número de comparações entre chaves de registrosConsiste na leitura de MAX_MEMO registros para a memória, classificação desses registros por qualquer processo de classificação interna e gravação desses registros classificados em uma partição.Todas as partições classificadas contém MAX_MEMO registros, exceto, talvez, a última

13

Processos de classificação interna

Troca: bubble sort, bubble com “flag”, shaker sort, quick sortSeleção: direta, heap sort,Inserção: simples, shell sortOutros: merge sort, etc.

14

Visão geral da Geração de partições Classificadas

Seleção com Substituição

16

Seleção com Substituição

Aproveita a possível classificação parcial do arquivo de entradaAlgoritmo:

1. Ler MAX_MEMO registros do arquivo para a memória2. Selecionar, no “array” em memória, o registro com menor chave3. Gravar na partição de saída o registro com menor chave4. Substituir, no “array” em memória, o registro gravado na saída pelo

próximo registro do arquivo de entrada1. Caso a chave deste último seja menor do que a chave recém-gravada,

considerá-lo "congelado" e ignorá-lo no restante do processamento5. Caso existam em memória registros não "congelados" voltar ao passo

dois6. Caso contrário, fechar a partição de saída, "descongelar" os registros

"congelados", abrir nova partição de saída e voltar ao passo doisEm média, o tamanho das partições obtidas pelo processo de seleção com substituição é de 2 * MAX_MEMO

Seleção Natural

18

Seleção Natural

Desvantagem da seleção com substituição - no final da partição grande parte do espaço em memória principal está ocupado com registros “congelados” Na seleção natural, reserva-se um espaço de memória secundária ("o reservatório") para abrigar os registros "congelados" num processo de substituiçãoA formação de uma partição se encerra quando o reservatório estiver cheio ou quando terminarem os registros de entradaPara a memória comportando MAX_MEMO registros supõe-se um reservatório comportando max_reserv registrosPara MAX_MEMO= max_reserv o comprimento médio das partições é de MAX_MEMO * e, onde e = 2,718... .

19

Comparação dos Processos

A classificação interna gera as menores partições mas simplifica o estágio de intercalação por usar partições de mesmo comprimentoOs processos de seleção exigem intercalação mais elaborada, porém, gerando partições maiores, reduzem o tempo total de processamentoA seleção natural sofre o ônus adicional de utilizar mais operações de entrada e saída

20

Exemplo

Considere-se ser necessário classificar um arquivo cujas chaves de registros estejam representadas a seguirSuponha-se a possibilidade de manter na memória, simultaneamente, 6 registrosPede-se exibir as partições que seriam obtidas utilizando cada um dos métodos de geração de partições

21

Chaves dos registros a classificar

22

Partições obtidas por classificação interna

23

Partições obtidas por seleção com substituição

24

Partições obtidas por classificação seleção natural

Intercalação das Partições Classificadas

26

GeneralidadesConsiste na transformação de um conjunto de seqüências de registros, classificadas por determinado critério, em uma única seqüência contendo todos os registros de todas as seqüências originais do conjunto, sendo esta seqüência única classificada pelo mesmo critério de classificação das seqüências iniciaisConsidere-se a existência de R partições geradas pelo processo de geração de partiçõesSeria ideal poder intercalar todas as partições de uma só vez e obter o arquivo classificado Contudo, os Sistemas Operacionais estabelecem número máximo de

arquivos abertos simultaneamente, número esse que pode ser bem menor do que o número de partições existentes

A intercalação vai exigir uma série de fases durante cada qual registros são lidos de um conjunto de arquivos e gravados em outro (partições)

27

Estágio de Intercalação

Estratégias de distribuição e intercalação: 1. Intercalação balanceada de N caminhos. 2. Intercalação ótima. 3. Intercalação polifásica.

28

Medida de Eficiência

Uma medida de eficiência de estágio de intercalação é dada pelo número de passos sobre os dados, assim definido:

O número de passos é o número médio de vezes que um registro é lido (ou gravado) durante o estágio de intercalação.

Numero de passosNumero total de registros lidos

Numero total de registros no arquivo classficado

Intercalação balanceada de N caminhos

30

Intercalação Balanceada de n caminhos (1)

Arquivos disponíveis são distribuídos, tão equilibradamente quanto possível, em dois conjuntosPartições inicias são distribuídas, tão equilibradamente quanto possível nos arquivos de um dos conjuntosDurante cada fase da intercalação são lidos registros dos arquivos no conjunto que recebeu as partições iniciais (conjunto de entrada) e o resultado das intercalações é gravado nos arquivos do conjunto de saída, ciclicamente

31


No final de cada fase, o conjunto de entrada torna-se o conjunto de saída e vice-versaO balanceamento do processo baseia-se em colocar nos arquivos de entrada aproximadamente o mesmo número de registrosConsiderando-se F possíveis arquivos abertos, um dos conjuntos conterá os arquivos numerados de 1 a N e o outro conterá os arquivos numerados de N+1 até FDefine -se uma variável conjunto_inicial_de_entrada para identificar qual é o conjunto de entrada em cada fase

32


A intercalação termina quando, em uma fase, grava-se apenas uma partição. O número de passos é igual ao número de fasesA intercalação utiliza no máximo F/2 caminhos, quando o ideal seria F-1 caminhosPode ocorrer que partições sejam copiadas de um arquivo para outro sem qualquer processamento

33

Exemplo – Intercalação Balanceada (1)

Considere-se a existência de 20 partições classificadas cada qual com 100 registros a intercalarSupõe-se ser possível manter abertos simultaneamente 4 arquivosA notação i x j significa i partições de j registros cada

34

Exemplo – Intercalação Balanceada (2)

Intercalação Ótima

36

Intercalação Ótima

Partições iniciais gravadas em arquivos, cada qual com uma única partição Durante cada fase do algoritmo, as F-1 menores partições são intercaladas e gravadas em uma partição ou arquivo de saídaDo conjunto inicial de partições removem-se as partições intercaladas e a ele agrega-se a partição gerada na intercalaçãoTermina quando este conjunto tiver apenas uma partição.Cada partição de conter seu número de registros, ou o Sistema Operacional deve determinar o tamanho dos arquivos para verificar quais deles devem ser intercalados em cada momento (os F-1 menores)

37

Exemplo – Intercalação Ótima (1)

Considere-se a existência de 20 partições classificadas cada qual com 100 registros a intercalarSupõe-se ser possível manter abertos simultaneamente 4 arquivosSerá utilizada a notação x:y significando a partição de número x contendo y registros

38

Exemplo – Intercalação Ótima (2)

15,320006300

passosdeNúmero

Intercalação Polifásica

40

Intercalação Polifásica (1)

Para eliminar as cópias de partições sem que elas sejam intercaladas pode-se fazer sempre intercalações de ordem F-1A Intercalação polifásica opera desta maneira, 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

41


Considere-se a notação i x j representando i partições e j registrosEm cada fase do algoritmo intercalam-se F-1 arquivos até chegar ao final de qualquer uma delasNesse ponto, interrompe-se a fase deixando o restante dos arquivos para a fase seguinte

42

Exemplo inicial de Intercalação Polifásica

Considere-se , por exemplo, a intercalação de 31 partições com F = 4

Nú merode passos 107003100 3 45,

43


A intercalação polifásica para ser otimizada necessita de uma distribuição consistente de partições iniciaisConsidere-se, por exemplo, F = 4 Na penúltima fase os 3 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çõesApós a intercalação são produzidos a partições, sendo a = min (a+b ; a+c ; a)

44


O comportamento ótimo do processo ocorre quando o número total de partições iniciais pertence a uma série de Fibonacci generalizada.

Para F = 4, os primeiros termos da série são: 1 , 1 , 1 , 3 , 5 , 9 , 17 , 31 , 57 , ... .

45

Caso particular e caso geral

A intercalação polifásica pode ocorrer em duas situações: Caso particular mais favorável quando o

número de partições classificadas a intercalar usando F arquivos pertence à Série de Fibonacci de ordem F

Caso geral quando o número de partições não pertence àquela série

46

Algoritmo do caso particular

A partir do valor de F, busca-se a configuração final (1, 1, 1, ..., 1, 0) e recupera-se as anteriores pelo esquema anteriormente exibido

a = min (a+b ; a+c ; a)

Para F = 4 o que se obtém é

47

Tabelas alvo e de vazios (1)

O algoritmo da distribuição das partições pelos F - 1 arquivos utiliza duas tabelas auxiliares, cada qual com F colunas e sempre com última coluna contendo o valor zero: Tabela de alvos indicando quantas partições serão

necessárias para completar uma fase de distribuição de partições entre os arquivos

Tabela de vazios indicando quantas partições poderão ser gravadas em cada arquivo para completar a fase de distribuição de partições corrente

48

Tabelas alvo e de vazios (2)Tabela de alvos A primeira linha, ou primeiro nível, da tabela de alvos de ordem 4 contém

1, 1, 1, 0 significando que, para ordem 4, se houver uma partição no arquivo 1, uma partição no arquivo 2 e uma partição no arquivo 3 a situação é ótima para a eficiência do método de intercalação polifásica

A soma dos elementos de cada linha pertence a uma série de Fibonacci de ordem F, sendo para o primeiro nível o termo de ordem F, para o segundo nível o termo de ordem F + 1 e assim sucessivamente

As tabelas alvo não são atualizadas nem consultadas diretamente durante o distribuição de partições

Tabela de vazios Para passar da tabela alvo de nível i para o nível i + 1 existe uma tabela de

diferenças ou tabela de vazios de nível i As tabelas de vazios são consultadas e atualizadas controlando a

distribuição de partições

49

Ordem de Intercalação Polifásica (1)

De uma maneira geral, supondo F = 4 o quarto arquivo seria reservado para obter o resultado das intercalações e a distribuição de

partições nos primeiro, segundo e terceiro arquivos seria a seguinte

50

Ordem de Intercalação Polifásica (2)

51

Caso Geral (1)

A melhor intercalação polifásica ocorre quando o número de partições pertence a uma série de Fibonacci.O algoritmo da distribuição das partições pelos F - 1 arquivos funciona em diversos níveis. No primeiro nível, distribuem-se partições buscando uma tabela

alvo cuja soma de linhas pertence a uma série de Fibonacci (termo de ordem F - 1)

No segundo nível a tabela alvo tem como soma da linha o termo da ordem F da mesma série e assim sucessivamente

Para passar da tabela alvo de nível i para o nível i + 1 existe uma tabela de diferenças ou tabela de vazios de nível i

52

Caso Geral (2)

A tabela de vazios é decrementada cada vez que se grava uma partição nos arquivos de entrada correspondentes.Quando uma linha ou nível da tabela de vazios só contém zeros é porque foi atingida a linha correspondente da tabela alvo e incrementa-se o nível da distribuição para o prosseguimento do processo.

53

Exemplo – Intercalação Polifásica (1)

Considere-se a notação i x j representando i partições e j registrosEm cada fase do algoritmo intercalam-se F-1 arquivos até chegar ao final de qualquer uma delasNesse ponto, interrompe-se a fase deixando o restante dos arquivos

54

Exemplo – Intercalação Polifásica (2)

Nú merode passos 107003100 3 45,

55

Outro Exemplo – Intercalação Polifásica (1)

Considere-se 20 partiçõesComo 20 não pertence à série de Fibonacci generalizada (1, 1, 1, 3, 5, 9, 17, 31, ...), acrescentam-se 11 partições vaziasSupõe-se ser possível manter abertos simultaneamente 4 arquivos

56


Número de leituras = (10 + 9 + 12 + 11 + 20 ) / 20 = 62 / 20 = 3,1

57


58

Intercalação Polifásica(Parte do algoritmo - distribuição)

vazios[ponteiro] vazios[ponteiro] - 1 /* Geração e distribuição das demais partições pelos arquivos de trabalho */ i i + 1 Abrir (arquivo = nome_do_array[i]) para leitura Enquanto ((i≠ número_de_partições) e (não EOF(ent))) /* Escolha do arquivo de gravação da partição corrente */

Se (vazios[ponteiro] < vazios[ponteiro +1]) então /* Esta condição significa que o número de vazios referente ao arquivo corrente

está menor do que o número de vazios de seu sucessor e que, portante as novas gravações de partições devam ocorrer em seu sucessor */ponteiro ponteiro+1 senãoSe (vazios[ponteiro] = 0) então /* Nesta situação não há mais vazios e deve-se mudar de alvo */nível nível+1 temp alvos[1] Para k variando de 1 até número_de_arquivos - 1 vazios[k] temp+ alvos[k+1] - alvos[k] alvos[k] temp + alvos[k+1] Fim do ParaFim do Se /* (vazios[ponteiro] = 0) */ponteiro 1 /* as gravações iniciam-se no primeiro arquivo */Fim do Se /* (vazios[ponteiro] < vazios[ponteiro +1]) */

59

Intercalação Polifásica(Parte do algoritmo - gravação)

/* Geração de uma partição e gravação em arq[ponteiro] */ chave(auxiliar) chave_válida Repetir Ler de (arquivo = nome_do_array[i])) auxiliar

Se (EOF(nome_do_array[i])) então

chave(auxiliar) HIGH_VALUE Fim do Se Gravar em (arquivo = arq[j]) auxiliar

até (chave(auxiliar) = HIGH_VALUE) Fechar (arquivo = nome_do_array[i]) vazios[ponteiro] vazios[ponteiro] - 1 i i + 1 Abrir (arquivo = nome_do_array[i]) para leitura Fim do Enquanto /* (i número_de_partições) e (não EOF(ent)) */ /* Fechamento dos arquivos que receberam as partições */

60

Intercalação Polifásica(Parte do algoritmo - intercalação)

/*intercalação*/ Enquanto (nível > 0)

Repetir * até EOF(arq[número_de_arquivos-1])) */ sem_vazios 0 Para i variando de 1 até número_de_arquivos - 1 Se (vazios[i]) = 0 então

sem_vazios sem_vazios +1 Fim do Se Fim do Para Se (sem_vazios = 0) então /* Todos os arquivos tem partições vazias */ Para i variando de 1 até número_de_arquivos-1 vazios[i] vazios[i] - 1 Fim do Para vazios[número_de_arquivos] vazios[número_de_arquivos] + 1 /* A saída ganha partição vazia */ senão /* Existem arquivos com partições prontas para intercalar */ Para i variando de 1 até número_de_arquivos-1 Se (vazios[i]) 0 então

vazios[i] vazios[i] - 1 Fim do Se Fim do Para Fim do Se

Documents

Classificação Externa