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.