Performance - pesquisas mais rapidas

Top  Previous  Next

Pesquisa binária.

{

Este é interessante e aumenta EM MUITO a performance de uma pesquisa.

Imagine que tenha um arquivo contendo sequenciais de letras exemplo:

 

AAAAA

AAAAB

AAAAC

.

.

.

ZZZZZ

 

Este arquivo é ENORME, eu sei porque no Win2000 um sequencial deste

usado AAAAA...ZZZZC (com a 5ª casa indo somente de A..C) ficou em

1,3 milhões de linhas e com quase 10Mb!

 

Se quisermos pesquisar a linha onde está a string "XXXXX"?

Numa pesquisa sequencial isto levaria quase 10 segundos (PIII 700):

}

var

  I: Integer;

 

begin

  Lista.LoadFromFile('C:\LISTA.TXT');

  for I := 0 to Lista.Count-1 do

    if Pos( Edit.Text , Lista[I] ) > 0 then

    begin

      ShowMessage('ACHEI, mas levou quase 10 segundos');

      Break;

    end;

end;

 

E se eu te dissesse que consigo fazer a mesma pesquisa em 10 milisegundos?

Impossivel? não, basta usar uma metodologia interessante.

Como o arquivo esta indexado pelo campo de pesquisa podemos fazer o seguinte:

Pegue a string no meio do arquivo e compare com a que quer pesquisar:

se for maior limite a pequisa da metade do arquivo pra frente, se menor para trás.

repita o processo até que a string seja igual.

Desta maneira haverá apenas uma 15 comparacoes até chegar no resultado final.

Diferente do sequencial que compara TODOS! (1,3 milhões).

O código para fazer isso não é muito complicado quanto parece:

}

var

  I, Min, Max: Integer;

begin

  Min := 0;

  Max := Lista.Count-1;

 

  while True do

  begin

    I := ((Max - Min) div 2) + Min; // aqui tá o calculo magico

 

    if Lista[I] = Edit.Text then

    begin

      ShowMessage('ACHEI, rapidinho');

      Break;

    end;

 

    if Edit.Text > Lista[I] then

    begin

      Min := I;

      Continue;

    end;

 

    if Edit.Text < Lista[I] then Max := I;

  end

end;

 

 

com arquivos TEXTO funcinou legal. 

Eu testei com Tables, usado MoveBy

FICOU LENTO. cerca de 6x mais lento 

do que o LOCATE.

 

Depois comparei o LOCATE e o FINDKEY

ficaram iguais.

 

Se o usar o locate na tabela SEM INDICE demora uns 2 segundos 

(neste exemplo), mas indexado leva ZERO segundos.

O FindKey (que só funciona com indices) tambem levou ZERO segundos.

 

Well Done!

}