Busca ( Search )

CAP-223

Busca (Search)Busca seqüencial

dados n elementos num array

Técnica mais simples para determinarse o array contém um dado elemento x.

for ( i = 1, n) do{

if ( A [ i ] == x ) return i;}return 0;

CAP-223

Busca (Search) - cont.

Busca binária

Se os dados num array seguem uma ordem(por exemplo ), i.e., k, 1 k<n: A[k] A[k+1]

A busca por um elemento x se torna maisrápida

Comparação do x com A[i] fornece maioresinformações

xA[i] exclui não só A[i] mas também todosos elementos de um dos lados do A[i]

CAP-223


u = 1; v = nwhile u v do{

m = qualquer valor u m vif x < A[m] then v = m - 1elseif x > A[m] then u = m + 1else return m

}return notfound

CAP-223


Hashing

faz uma referência direta aos registros numatabela realizando transformações aritméticasem endereços na tabela

se as chaves forem inteiros distintos de 1 a N,então pode-se armazenar o registro com chavei na posição i dentro da tabela

Hashing é uma generalização desta metodologiaquando não há conhecimento dos valores daschaves

CAP-223


Hashing é um bom exemplo de compromissoentre tempo e memória

Se não houvesse limitação de memória, pode-sefazer qualquer busca com somente um únicoacesso.

Se não houvesse limitação de tempo, pode-serealizar a busca seqüencial

Uso eficiente de memória disponível e acessorápido são principais fatores dos métodos hash

CAP-223


Endereçamento direto - elemento k éarmazenado na posição k

Com o hashing, o elemento k éarmazenado na posição h(k), onde h éuma função hash para determinar aposição a partir da chave k.

CAP-223


Primeiro passo numa busca utilizando hashingé calcular uma função de hash que transformaa chave de busca num endereço da tabela

Ideal seria chaves diferentes mapeando paraendereços diferentes - MAS NENHUMAFUNÇÃO HASH é perfeita

Processo de collision-resolution (resolução decolisão)

CAP-223

Busca (Search) - cont.O ideal é que uma boa função hash satisfaçahashing uniforme: cada chave tem a mesmaprobabilidade de ser alocada a qualquer umadas mm posições

Infelizmente isto nem sempre é possível. Nemsempre a distribuição é conhecida. Em muitoscasos as chaves podem NÃO ser geradasde uma forma independente.

CAP-223

Busca (Search) - cont.Informação qualitativa sobre a distribuição daschaves pode ser muito útil para criar umafunção hash

Como exemplo, considere tabela de símbolosde um compilador onde as chaves são “strings”que representam identificadores num programa.

Símbolos próximos como ptpt e ptspts ocorrem nummesmo programa. Uma boa função hash seriaminimizar a chance de que tais variações sejamalocadas para a mesma posição

CAP-223

Busca (Search) - cont.Uma boa política é derivar umo valor hash talque este valor é independente de quaisquerpadrões que possam existir nos dados

Um bom exemplo é o “método de divisão”O valor de hash é o resto quando a chave édividida por um número primo.

Algumas aplicações podem precisar de certaspropriedades específicas. Por exemplo,chaves “próximas” deveriam gerar valoreshash distantes.

CAP-223

Busca (Search) - cont.Maioria das funções hash supõe que o universodas chaves é um conjunto de números Naturais.Quando não é, teria que achar uma forma deinterpretar as chaves como números Naturais.

Método da divisão - h(k) = k mod m,mapear a chave kk em umas das mm posiçõesExemplo: k = 100 e m = 12 h(k) = 4

Evitar certos valores para m. m NÃO deveria serpotência de 2. Se m = 2p, então h(k) é apenasos p bits menos significativos de k. É melhoruma função que dependa de todos os bits de k.

CAP-223

Busca (Search) - cont.Um número primo que não seja muito próximoa uma potência exata de 2 é, em geral, uma boaopção para m.

Exemplo: n = 2000 e quando há insucesso, nãoteria importância de examinar uma média de3 elementos.m deveria ser 701, pois é umprimo próximo a 2000/3 e não é próximo anenhuma potência de 2.

h(k) = k mod 701

CAP-223


Função Hash - mod M, onde M é tamanhoda tabela

chave AKEY - 44217 80chave BARH 80

Uso da lista ligada para cada endereço ondea lista contém registros com aquele endereço

M listas

CAP-223

Busca (Search) - cont.M: 11chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-Ehash: 1 8 5 1 7 3 8 9 3 7 5 2 1 2 5 1 5

0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 A X C E G S I A M N E R H A E L PSeparate chaining (encadeamento separado)registros em colisão são “encadeados” emlistas ligadas

CAP-223

Busca (Search) - cont.Linear Probing

M (tamanho da tabela) > N registros

Examinar posição imediatamente apósa posição em colisão

comparar a chave com o registrose chaves forem iguais sucessose não há registro insucessosenão procure na posição seguinte

CAP-223

Busca (Search) - cont.M: 19chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-Ehash: 1 0 5 1 18 3 8 9 14 7 5 5 1 13 16 12 5

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

AS E

AA RC

HI

NGEE XX

CAP-223


Double Hashing

Sempre que houver um conflito (colisão),em vez de procurar a próxima posiçãovazia, é usada uma outra função hash cujovalor é somado ao valor da chave.

O processo trabalha com duas funções hash

CAP-223

Busca (Search) - cont.M: 19chave: A-S-E-A-R-C-H-I-N-G-E-X-A-M-P-L-Ehash1: 1 0 5 1 18 3 8 9 14 7 5 5 1 13 16 12 5

