O objetivo deste post é apresentar um meio eficiente de busca de objetos em memória.

O surgimento da sintaxe LINQ, assim como a utilização de query methods, facilitou a busca em memória. Com estes recursos podemos facilmente executar queries em arrays, coleções e listas de tipos genéricos. O uso deste modelo de sintaxe agiliza o processo de desenvolvimento por tornar a busca em memória trivial e de simples codificação.

Mas, ao adotarmos esse modelo de sintaxe, estamos realmente escrevendo código performático? Será que essas consultas em memória são o modelo mais rápido de pesquisa? Não estaríamos perdemos poder computacional ou tempo de processamento ao adotar estes recursos em determinados cenários de pesquisa em memória?

Dada a necessidade de executar consultas eficientes e com baixo custo computacional, passamos a evitar consultas que consumam muitos recursos computacionais e que sejam lentas.

A busca binária é um algoritmo de busca que segue o paradigma da divisão e conquista. Partindo do pressuposto de que o conjunto de elementos está ordenado, são executadas diversas divisões do espaço de busca restringindo o possível local no qual o elemento buscado está posicionado. A imagem a seguir ilustra o processo de divisão do conjunto de elementos realizado pela busca de elementos.

A busca binária possui complexidade algorítmica de Θ(log2 n), enquanto que os algoritmos de busca linear possuem complexidade algorítmica de Θ(n) – dado que n é o tamanho do conjunto de elementos.

Os algoritmos de busca linear são caracterizados pelo modelo sequencial de pesquisa, no qual a validação é feita elemento por elemento.

Vamos aos exemplos.

1 – Busca binária.

Este é o algoritmo de busca binária. Note que a sua execução depende da identificação de um ponto central no conjunto de elementos para que subconjuntos menores sejam criados. Vale ressaltar que este algoritmo é funcional apenas com elementos ordenados. Se os elementos não estiverem ordenados, então a busca binária não deve ser utilizada.

    static bool SearchUsingHandCodeWithDepthFirstSearch(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, 0, targetList.Count - 1);
    }
 
    static bool SearchUsingHandCodeWithDepthFirstSearch(IList<EstruturaHierarquica> targetList, string searchParameter, int start, int end) {
 
        if (start >= end)
            return false;
 
        int middlePoint = end - ((end - start) / 2);
 
        int compare = string.Compare(targetList[middlePoint].CodigoTipoRegistro, searchParameter);
            
        if (compare < 0) {
            return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, middlePoint, end);
        }
        else if (compare > 0) {
            return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, start, middlePoint - 1);
        }
        else {
            return true;
        }
    }

2 – Busca linear

A busca linear nada mais é do que a varredura sequencial de um conjunto de elementos. Seja essa varredura iniciada na posição 0, na posição N ou com dupla validação de extremidades, ela é realizada item a item, sem utilizar o paradigma da divisão e conquista, ou qualquer outra abordagem.

    static bool SearchUsingHandCodeWithStringCompare(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        foreach (var item in targetList) {
            if (string.Compare(item.CodigoTipoRegistro, searchParameter) == 0)
                return true;
        }
        return false;
    }
 
    static bool SearchUsingHandCodeWithStringEquals(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        foreach (var item in targetList) {
            if (string.Equals(item.CodigoTipoRegistro, searchParameter))
                return true;
        }
        return false;
    }
 
    static bool SearchUsingHandCodeWithStringEqualsCurrentCultureIgnoreCase(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        foreach (var item in targetList) {
            if (string.Equals(item.CodigoTipoRegistro, searchParameter, StringComparison.CurrentCultureIgnoreCase))
                return true;
        }
        return false;
    }
 
    static bool SearchUsingHandCodeWithStringCompareOrdinal(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        foreach (var item in targetList) {
            if (string.CompareOrdinal(item.CodigoTipoRegistro, searchParameter) == 0)
                return true;
        }
        return false;
    }
 
    static bool SearchUsingHandCode(IList<EstruturaHierarquica> targetList, string searchParameter) {
 
        foreach (var item in targetList) {
            if (item.CodigoTipoRegistro == searchParameter)
                return true;
        }
        return false;
    }
 
    static void PopulateList(IList<EstruturaHierarquica> targetList) {
 
        for (int i = 0; i < POPULATIONSIZE; i++) {
 
            EstruturaHierarquica newNode = new EstruturaHierarquica();
 
            newNode.CodigoTipoRegistro = string.Format(i.ToString().PadLeft(POPULATIONSIZE.ToString().Length, '0'));
 
            targetList.Add(newNode);
        }
    }

 

