EDII15 [2012.1] Classificação Externa

Prof. Kenia Kodel

Organização de Arquivos

Arquivos Sequenciais Desordenados

Arquivos Sequenciais Ordenados Fisicamente

Arquivos Sequenciais Ordenados por Link

Arquivos Diretos Mantidos por Dicionário de Dados

Arquivos Diretos Mantidos por Hashing

Arquivos Sequenciais Indexados

Recuperação de Chave Secundária – Multilista

Recuperação de Chave Secundária – Arquivos Invertidos

Recuperação de Chave Secundária – Árvores de Assinaturas

Estruturas de Busca em Texto

Árvores B e B+

Classificação Externa

Extrato

UFS - DComp - Prof. Kenia Kodel 2

O que é

classificar?


Quando

aplicar

classificação?


O que é

classificação

externa?


Classificação Externa Denomina-se classificar o

processo de ordenação de

dados, segundo um ou mais

campos – chaves de

classificação.


Classificação Externanição

Esta operação é útil para

exibição dos dados de forma

mais amigável para usuários de

computadores e/ou para tornar

outras tarefas mais eficientes.


Classificação Externaf

Quando a classificação é

aplicada sobre dados residentes

em memória principal, esta é

denominada classificação interna.

Quando em memória auxiliar,

classificação externa.


Por que distinguir

classificação interna

da externa?


As características do meio onde estão

armazenados os dados a serem

classificados afetam

significativamente o processo de

ordenação.



Dois principais aspectos dos meios de

armazenamento exercem influência

sobre a classificação: (1) a

capacidade de armazenamento e

(2) velocidade de processamento.



Como efetuar

classificação

externa?


Para efetuar a

classificação externa,

deve-se transferir os

dados para memória

interna e aplicar

métodos de

classificação interna?


Deve-se efetuar a

classificação externa,

aplicando em

memória externa os

mesmos métodos

aplicados em memória

interna?


Quais são os

métodos de

classificação

interna?


58 45 31 80 45 54

58 45 31 80 45 54

45 58 31 80 45 54

31 45 58 80 45 54

31 45 58 80 45 54

31 45 45 58 80 54

31 45 45 54 58 80

Classificação por Inserção


Classificação Interna

58 45 31 80 45 54

45 31 58 80 45 54

45 31 58 45 54 80

45 31 58 45 54 80

31 45 58 45 54

31 45 45 54 58

Classificação por Troca: Bolha



58 45 31 80 45 54 ≥ ≤

31 45 58 80 45 54 ≤ ≥

31 45 58 80 45 54 ≥ ≤

45 58 54 45 80

≤ ≥

45 58 54 45 80

Classificação por Troca: Quicksort



58 45 31 80 45 54

31 45 58 80 45 54

31 45 58 80 45 54

31 45 45 80 58 54

31 45 45 54 58 80

31 45 45 54 58 80

31 45 45 54 58 80

Classificação por Seleção: Direta



90

35 57

23 10 46

(1) Dados:

23 – 57 – 46 – 35 – 10 – 90

(2) Montagem do heap.

(3) Seleção dos maiores elementos – remoção da(s) raiz(es) do heap (ordenação decrescente).

Classificação por Seleção: Heapsort



58 45 31 80 45 54

45 58 31 80 45 54

31 45 58 80 45 54

31 45 45 54 58 80

Merging Total



58 45 31 80 45 54

45 58 31 45 54 80

31 45 45 54 58 80

Merging Natural



58 45 31 80 45 54

* 31 45 58 45 54 80

31 45 45 54 58 80

Merging Parcial



RETOMANDO A QUESTÃO: Como

efetuar classificação externa?

Transferindo os dados para memória

interna e aplicando métodos de

classificação interna? Ou aplicando

os métodos o de classificação

interna em memória secundária?


São itens importantes a considerar:

custo de acesso adicional para

transferência de dados entre memórias;

custos adicionais para (re)posicionamento

dos dispositivos de leitura em memória

secundária;

restrições de acesso conforme o dispositivo

de armazenamento usado.



A solução trivial do processo de classificação

externa é:

1. transferir os dados para memória principal;

2. aplicar método de classificação interna de

dados;

