Alta Performance com Busca Binária

Um dos métodos mais comum de realizar uma busca em uma lista de opções, é procurar item a item, até encontrar a opção que corresponde à aquela que está sendo procurada. Essa metodologia de busca é conhecida como bubble search. Embora funcional, ela é horrível para a performance, porque faz com que cada elemento dentro do conjunto a ser procurado, precise ser testado, até que a opção correta seja encontrada. Assim, em uma lista de 100.000 opções por exemplo, caso a última opção seja a correta, todas as 100.000 opções precisam ser testadas.

Em uma implementação Delphi, isso geralmente está vinculado a um laço de repetição como “for” ou “while”:

 

Embora esse seja um caso necessário em alguns cenários, obviamente não é algo a ser desejado.

Quando os valores de uma lista possam ser ordenados de alguma forma, é possível criarmos alguns algorítmos otimizados para a busca desses valores. Existem diversos algorítmos recomendados para cada situação. Falaremos agora um pouco da busca binária.

Busca Binária

Binary Search
Mecanismo de uma busca binária

Quando pudermos ordenar uma lista de elementos, é possível utilizarmos a busca binária. Ela possui esse nome porque sempre que a condição do retorno é testada, ela descarta metade da lista em cada teste. Assim, ela considera que existam dois lados: o lado correto, e o lado errado (2 = BInário).

Vamos entender melhor.

Imaginemos um conjunto de números dispersos que vão de 1 a 100. A primeira coisa a ser feita, é ordenar esses números de alguma forma. No nosso exemplo, vamos ordená-los de forma crescente (1, 5, 7, 10…100). A ordenação é o passo mais importante, porque ela que cria a condição necessária para o funcionamento da busca binária.

Uma vez com a lista ordenada, vamos utilizar a seguinte lógica para buscarmos nossos valores. Sempre que formos procurar um valor, iremos sempre ao meio da lista de verificaremos se o valor do meio é o valor que procuramos. Se for, está finalizado. Caso não for, verificaremos, conforme a ordenação dada (no nosso caso, ordem crescente de números), se o número que procuramos está antes ou depois do meio. Caso esteja antes, sabemos que podemos descartar da busca a metade para frente. Caso esteja depois, sabemos que podemos descartar o início da lista até a metade. Agora, teremos apenas metade da lista para procurar novamente.

Esse trecho da metade da lista restante forma uma nova lista, menor, é verdade, mas a qual podemos aplicar a mesma lógica. Assim, para essa nova lista, resultado da lista anterior, aplicamos o mesmo princípio: vamos à metade dessa nova lista e verificamos se o valor do meio é o valor que procuramos. Se for, encontramos o elemento. Se não for, verificamos se o número que procuramos está antes ou depois do meio. Se estiver antes, a metade posterior é descartada. Se estiver depois, a metade anterior é descartada.

Essa lógica é aplicada continuamente  às novas “sublistas” até encontrarmos o resultado.

O interessante desse algorítmo é que, não importa o tamanho da lista, o valor será encontrado em até 8 etapas. Isso mesmo. Mesmo que a lista tenha 1.000.000 de elementos, em até 8 etapas, o resultado correto é retornado. Isso é fantástico quando falamos em desempenho, porque 8 etapas de processamento é muito pouco para qualquer computador processar e
retornar o valor correto.

Implementando uma busca binária

Podemos implementar uma busca binária em Delphi facilmente, utilizando o recurso da recursividade. Como teremos ao máximo 8 chamadas para o mesmo método, não haverá risco de estouro de pilha (stack overflow). Veja o código abaixo:

 

 

A primeira coisa a fazermos é checar se o valor a ser encontrado está é algum dos limites da lista. Se não for, encontramos o meio e verificamos se o elemento do meio é o elemento que procuramos. Se não for, verificamos se está para frente ou para trás da lista. Conforme o caso, chamamos novamente a função BuscaBinaria, mas alterando o “range” do valor inicial e valor final da lista. Essa é a forma de limitarmos as buscas para a metade anterior ou posterior da lista.

Lembrando que a chamada inicial da busca ocorre passando o valor inicial como o primeiro elemento da lista, e o valor
final como o último elemento da lista.

Em poucas linhas você tem uma excelente ferramenta de busca de alta performance.

Busca Binária nativa no Delphi

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TArray.BinarySearch

O Delphi possui uma ferramenta nativa para buscas binárias. Utilizando-se do método BinarySearch da classe TArray, é possível chegar ao mesmo resultado.

Veja o código abaixo:

 

A primeira coisa que fizemos aqui foi criar uma lista aleatória de 0 à MAX (ou 100.000). Depois definimos qual seria o valor a ser encontrado na lista. A variável “Indice” é alimentada pelo terceiro parâmetro do método, um parâmetro out que retorna o índice em que está o elemento (ou o índice mais próximo a ele). O último parâmetro do método é um método anônimo para a definição da ordenação da lista (lembra que a ordenação é muito importante para a busca binária?).