3 – Busca com LINQ

Estes últimos são os exemplos com queries LINQ. Eles são apresentados para que possamos identificar a diferença de tempo entre estas queries e as demais.

    static bool SearchUsingLinqAny(IList<EstruturaHierarquica> targetList, string searchParameter) {

        var query = targetList.Any(e => e.CodigoTipoRegistro == searchParameter);
        return query;
    }

    static bool SearchUsingLinqFirstOrDefault(IList<EstruturaHierarquica> targetList, string searchParameter) {

        var query = targetList.FirstOrDefault(e => e.CodigoTipoRegistro == searchParameter);
        return (query != null);
    }

Como os tempos serão medidos?

Para identificar o tempo expendido na execução de cada query, foi criada uma classe chamada TimeCollector. Está classe utiliza um Stopwatch internamente, coletando o início e o término da execução das queries.

    public class TimeCollector : IDisposable {
 
        private string _label;
        private Stopwatch _watch;
 
        public object Result { get; set; }
 
        public TimeCollector(string label) {
 
            this._label = label;                 
            this._watch = Stopwatch.StartNew();
        }
        
        public void Dispose() {
 
            this._watch.Stop();
 
            Console.WriteLine(":: {0} - Total: {1} / Result: {2}", this._label,
                                                                   this._watch.Elapsed.TotalMilliseconds,
                                                                   this.Result == null ? string.Empty : this.Result.ToString());
        }
    }

 

Testes de Performance

Para validar a performance dos algoritmos de busca utilizaremos uma lista com mil itens em memória. Esses itens estão ordenados e a mesma lista será utilizada por todos os exemplos.

Abaixo temos o resultado de três execuções:

– Primeira Execução

– Segunda Execução

– Terceira Execução

 

Com estas execuções podemos notar que:

– Os métodos de busca que utilizam LINQ possuem performance bastante próxima aos métodos de busca linear.

– O meio utilizado para comparação de strings pode ser tido como fator descriminante para uma execução mais rápida na busca linear.

– Em todos os casos a busca binaria mostrou mais rápida, chegando a ser 4 vezes, 8 vezes e até 10 vezes mais rápida que os demais métodos.

Existem outros métodos de busca em memória tão performáticos quanto a busca binária (i.e. busca em profundidade, busca em largura). Acredito que vale a pena estudar algoritmos de busca, pois são parte do nosso dia-a-dia e agregam mais performance a nossas aplicações.

Espero que a partir deste post sempre que for necessária a pesquisa em memória, seja feita uma análise do cenário e da disposição dos dados, para que assim o melhor algoritmo seja utilizado.