hash2: 7 3 3 7 6 5 8 7 2 1 3 8 7 3 8 4 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

AS E

AA RC HH

ING EE

XX

CAP-223


•Radix Searching»Radix Search Tries»Multiway Radix Searching»Patricia (Practical Algorithm To Retrieve Information Coded in Alphanumeric)

•External Searching

»Indexed Sequential Access»B-Trees»Extendible Hashing

CAP-223

Classificação (Sorting)

Ordenar (classificar) arquivos de registroscontendo chavesOrdenação interna - arquivo a ser ordenado cabe na memória

Ordenação externa - arquivos em disco

registros são fáceis de acessar

acesso seqüencial ou em blocos grandes

CAP-223

Classificação (Sorting) - cont.

Selection sort

• ache o menor elemento e troca-o com o elemento que está na primeira posição• ache o segundo menor elemento e troca-o com o que está na segunda posição• continue com este processo até que a lista está totalmente classificada

“seleciona” o menor elemento que restou

CAP-223


for i := 1 to N - 1 do {min := i;for j := i + 1 to N do {

if a [ j ] < a [ min ] then min := j;}t := a [ min ];a [ min ] := a [ i ];a [ i ] := t;

}

CAP-223

Classificação (Sorting) - cont.Insertion sort

Mais flexível do que Selection Sort

Elemento sendo considerado é inserido movendoelementos maiores uma posição a direita

for i := 2 to N do {v := a [ i ]; j := i;while a [ j - 1 ] > v do {

a [ j ] := a [ j - 1 ];j--;

}a [ j ] := v;

}

CAP-223

Classificação (Sorting) - cont.Bubble sort

Passe pelos elementos trocando elementosadjacentes. Em algum momento quando nãofoi efetuada nenhuma troca, a lista está classificada

for i := N to 1 do {for j := 2 to i do {

if a [ j - 1 ] > a [ j ] then {t := a [ j - 1 ];a [ j - 1 ] := a [ j ];a [ j ] := t;

}}

{

CAP-223


Shell sort

•h é um número escolhido•os elementos com distância-h são classificados•h vai sendo decrementado até 1 (seqüências ...)•nesta fase não há necessidade mover elementos a uma distância grande

h = ..., 1093, 364, 121, 40, 13, 4, 1

CAP-223

Classificação (Sorting) - cont.h := 1; repeat h := 3*h + 1 until h > N;repeat

h := h div 3;for i := h + 1 to N do {

v := a [ i ]; j := i;while a [ j - h ] > v do {

a [ j ] := a [ j - h ];j := j - h;if j <= h then {

a [ j ] := v;break;

}}

}until h = 1;

CAP-223


25 - 57 - 48 - 37 - 12 - 92 - 86 - 33seqüência (h) é (5, 3, 1)

25 - 57 - 48 - 37 - 12 - 92 - 86 - 33h = 5

25 - 57 - 33 - 37 - 12 - 92 - 86 - 48

25 - 12 - 33 - 37 - 48 - 92 - 86 - 57...

h = 3

CAP-223

Classificação (Sorting) - cont.Radix sort

• propriedades “digitais”• comparam e processam pedaços de chaves• sistema base M

Exemplo: radix 4 (cada dígito entre 0 e 3) e no máximo 3 dígitos

301 - 023 - 230 - 322 - 100 - 321 - 213

Dígito mais à direita - classificaDígito central - classificaDígito mais à esquerda - classifica

CAP-223

Classificação (Sorting) - cont.Mergesort

•Arquivos grandes com inserções regulares de novos elementos•Organizar novos registros em lote e inserir este lote no “arquivão”

i := j := 1;for k := 1 to M + N do {

if a [ i ] < b [ j ] then {c [ k ] := a [ i ]; i++;

}else {

c [ k ] := b [ j ]; j++;}

}

CAP-223


Variações de Mergesort

•List Merge sort

•Bottom-up Merge sort

CAP-223


Quicksort

C. A. R. Hoare (1960)Muito usado e muito popularFácil de implementarFunciona em uma variedade de situaçõesConsumo de poucos recursosOperações cerca de N log N

Problemas: implementação recursiva pior caso N2 operações frágil: pequeno erro na implementação pode afetar no desempenho

CAP-223


Algoritmo utiliza princípio de divide-and-conquer divide - particiona em:

elementos menores à esquerda elementos maiores à direita

conquer - classifica as duas partes em separado

Problema de Partição achar um limite m tal que elementos menores à esquerda são m e elementos maiores à direita são m

CAP-223


Particiona um subarray a [ left .. right ]e ordena de esquerda para direitaincrementando i e “ao mesmo tempo”ordena da direita para esquerdadecrementando j

CAP-223


Sugestões para partição

a [ ( left+right )div 2 ] elemento escolhido aleatoriamente mediana de três ou cinco elementos do array a partir de posições fixas ou aleatórias média entre menor e maior elemento (?)

CAP-223

Classificação (Sorting) - cont.quicksort ( left, right ) {

partition ( i, j, left, right );if left < j then quicksort ( left, j );if i < right then quicksort ( i, right );

}

partition ( i, j, left, right ) {m := guessmedian ( left, right );i := left; j := right;repeat

while a [ i ] < m do i++;while m < a [ j ] do j--;if i j then { a [ i ] := a [ j ]; i++; j--; }

until i > j;}

Documents

Busca ( Search )