O método retorna “true” se encontrou o elemento ou “false” se ele não foi encontrado.

Muito simples não é?

Conclusão

A busca binária é uma execelente ferramenta para encontrar valores dentro de um conjunto que possa ser ordenado de alguma forma. O Delphi possui essa ferramenta implementada de forma nativa e bem flexível, pois implementa a
funcionalidade com o uso de genérics, dando a possibilidade de alterar o tipo e a metodologia de busca conforme o caso necessário. Todavia, ainda sim existem alguns casos mais complexos onde será necessário o desenvolvimento de uma busca binária própria para o problema em questão, então é importante conhecer o mecanismo de funcionamento dessa busca, para conseguir extrair o máximo de proveito de sua utilização.

Como é a Performance da RTTI?

Trabalhando em um determinado projeto, o primeiro caminho que tomei foi utilizar as funcionalidades da RTTI, porque realmente gosto como ela funciona. Todavia, deparei-me com a possibilidade de realizar a mesma coisa de uma forma mais simples, e sem a necessidade de nenhum processamento em runtime, visto que rodaria através do  código compilado. A primeira coisa que pensei foi: claro que vou alterar para a forma mais simples, mas qual seria o prejuízo na performance, se optasse pela RTTI? Isso foi algo que não consegui responder no primeiro momento.

Foi então que fiz um teste simples. Testaria as duas formas e mediria a performance, para saber o quanto a RTTI (por utilizar o processamento em runtime) prejudicaria a performance em rotinas diversas vezes executadas.

Segue a implementação do teste:

A diferença das duas formas de execução é obtenção do método e sua execução pela RTTI, ao contrário do cast diretamente para a interface e sua execução.

Veja que a utilização da RTTI, por sua própria natureza, utiliza muito mais código e muito mais processamento, porque o fluxo para obter o mesmo resultado é muito mais longo, embora muito mais flexível. Mas qual seria o resultado?

Realmente fiquei muito impressionado. Só pela leitura do código, imaginei que a RTTI fosse muito mais lento, mas não foi isso o que aconteceu. Ela deveras possui uma performance inferior, mas nada a se envergonhar.

  • Para 100.000 iterações, as duas rodaram em menos de 1 segundo.
  • Para 1.000.000 iterações,  pela interface foi menos de 1 segundo, enquanto pela RTTI durou próximo à 6 segundos.

A partir daí, o tempo de diferença aumenta exponencialmente, lógico.

Quero apenas chamar a atenção para o fato de que dificilmente rodamos rotinas mais de 100.000 vezes. Quando necessário, a melhor performance deve ser utilizada, mas acredito, embasado na evidência àcima, que na grande maioria dos casos, pode-se utilizar a RTTI sem prejuízo algum da performance, que seja sensível ao usuário.

Tem uma visão diferente? Comente abaixo e vamos aprender ainda mais juntos.

Diagnóstico de Performance com TStopWatch e TTimeSpan

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Diagnostics.TStopwatch

O Delphi possui uma função de diagnóstico muito últil para medir a performance do sistema. No momento de melhorar a performance de um trecho de código, geralmente o desenvolvedor faz algo como:

Isso basicamente pega a data antes da execução, pega a data depois da execução, e depois mostra a diferença dos tempos entre as datas.

Isso funciona na maioria dos casos.

Caso você precise de uma maior precisão na medida do tempo, você pode utilizar GetTickCount: https://reisthales.wordpress.com/2016/03/30/delphi-medindo-o-tempo-de-execucao-de-um-processo/

Contudo, o Delphi possui uma classe preparada para esse tipo de diagnóstico, chamada TStopWatch. Sua utilização segue abaixo:

Embora TStopWatch seja um record, ele precisa ser inicializado, seja pelo método Create, seja pelo método StartNew. Ambos criam e inicializam o StopWatch. A diferença é que Create cria com o contador de tempo parado, e StartNew já cria com o contador de tempo girando.

StopWatch.Start inicia a contagem do tempo e StopWatch.Stop para a contagem do tempo. Isso feito, você consegue obter os valores em:

StopWatch.ElapsedMilliseconds – Retorna o total de tempo em milesegundos.

System.Diagnostics.TStopwatch.ElapsedTicks – Retorna o total de tempo em milesegundos (também).

System.Diagnostics.TStopwatch.Elapsed – Retorna o total de tempo em formato TTimeSpan – o melhor a ser usado.

Existem ainda outras funcionalidades como StopWatch.Reset, que reinicia o contador do StopWatch.

TTimeSpan

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.TimeSpan.TTimeSpan

TTimeSpan é um record com funcionalidades específicas para tratamento de tempo. Assim que ele é retornado pelo método “Elapse”, você pode utilizar um de seus métodos:

Assim, você pode obter o retorno dessas informações facilmente em milesegundos, segundos, minutos, horas, dias, etc.

Pronto para melhor diagnosticar seu código?