Como todos sabran ya, las listas genericas nos ofrecen dos opciones de busqueda que son atravez de una busqueda lineal utilizando una sentencia foreach / while o bien utilizando un metodo propio de dichas listas que es Find ultizando un delegado anonimo y como lujo final utilizaremos tambien una busqueda mediante Expresiones Lamda.
Cualquiera de estas dos formas de busqueda presuponen un gasto en recursos importante debido a que en todos los casos se utiliza una busqueda lineal sobre la lista.
Otra opcion de busqueda que tenemos es implementar un tipo de busqueda binaria, accediendo a los elementos de la lista por el indice que estas tienen.
A continuacion vamos a ir explicando paso a paso cada una de estas formas de busqueda.
Busqueda lineal utilizando ForEach / While / Delegado anonimo / Expresiones Lambda:
En este caso, lo unico que haremos sera recorrer uno a uno los elementos de la lista hasta encontrar el buscado. Este tipo de busqueda lineal es la mas sencilla y rapida de implementar, y en terminos de velocidad dependiendo de la cantidad de elementos de nuestra lista va a variar los tiempos de busqueda.
Veamos la sentencia de estas implementaciones:
Sentencia ForEach:
...
foreach (int var in arg)
{
if (var.CompareTo(item) == 0)
{
tf = new TimeSpan(0, 0, 0, DateTime.Now.Second,
DateTime.Now.Millisecond);
break;
}
}
...
Sentencia While:
...
IEnumeratoree = arg.GetEnumerator();
bool find = false;
ee.Reset();
while (ee.MoveNext() && !find)
{
find = (ee.Current.CompareTo(item) == 0);
}
...
Metodo Find:
...
int finder = arg.Find(delegate(int aa)
{
if (aa.CompareTo(item) == 0)
{
tf = new TimeSpan(0, 0, 0, DateTime.Now.Second,
DateTime.Now.Millisecond);
return true;
}
else
{
return false;
}
});
...
Expresiones Lambda:
...
int finder = arg.First(number => number.CompareTo(item) == 0);
...
Que sacamos en conclucion de estos cuatro ejemplos de busqueda? Basicamente la busqueda en todos se realiza de la misma manera, recorrer uno a uno los elementos empezando desde el primero hasta llegar al elemento buscado, con todas las implicancias que esto tiene debido a que si buscamos el anteultimo elemento en una lista como la del ejemplo que tiene 100.000.000 de elementos los tiempos de busqueda se dispararan a medida que nos acerquemos al final de la lista
Tengamos en cuenta que si bien la lista se llena con numeros en forma aleatoria luego para que esto sea un ejemplo verdaderamente serio se ordenan ya que si trabajaramos con listas desordenadas cabe la posibilidad que el elemento a buscar este en la primer posicion y en ese caso las busquedas lineales contarian con ventaja, sin embargo vamos a darle la recarga del ordenamiento a la busqueda binaria para ser equitativos ademas.
En los dos primeros ejemplos tanto el While como en el ForEach nosotros vamos indicando como debe hacerce la iteracion en los elementos de la lista como se habran dado cuenta. Aca cabe destacar los beneficios del dotNet Framework tanto con los metodos anonimos como con las expresiones lambda nos abstraen de esta iteracion y solo necesitan que nosotros les brindemos las condiciones para realizar la busqueda si se fijan en el ejemplo, las lineas de codigo disminuyen notoriamente.
Busqueda binaria accediendo por el indice de la lista:
Para este tipo de busqueda necesitamos que la lista se encuentre ordenada como ya aclaramos anteriormente. Basicamente lo que vamos a realizar es una division de la misma tomando el elemento del medio de la lista, el cual utilizaremos para comparar contra nuestro item a buscar, en caso de ser igual lo retornaria, en caso de ser menor nuestra nueva lista seria solo la mitad de la original menos 1.
En este punto volvemos a repetir la operacion y dividimos la lista en la mitad, volvemos a comparar y supongamos que ahora nuestro item a buscar es mayor que el item del centro, ahora nuestra nueva lista sera la mitad superior de esta mitad menos 1 (el item ya comparado) asi repetiremos el proceso las veces que sean necesarias descartando en cada vuelta la mitad de los elementos
Hice este ejemplo a partir de un while iterando sobre la lista original, cabe destacar que el mismo podria hacerce mediante un metodo recursivo.
Como podran ver a continuacion en cada pasada nos deshacemos exactamente de la mitad de los elementos a buscar con lo cual las probabilidades de ascierto estan en un orden exponencial con cada vuelta.
Busqueda binaria:
...
arg.Sort();
bool find = false;
int izquierda = 0;
int derecha = arg.Count - 1;
int centro = 0;
int counter = 0;
while (!find && izquierda <= derecha)
{
counter++;
centro = (izquierda + derecha) / 2;
if (item < derecha =" centro"> arg[centro])
izquierda = centro + 1;
else
find = true;
}
...
Los resultados de esta busqueda verdaderamente son increibles, de por si esto esta fundamentado en que el numero de compraciones realizadas disminuye exponencialmente como dijimos anteriormente. Cabe la pena aclarar que los resultados se elevan bastante cuando uno agrega el metodo Sort a la busqueda, ya que esto lo alentece y mucho.
Pruebas realizadas:
Lo que les ofrezco aca es un screenshot de los tiempos que demora cada uno de los metodos de busca descriptos en este post.
Codigo Fuente:
Aca les dejo el link de google code donde podran obtener el codigo de ejemplo:
svn checkout http://testbusquedalistas.googlecode.com/svn/trunk/ testbusquedalistas-read-only
Conclucion:
Como conclucion final lo que pudimos ver es que cada vez que delegamos una tarea en un componente que la realiza de manera automatica perdemos en performance, lo mas conveniente (pese a que muchos no opinen esto) es realizar los algoritmos importantes dentro del poyecto como los de busqueda u ordenamiento nosotros.
Pudimos ver que cuando delegamos un trabajo tan importante como la forma de iterar sobre la lista ganamos en tiempo de desarrollo pero perdimos en performance, todas estas cosas son buenas evaluarlas con anticipacion para no encontrarnos con problemas al realizar pruebas de usuario.
Desde ya muchas gracias a los que se tomaron el tiempo para leer este post, espero que les sea util y desde ya se aceptan todo tipos de comentarios o sugerencias, como asi tambien criticas.