Abaixo o código do exemplo na integra.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleSearch {
    class Program {

        const int POPULATIONSIZE = 1000;
        const int RANDOM_SEED = 10;

        static void Main(string[] args) {

            IList<EstruturaHierarquica> list = new List<EstruturaHierarquica>();

            PopulateList(list);

            Random rnd = new Random(RANDOM_SEED);
            do {

                Console.Clear();
                string SEARCHPARAMETER = rnd.Next(0, list.Count).ToString().PadLeft(POPULATIONSIZE.ToString().Length, '0');

                Console.WriteLine("SEARCHPARAMETER {0}", SEARCHPARAMETER);

                Console.WriteLine("LINQ Methods");

                using (var timer = new TimeCollector("SearchUsingLinqAny")) {
                    timer.Result = SearchUsingLinqAny(list, SEARCHPARAMETER);
                }

                using (var timer = new TimeCollector("SearchUsingLinqFirstOrDefault")) {
                    timer.Result = SearchUsingLinqFirstOrDefault(list, SEARCHPARAMETER);
                }

                Console.WriteLine("Linear Search");

                using (var timer = new TimeCollector("SearchUsingHandCode")) {
                    timer.Result = SearchUsingHandCode(list, SEARCHPARAMETER);
                }

                using (var timer = new TimeCollector("SearchUsingHandCodeWithStringCompare")) {
                    timer.Result = SearchUsingHandCodeWithStringCompare(list, SEARCHPARAMETER);
                }

                using (var timer = new TimeCollector("SearchUsingHandCodeWithStringCompareOrdinal")) {
                    timer.Result = SearchUsingHandCodeWithStringCompareOrdinal(list, SEARCHPARAMETER);
                }

                using (var timer = new TimeCollector("SearchUsingHandCodeWithStringEqualsIgnoreCase")) {
                    timer.Result = SearchUsingHandCodeWithStringEqualsCurrentCultureIgnoreCase(list, SEARCHPARAMETER);
                }

                using (var timer = new TimeCollector("SearchUsingHandCodeWithStringEquals")) {
                    timer.Result = SearchUsingHandCodeWithStringEquals(list, SEARCHPARAMETER);
                }

                Console.WriteLine("Binary Search");

                using (var timer = new TimeCollector("SearchUsingHandCodeWithDepthFirstSearch")) {
                    timer.Result = SearchUsingHandCodeWithDepthFirstSearch(list, SEARCHPARAMETER);
                }

                Console.ReadLine();
                Console.WriteLine("-------------------------------------------------------------");
            } while (true);
        }

        static bool SearchUsingHandCodeWithDepthFirstSearch(IList<EstruturaHierarquica> targetList, string searchParameter) {

            return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, 0, targetList.Count - 1);
        }

        static bool SearchUsingHandCodeWithDepthFirstSearch(IList<EstruturaHierarquica> targetList, string searchParameter, int start, int end) {

            if (start >= end)
                return false;

            int middlePoint = end - ((end - start) / 2);

            int compare = string.Compare(targetList[middlePoint].CodigoTipoRegistro, searchParameter);

            if (compare < 0) {
                return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, middlePoint, end);
            }
            else if (compare > 0) {
                return SearchUsingHandCodeWithDepthFirstSearch(targetList, searchParameter, start, middlePoint - 1);
            }
            else {
                return true;
            }
        }

        static bool SearchUsingHandCodeWithStringCompare(IList<EstruturaHierarquica> targetList, string searchParameter) {

            foreach (var item in targetList) {
                if (string.Compare(item.CodigoTipoRegistro, searchParameter) == 0)
                    return true;
            }
            return false;
        }

        static bool SearchUsingHandCodeWithStringEquals(IList<EstruturaHierarquica> targetList, string searchParameter) {

            foreach (var item in targetList) {
                if (string.Equals(item.CodigoTipoRegistro, searchParameter))
                    return true;
            }
            return false;
        }

        static bool SearchUsingHandCodeWithStringEqualsCurrentCultureIgnoreCase(IList<EstruturaHierarquica> targetList, string searchParameter) {

            foreach (var item in targetList) {
                if (string.Equals(item.CodigoTipoRegistro, searchParameter, StringComparison.CurrentCultureIgnoreCase))
                    return true;
            }
            return false;
        }

        static bool SearchUsingHandCodeWithStringCompareOrdinal(IList<EstruturaHierarquica> targetList, string searchParameter) {

            foreach (var item in targetList) {
                if (string.CompareOrdinal(item.CodigoTipoRegistro, searchParameter) == 0)
                    return true;
            }
            return false;
        }

        static bool SearchUsingHandCode(IList<EstruturaHierarquica> targetList, string searchParameter) {

            foreach (var item in targetList) {
                if (item.CodigoTipoRegistro == searchParameter)
                    return true;
            }
            return false;
        }

        static void PopulateList(IList<EstruturaHierarquica> targetList) {

            for (int i = 0; i < POPULATIONSIZE; i++) {

                EstruturaHierarquica newNode = new EstruturaHierarquica();

                newNode.CodigoTipoRegistro = string.Format(i.ToString().PadLeft(POPULATIONSIZE.ToString().Length, '0'));

                targetList.Add(newNode);
            }
        }

        static bool SearchUsingLinqAny(IList<EstruturaHierarquica> targetList, string searchParameter) {

            var query = targetList.Any(e => e.CodigoTipoRegistro == searchParameter);
            return query;
        }

        static bool SearchUsingLinqFirstOrDefault(IList<EstruturaHierarquica> targetList, string searchParameter) {

            var query = targetList.FirstOrDefault(e => e.CodigoTipoRegistro == searchParameter);
            return (query != null);
        }
    }

    public class TimeCollector : IDisposable {

        private string _label;
        private Stopwatch _watch;

        public object Result { get; set; }

        public TimeCollector(string label) {

            this._label = label;
            this._watch = Stopwatch.StartNew();
        }

        public void Dispose() {

            this._watch.Stop();

            Console.WriteLine(":: {0} - Total: {1} / Result: {2}", this._label,
                                                                   this._watch.Elapsed.TotalMilliseconds,
                                                                   this.Result == null ? string.Empty : this.Result.ToString());
        }
    }

    public class EstruturaHierarquica {

        public string CodigoTipoRegistro { get; set; }

        public object Value { get; set; }
    }
}
 

FH