EDII15 [2012.1] Classificação Externa

Embed Size (px)

Text of EDII15 [2012.1] Classificação Externa

  • 1. Prof. Kenia Kodel

2. ExtratoOrganizao de Arquivos Arquivos Sequenciais Desordenados Arquivos Sequenciais Ordenados Fisicamente Arquivos Sequenciais Ordenados por Link Arquivos Diretos Mantidos por Dicionrio de Dados Arquivos Diretos Mantidos por Hashing Arquivos Sequenciais Indexados Recuperao de Chave Secundria Multilista Recuperao de Chave Secundria Arquivos Invertidos Recuperao de Chave Secundria rvores de Assinaturas Estruturas de Busca em Texto rvores B e B+ Classificao ExternaUFS - DComp - Prof. Kenia Kodel2 3. O que classificar?UFS - DComp - Prof. Kenia Kodel 3 4. Quando aplicar classificao?UFS - DComp - Prof. Kenia Kodel 4 5. O que classificao externa?UFS - DComp - Prof. Kenia Kodel 5 6. Classificao ExternaDenomina-se classificar oprocesso de ordenao dedados, segundo um ou maiscampos chaves declassificao.UFS - DComp - Prof. Kenia Kodel 6 7. Classificao ExternanioEsta operao til paraexibio dos dados de formamais amigvel para usurios decomputadores e/ou para tornaroutras tarefas mais eficientes.UFS - DComp - Prof. Kenia Kodel 7 8. Classificao ExternafQuando a classificao aplicada sobre dados residentesem memria principal, esta denominada classificao interna.Quando em memria auxiliar,classificao externa.UFS - DComp - Prof. Kenia Kodel 8 9. Por que distinguir classificao interna da externa?UFS - DComp - Prof. Kenia Kodel9 10. Classificao Externa As caractersticas do meio onde esto armazenados os dados a serem classificados afetam significativamente o processo de ordenao.UFS - DComp - Prof. Kenia Kodel 10 11. Classificao ExternaDois principais aspectos dos meios dearmazenamento exercem influnciasobre a classificao: (1) acapacidade de armazenamento e(2) velocidade de processamento. UFS - DComp - Prof. Kenia Kodel 11 12. Como efetuar classificao externa?UFS - DComp - Prof. Kenia Kodel 12 13. Para efetuar a classificao externa, deve-se transferir os dados para memria interna e aplicar mtodos de classificao interna?UFS - DComp - Prof. Kenia Kodel 13 14. Deve-se efetuar aclassificao externa,aplicando emmemria externa osmesmos mtodosaplicados em memriainterna?UFS - DComp - Prof. Kenia Kodel14 15. Quais so os mtodos de classificao interna?UFS - DComp - Prof. Kenia Kodel 15 16. Classificao Interna58 45 31 80 455458 45 31 80 455445 58 31 80 455431 45 58 80 455431 45 58 80 455431 45 45 58805431 45 45 545880 Classificao por InseroUFS - DComp - Prof. Kenia Kodel 16 17. Classificao Interna5845 31 80 45 544531 58 80 45 544531 58 45 54 804531 58 45 54 803145 58 45 543145 45 54 58 Classificao por Troca: Bolha UFS - DComp - Prof. Kenia Kodel 17 18. Classificao Interna 5845 31 80 45 54 3145 58 80 45 54 3145 5854 80 45 45584580 54 4558544580Classificao por Troca: QuicksortUFS - DComp - Prof. Kenia Kodel 18 19. Classificao Interna5845 31 80 45543145 58 80 45543145 58 80 45543145 45 80 58543145 45 54 58803145 45 5458803145 45 545880 Classificao por Seleo: Direta UFS - DComp - Prof. Kenia Kodel 19 20. Classificao Interna(1) Dados:23 57 46 35 10 90 90(2) Montagem do heap.(3) Seleo dos maiores3557elementos remoo da(s)raiz(es) do heap (ordenaodecrescente). 231046 Classificao por Seleo: HeapsortUFS - DComp - Prof. Kenia Kodel 20 21. Classificao Interna58 45 31 80 45 5445 58 31 80 45 5431 45 58 80 45 5431 45 45 54 58 80 Merging TotalUFS - DComp - Prof. Kenia Kodel 21 22. Classificao Interna58 45 31 80 45 5445 58 31 45 54 8031 45 45 54 58 80Merging NaturalUFS - DComp - Prof. Kenia Kodel 22 23. Classificao Interna 58 4531 8045 54 * 31 4558 4554 80 31 4545 5458 80 Merging Parcial UFS - DComp - Prof. Kenia Kodel 23 24. RETOMANDO A QUESTO: Comoefetuar classificao externa?Transferindo os dados para memriainterna e aplicando mtodos declassificao interna? Ou aplicandoos mtodos o de classificaointerna em memria secundria? UFS - DComp - Prof. Kenia Kodel24 25. Classificao Externa So itens importantes a considerar: custodeacessoadicionalparatransferncia de dados entre memrias; custos adicionais para (re)posicionamentodos dispositivos de leitura em memriasecundria; restries de acesso conforme o dispositivode armazenamento usado. UFS - DComp - Prof. Kenia Kodel 25 26. Classificao ExternaA soluo trivial do processo de classificaoexterna :1. transferir os dados para memria principal;2. aplicar mtodo de classificao interna de dados;3. transferir dados (ordenados) para memria secundria. UFS - DComp - Prof. Kenia Kodel 26 27. Classificao Externa Entretanto, a memria secundria, devido a sua capacidade de armazenamento, usada para manter grande quantidade de dados, os quais, muitas vezes, no cabem em memria principal. Surge ento o KeySort.UFS - DComp - Prof. Kenia Kodel 27 28. Classificao Externa Para aplicao do KeySort, deve-se: 1. transferir as chaves dos registros para amemria principal; 2. aplicar mtodo de ordenao interna; 3. gerar arquivo de dados a partir daschaves.UFS - DComp - Prof. Kenia Kodel 28 29. Classificao ExternaPara aplicao do KeySort:1. transferir as chaves dos registros para a memria principal;2. aplicar mtodo de ordenao interna; Que estrutura dedados usaria em3. gerar arquivo de dados amemria partir das chaves. principal?UFS - DComp - Prof. Kenia Kodel29 30. Classificao Externa Porm h situao em que tambm as chaves no cabem, num bloco nico, em memria principal. Ento: (1) as chaves so agrupadas em blocos; (2) os blocos so ordenados em memria principal e (3) os blocos ordenados so reunidos por merging. UFS - DComp - Prof. Kenia Kodel 30 31. Classificao ExternaPara classificao externa de dados a estratgia maisusada a estudada como Merge Parcial. Para tanto necessrio:1. Subdividir o arquivo a ser ordenado em blocos de tamanho da memria interna disponvel.2. Ordenar cada bloco em memria primria, usando mtodos de classificao interna, de preferncia os de menor custo.3. Intercalar os blocos ordenados criando blocos ordenados cada vez maiores at que todo o arquivo esteja ordenado.UFS - DComp - Prof. Kenia Kodel 31 32. Classificao ExternaDada base de dados:52 1523 28704514 84 23 62 36Considerando memria interna com capacidade para trsregistros: 521523 2870 45148423 62 36Aplicando mtodos de classificao interna:15 2352 28457014 23 84 36 62Aplicando merge:15 235228 457014 23 84 36 62 ...UFS - DComp - Prof. Kenia Kodel 32 33. Balanceada em Vrios Caminhos Tambm denominada em T-Vias. Dado o arquivo desordenado composto pelasseguintes chaves: 09 14 20 05 18 030112 0104 02 1506 12 17 22 30 28 31 42 36 07 Considerando que na memria interna disponvel h espao para trs registros; o arquivo particionado:09 14 2005 18 03 01 12 0104 02 1506 12 17 22 30 2831 42 3607 UFS - DComp - Prof. Kenia Kodel 33 34. Balanceada em Vrios Caminhos Ordenando os blocos em memria principal obtm-se : 09 14 20 03 05 18 01 01 12 02 04 15 06 12 17 22 28 30 31 36 42 07 A etapa seguinte consiste em intercalar os blocos compondo blocosmaiores. Para tanto o mtodo usa mltiplas unidades dearmazenamento. A medida que os blocos so ordenados, estes so armazenadosequitativamente em trs unidades de armazenamento(quantidade definida pela capacidade da memria principal). unidade 1 09 1420 0204 15 31 36 42 unidade 2 03 0518 0612 17 07 unidade 3 01 0112 2228 30 UFS - DComp - Prof. Kenia Kodel34 35. Balanceada em Vrios Caminhos Para distribuio equitativa dos blocos nas trs unidades: o 1, aps aordenao, armazenado na unidade 1, o 2 na unidade 2, o 3na 3, o 4 na unidade 1, o seguinte na unidade 2 e assimsucessivamente at que todos os blocos estejam alocados nas 3unidades. 1 2 3 arquivomemria desordenadounidadesprincipal unidade 1 091420 0204 15 31 36 42 unidade 2 03 05 18 0612 17 07 unidade 3 010112 2228 30UFS - DComp - Prof. Kenia Kodel35 36. Balanceada em Vrios Caminhos Os blocos ordenados so intercalados. Para tanto, o 1 registro de cada uma das 3 unidades transferido para memria interna, nesta o menor item M eleito e transferido para memria secundria. Em seguida o prximo registro da unidade de origem de M transferido para a memria interna.unidade 1 0914 20 02 04 15 31 36 42unidade 2 0305 18 06 12 17 07unidade 3 0101 12 22 28 30memriaprincipal 09 03 01 UFS - DComp - Prof. Kenia Kodel36 37. Balanceada em Vrios Caminhos So usadas outras 3 unidades e armazenadas nestas a intercalao de cada 3 blocos de registros (9 registros). A intercalao dos primeiros blocos na unidade 4, dos segundos na 5, e assim sucessivamente. Ao final deste as 3 primeiras unidades usadas esto livres (vagas).unidade 1 091420 020415 31 36 42unidade 2 030518 061217 07unidade 3 010112 222830unidade 4010103 050809 1214 20unidade 5020406 121517 2228 30unidade 60731 3642Se houvesse mais blocos? UFS - DComp - Prof. Kenia Kodel 37 38. Balanceada em Vrios CaminhosNum determinado passo do processo haver umbloco de registros em cada unidade e um grupode unidades vazias. Ento, para obteno doarquivo ordenado, basta efetuar a intercalaodestes blocos de registros usando uma dasunidades vazias como destino. unidade 4 01 010305 08 09 12 14 20 unidade 5 02 040612 15 17 22 28 30 unidade 6 07 313642Neste caso a unidade 1 poderia ser usada comodestino da intercalao, e comportaria o arquivototal ordenado (final de processo). UFS - DComp - Prof. Kenia Kodel 38 39. Intercalao Polifsica Corresponde a uma variante do mtodo de intercalao balanceada em T-Vias; onde os blocos so distribudos entre unidades de forma desigual e somente uma fita reservada para armazenar os blocos resultantes das intercalaes. Neste, a cada passo, uma fita deve esvaziar-se. Considerando a mesma base 09 14 2005 18 03 01 12 01 de dados inicial: 04 02 1506 12 17 22 30 2831 42 3607UFS - DComp - Prof. Kenia Kodel39 40. Intercalao Polifsica Diferente da intercalao em T-Vias, neste no se usa 2n unidades onde n a capacidade da memria principal. Neste se usa o nmero de unidades disponveis.unidade 1 09 14 20 03 05 1801 01 12 02 04 15 06 12 17unidade 2 22 28 3031 364007unidade 3 UFS - DComp - Prof. Kenia Kodel40 41. Inte