3. transferir dados (ordenados) para memória

secundária.



Entretanto, a memória secundária, devido a

sua capacidade de armazenamento, é

usada para manter grande quantidade de

dados, os quais, muitas vezes, não cabem em

memória principal. Surge então o KeySort.



Para aplicação do KeySort, deve-se:

1. transferir as chaves dos registros para a

memória principal;

2. aplicar método de ordenação interna;

3. gerar arquivo de dados a partir das

chaves.



Para aplicação do KeySort:

1. transferir as chaves dos

registros para a memória

principal;

2. aplicar método de

ordenação interna;

3. gerar arquivo de dados a

partir das chaves.



Que estrutura de

dados usaria em

memória

principal?

Porém há situação em que também as

chaves não cabem, num bloco único, em

memória principal. Então: (1) as chaves

são agrupadas em blocos; (2) os blocos

são ordenados em memória principal e

(3) os blocos ordenados são reunidos por

merging.



Para classificação externa de dados a estratégia mais

usada é a estudada como Merge Parcial. Para tanto

é necessário:

1. Subdividir o arquivo a ser ordenado em blocos de

tamanho da memória interna disponível.

2. Ordenar cada bloco em memória primária,

usando métodos de classificação interna, de

preferência os de menor custo.

3. Intercalar os blocos ordenados criando blocos

ordenados cada vez maiores até que todo o

arquivo esteja ordenado.



Dada base de dados:

52 15 23 28 70 45 14 84 23 62 36

Considerando memória interna com capacidade para três registros:

52 15 23 28 70 45 14 84 23 62 36

Aplicando métodos de classificação interna:

15 23 52 28 45 70 14 23 84 36 62

Aplicando merge:

15 23 52 28 45 70 14 23 84 36 62

... UFS - DComp - Prof. Kenia Kodel 32


Também denominada em T-Vias.

Dado o arquivo desordenado composto pelas

seguintes chaves:

09 14 20 05 18 03 01 12 01 04 02 15 06 12 17 22 30 28 31 42 36 07

Considerando que na memória interna disponível há

espaço para três registros; o arquivo é particionado:

09 14 20 05 18 03 01 12 01

04 02 15 06 12 17 22 30 28

31 42 36 07


Balanceada em Vários Caminhos

Ordenando os blocos em memória principal obtém-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 blocos maiores. Para tanto o método usa múltiplas unidades de armazenamento.

A medida que os blocos são ordenados, estes são armazenados equitativamente em três unidades de armazenamento (quantidade definida pela capacidade da memória principal).

unidade 1 09 14 20 02 04 15 31 36 42

unidade 2 03 05 18 06 12 17 07

unidade 3 01 01 12 22 28 30



Para distribuição equitativa dos blocos nas três unidades: o 1º, após a ordenação, é armazenado na unidade 1, o 2º na unidade 2, o 3º na 3, o 4º na unidade 1, o seguinte na unidade 2 e assim sucessivamente até que todos os blocos estejam alocados nas 3 unidades.

unidade 1 09 14 20 02 04 15 31 36 42

unidade 2 03 05 18 06 12 17 07

unidade 3 01 01 12 22 28 30

1

2

3

arquivo

desordenado memória

principal unidades



Os blocos ordenados são intercalados. Para tanto, o 1º registro

de cada uma das 3 unidades é transferido para memória

interna, nesta o menor item M é eleito e transferido para

memória secundária. Em seguida o próximo registro da

unidade de origem de M é transferido para a memória

interna.

unidade 1 09 14 20 02 04 15 31 36 42

unidade 2 03 05 18 06 12 17 07

unidade 3 01 01 12 22 28 30

memória principal 09 03 01



São usadas outras 3 unidades e armazenadas nestas a intercalação de cada 3 blocos de registros (9 registros). A intercalação dos primeiros blocos na unidade 4, dos segundos na 5, e assim sucessivamente. Ao final deste as 3 primeiras unidades usadas estão livres (vagas).

unidade 1 09 14 20 02 04 15 31 36 42

unidade 2 03 05 18 06 12 17 07

unidade 3 01 01 12 22 28 30

unidade 4 01 01 03 05 08 09 12 14 20

