Um blog sobre nada

Um conjunto de inutilidades que podem vir a ser úteis

Sort e BinarySearch

Posted by Diego em Junho 22, 2009


            Me deparei nesses ultimos dias com uma situacao em que eu precisava procurar um nome numa lista com 900 mil elementos e pra piorar, havia 1 milhao e 700 mil nomes pra procurar. Para fazer procuras, eu sempre utlizei o metodo “Find” da classe “List”, que apesar de funcionar estava “um pouco” demorado (cerca de 2 segundos cada procura). Como o programa ia ser rodado uma vez a cada morte de papa mais ou menos, ate nao teria problema mas eu preferi buscar uma solucao mais rapida….ou pelomenos menos demorada J

            Pesquisando na net, descobri o metodo BinarySearch que supostamente eh o tipo de pesquisa mais rapida, entao eu resolvi testar ele. O resultado foi bom, eu diminui o tempo de execucao em mais ou menos 1/3 a 2/3 (eu fiz uma estimativa com base no numero de comparacoes por minutos de cada um dos metodos. Na verdade ficou dificil de saber a real melhora pq a rotina de comparacao envolvia insercoes na base de dados, entao dependia do trafego da rede, do servidor, etc…mas definitivamente ficou mais rapido).

            Segue abaixo uma explicacao de como o metodo funciona. Vale lembrar que foi a primeira vez que eu implemente esse metodo e talvez nao seja a maneira mais correta…mas funciona hehe.

Bom, primeiro segue o construtor da classe que estou usando (nao vou colocar todo codigo da classe pq eh desnecessario):

public JPGFile(string name, string path, double bytes)

e a lista em questao:

List<JPGFile> listUsedCars = new List<JPGFile>();

Para o metodo funcionar, eh necessario que a lista esteja ordenada, o que deve ser feito com o metodo sort desse jeito:

listUsedCars.Sort(new CarComparer());

o detalhe eh que como estamos comparando objetos, temos que dizer como que essa comparacao vai ser feita. Para dizer isso usamos uma classe que deve implementar a interface Icomparer:

public class CarComparer : IComparer<JPGFile>
     {
     public int Compare(JPGFile x, JPGFile y)
     {
          int RetVal = String.Compare((x as JPGFile).Name, (y as JPGFile).Name, true);
          return RetVal;
     }
}

Depois de usar o Sort, podemos usar o metodo BinarySearch para procurar um elemento dentro da lista:

int achou = listUsedCars.BinarySearch(new JPGFile(name, photopath, 0), new CarComparer());

onde “name” eh o nome que queremos procurar se existe na lista. Se o “achou” for maior que zero, o elemento existe na lista.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s

 
%d bloggers like this: