Pesquisa: Binaria X Sequencial

June 19, 2019

 

 

 

Quando estamos escrevendo algum código, é importante nos preocuparmos também, além do correto funcionamento da solução, com a performance de execução do mesmo, principalmente onde a carga de dados é maior. Umas das técnicas é o modo como as informações são processadas no código. No SAP, utilizando a linguagem ABAP, vamos exemplificar 2 métodos de busca, a pesquisa sequencial e a pesquisa binaria. Mas antes disso, falaremos sobre um pouco sobre cada uma delas.

 

A pesquisa sequencial, trata-se de uma busca, em uma tabela por exemplo, de forma que cada registro é testado individualmente até que o resultado esperado seja encontrado. Num exemplo prático, onde tenhamos uma tabela com 1000 registros e desejamos encontrar o que está na posição 997, precisaremos fazer 997 comparações para chegar ao resultado. Em média, nesse exemplo serão feitas 500 comparações.

 

A pesquisa binaria, por sua vez, parte do princípio que os registros estão ordenados. E é feita a divisão de blocos menores sucessivamente. Primeiramente é comparado o registro do meio da tabela. Fazendo a verificação se é o resultado correto, caso não seja, verifica se é maior que este, desconsiderando os anteriores. Caso o resultado esperado seja inferior a este, desconsidera os posteriores, e assim fará até encontrar o alvo desejado. A cada comparação, a tabela é reduzida pela metade. Seguindo a linha do exemplo anterior, primeiramente irá verificar o registro 500. Como 997 é maior que 500, irá desconsiderar os 500 registros anteriores. No passo seguinte, irá testar a posição 750, como ainda é maior, ficará apenas com os registros de 750 a 1000, e assim, o fará até encontrar o resultado esperado. Neste tipo de pesquisa, no exemplo utilizado, em média serão feitas 18 comparações para encontrar qualquer valor.

No ABAP, não precisamos nos preocupar com a teoria, desde que tenhamos entendido o conceito das duas opções, então, vejamos abaixo um exemplo.

 

Para efeito de comparação, os dados utilizados são os mesmos e os blocos de código da pesquisa binaria e pesquisa sequencial, são idênticos, salvo o comando ‘BINARY SEARCH’ na linha 33.

 

 

Explicando o código:

  • Das linhas 17 a 23, temos a busca das informações nas tabelas, através do comando SELECT.

  • Na linha 25, temos a ordenação da tabela, conforme os campos necessários na busca. Essencial para o funcionamento da pesquisa binaria.

  • Na linha 28, temos um LOOP na tabela LT_SBOOK, e dentro deste buscando o registro da tabela LT_SFLIGHT, através de um READ TABLE. Aqui utilizamos o BINARY SEARCH, para ser efetuada a pesquisa binaria.

  • Na linha 39, temos um LOOP idêntico ao anterior, e dentro, a mesma busca na LT_SFLIGHT, porém aqui não temos o BINARY SEARCH. Sempre que não houver esse código no READ TABLE será executada a pesquisa sequencial.

     

E o resultado disso?

 

Perceba que a diferença de tempo de uma pesquisa para outra é considerável. A pesquisa binaria levou 2 segundos, enquanto a sequencial levou 142 segundos. Assim podemos confirmar que a pesquisa binaria foi muito mais eficiente em comparação a pesquisa sequencial.

 

E para finalizar: “nunca mais devo utilizar pesquisa sequencial?” Prefira sempre a pesquisa binaria. Mas atente ao fato de que a tabela tem que estar obrigatoriamente ordenada. Caso não seja possível a ordenação da mesma, utilize a pesquisa sequencial.

 

 

Compartilhar
Twitter
Please reload