unidade 5 02 04 06 12 15 17 22 28 30

unidade 6 07 31 36 42

Se houvesse mais blocos?



Num determinado passo do processo haverá um bloco de registros em cada unidade e um grupo de unidades vazias. Então, para obtenção do arquivo ordenado, basta efetuar a intercalação destes blocos de registros usando uma das unidades vazias como destino.

unidade 4 01 01 03 05 08 09 12 14 20

unidade 5 02 04 06 12 15 17 22 28 30

unidade 6 07 31 36 42

Neste caso a unidade 1 poderia ser usada como destino da intercalação, e comportaria o arquivo total ordenado (final de processo).



Corresponde a uma variante do método de intercalação balanceada em T-Vias; onde os blocos são distribuídos entre unidades de forma desigual e somente uma fita é reservada para armazenar os blocos resultantes das intercalações. Neste, a cada passo, uma fita deve esvaziar-se.

Considerando

a mesma base

de dados inicial:

09 14 20 05 18 03 01 12 01

04 02 15 06 12 17 22 30 28

31 42 36 07


Intercalação Polifásica

Diferente da intercalação em T-Vias, neste não se usa 2n unidades onde n é a capacidade da memória principal.

Neste se usa o número de unidades disponíveis.

unidade 1 09 14 20 03 05 18 01 01 12 02 04 15 06 12 17

unidade 2 22 28 30 31 36 40 07

unidade 3



Efetuando a primeira intercalação:

unidade 1 09 14 20 03 05 18 01 01 12 02 04 15 06 12 17

unidade 2 22 28 30 31 36 40 07

unidade 3

unidade 1 02 04 15 06 12 17

unidade 2

unidade 3 09 14 20 22 28 30 03 05 18 31 36 40 01 01 07 12

Obtém-se:



Efetuando a segunda intercalação:

unidade 1 02 04 15 06 12 17

unidade 2

unidade 3 09 14 20 22 28 30 03 05 18 31 36 40 01 01 07 12

Obtém-se:

unidade 1

unidade 2 02 04 09 14 15 20 22 28 30 03 05 06 12 17 18 31 36 40

unidade 3 01 01 07 12

Na próxima intercalação o arquivo original estará ordenado?



Na intercalação seguinte o arquivo ordenado é obtido e mantido na unidade 3.

unidade 1 01 01 01 07 09 12 14 15 20 22 28 30

unidade 2 03 05 06 12 17 18 31 36 40

unidade 3

O Merging Polifásico aposta na distribuição perfeita das corridas nas vias; de forma a obter, a cada passo, uma via vazia que servirá como saída.



Considerando uma distribuição de 129 corridas (blocos de registros) em 6 vias.

unidades

quantidade de

itens por unidades,

a cada passo


8


Trata-se de uma variante do Merging

Polifásico. Enquanto na Polifásica a cada

passo (T-1) são intercaladas (1 é usada

como destino). Na cascata a cada passo

as corridas de (T-1) vias são intercaladas;

em seguida (T-2), (T-3) e assim por diante.


Intercalação em Cascata

Desta forma aposta-se em melhor performance que o

Polifásico, em função deste decréscimo do número de vias

intercaladas a cada passo. Considerando uma distribuição de 190 corridas (blocos de registros) em 6 vias.

T1 T2 T3 T4 T5 T6 unidades

1 55 50 41 29 15 -

quantidade

de itens

por via, a

cada passo.

2 40 35 26 14 - 15

3 26 21 12 - 14

4 14 9 - 12

5 5 - 9

6 - 5

O processo segue com: 15 -14 – 12 – 9 – 5 distribuído em 5 unidades (vias).


Intercalação em Cascata

Considerando: (1) a mesma base de dados

trabalhada em aula e (2) memória

principal com capacidade para 4

registros. Apresentar, passo a passo, a

ordenação desta usando:

(a) Intercalação balanceada em T-Vias

(b) Intercalação polifásica

Exercício


Complementar Estudos...

File Organization and Processing

Allan L Tharp

Capítulo 13

S o r t i n g External Sorting


49 UFS - DCOMP - Prof. Kenia Kodel

(Avaliações)

Próximos passos...

UFS - DCOMP - Prof. Kenia Kodel 49 UFS - DComp - Prof. Kenia Kodel 49

EDII15 [2012.1] Classificação Externa

Text of EDII15 [2012.1] Classificação Externa

Catálogo Hadassa 2012.1

Prova 2012.1

Remuneração versão 2012.1

Apostila prática TM 2012.1

2012.1 semana 11_-_defeitos_do_neg_cio_jur_dico_ii

QUADRO LG 2012.1

UECE 2012.1 Resultado

Classificação Externa

OXIGENOTERAPIA 2012.1

prova cederj vestibular 2012.1

PROAB 2012.1 DIREITO DO TRABALHO – AULA 12 PROAB 2012.1 DIREITO DO TRABALHO PROFESSORA: MARIA INÊS GERARDO Aula 12 PROAB 2012.1 DIREITO DO TRABALHO PROFESSORA:

Escabiose 2012.1

AVALIAÇÃO EXTERNA DO DESEMPENHO DOCENTEc7%c3O%20vers%e... · AVALIAÇÃO EXTERNA DO DESEMPENHO DOCENTE CLASSIFICAÇÃO DGAE DIREÇÃO-GERAL DA ADMINISTRAÇÃO ESCOLAR. ... Reconhecer

PROAB 2012.1 DIREITO CONSTITUCIONAL – AULA 12 PROAB 2012.1 DIREITO CONSTITUCIONAL PROFESSORA: CIBELE FERNANDES DIAS Aula 12 PROAB 2012.1 DIREITO CONSTITUCIONAL

13. AVALIACAO PSICOLOGICA (2012.1)

PROAB 2012.1 DIREITO CONSTITUCIONAL – AULA 1 PROAB 2012.1 DIREITO CONSTITUCIONAL PROFESSORA: CIBELE FERNANDES Aula 1 PROAB 2012.1 DIREITO CONSTITUCIONAL

1 AVALIAÇÃO EXTERNA DO DESEMPENHO DOCENTE DIMENSÃO CIENTÍFICA E PEDAGÓGICA Avaliação e Classificação Avaliação e Classificação AVALIAÇÃO EXTERNA DO DESEMPENHO

PROAB 2012.1 DIREITO CONSTITUCIONAL – AULA 2 PROAB 2012.1 DIREITO CONSTITUCIONAL PROFESSORA: CIBELE FERNANDES Aula 1 PROAB 2012.1 DIREITO CONSTITUCIONAL

Prova Unifor 2012.1

Demodicidose 2012.1

2005 a 2012.1

2012.1 semana 13_-_prescri_o_e_decad_ncia

Metodologia aula 3 2012.1

PROAB 2012.1 DIREITO PROCESSUAL PENAL – AULA 02 PROAB 2012.1 DIREITO PROCESSUAL PENAL PROFESSORA: BEATRIZ ABRAÃO Aula 2 PROAB 2012.1

PROAB 2012.1 DIREITO EMPRESARIAL – AULA 6 PROAB 2012.1 DIREITO EMPRESARIAL PROFESSORA: CÉLIO CELLI Aula 6 PROAB 2012.1 DIREITO EMPRESARIAL PROFESSORA:

PROAB 2012.1 DIREITO DO TRABALHO – AULA 9 PROAB 2012.1 DIREITO DO TRABALHO PROFESSORA: MARIA INÊS GERARDO Aula 9 PROAB 2012.1 DIREITO DO TRABALHO PROFESSORA:

Apresentação de bioquímica 2012.1

PROAB 2012.1 DIREITO CONSTITUCIONAL – AULA 13 PROAB 2012.1 DIREITO CONSTITUCIONAL PROFESSORA: CIBELE FERNANDES DIAS Aula 13 PROAB 2012.1 DIREITO CONSTITUCIONAL

PROAB 2012.1 DIREITO PROCESSUAL DO TRABALHO – AULA 2 PROAB 2012.1 DIREITO PROCESSUAL DO TRABALHO PROFESSORA: MARIA INÊS GERARDO Aula 2 PROAB 2012.1 DIREITO

EDITAL 038 Vestibular 2012.1

Education

EDII15 [2012.1] Classificação Externa

Text of EDII15 [2012.1] Classificação Externa