C# Performance, Acelerando C#, Tip #1 List.Contains() vs Dictionary.ContainsKey()

Generalmente el rendimiento de una aplicación no se toma en cuenta hasta que este se vuelve inaceptable, es decir, si todo funciona y esta dentro de los limites aceptables,  pues nadie se pone a pensar en optimizar nada, por ahí dicen "no optimice demasiado pronto" pero esto no significa "no optimice nunca", para mi la optimización empieza desde el momento en el que se piensa la solución, es inaceptable no considerar el rendimiento cuando se planea la forma de implementar una característica. 

Hoy publico uno de los tantos casos con los que me ha tocado optimizar, es muy común y muchas personas no tienen presentes este tipo de consideraciones al decidir que método utilizar, es mas ahora con LINQ y la inferencia de tipos mucha gente se enfoca mas en usar querys LINQ para resolverlo todo, sin ponerse a pensar ni por un momento las implicaciones que esta "maravilla" tienen en el rendimiento final de una aplicación. 

En esta publicación voy a presentar un problema de rendimiento que es bastante evidente para las personas que prestaron 10% de atención a su curso de estructuras de datos, pero que resulta difícil apreciar cuando uno empieza en esto de la programación (todos pasamos por ahí no se preocupen). 

ahora vamos a los datos concretos, en este post vamos a analizar el rendimiento de List.Contains() contra el rendimiento de Dictionary.ContainsKey() para esto nos vamos a respaldar de unas cuantas lineas de código para clarificar la diferencia. Este caso concreto usando Strings para los elementos de la colección resulta apreciable la diferencia entre una y otro, resultando en una gran ventaja para el Dictionary.ContainsKey, el ejemplo que acompaño para soportar esta afirmación demuestra una necesidad bastante común cuando uno esta trabajando con colecciones en memoria, esto es seleccionar un grupo de objetos solo si estos tienen una correspondencia de algún campo en otra colección (podríamos decir que es una intersección)

en la imagen podemos apreciar que utilizando el query de esta forma, tenemos 3558 mili segundos para obtener el resultado

 var r1 = (from foo in fooList
                     where (from bar in barList select bar.Id).Contains(foo.BarId)
                          select foo).ToList();

sin darnos cuenta estamos relegando la mayor parte del trabajo en List.Contains (esto aplica para colecciones en memoria, cuando son querys a la base de datos es otra la historia)

por otro lado cuando creamos un diccionario intermedio para ayudarnos a resolver la dependencia sobre contains() tenemos el siguiente codigo, el cual tarda solo 88 mili segundos para obtener el mismo resultado, aunque consume un poco mas de memoria por el uso del diccionario extra.

var barMap = (from item in barList
                              select item.Id).Distinct().ToDictionary(item => item, item => 1);
 
var r2 = (from foo in fooList
          where barMap.ContainsKey(foo.BarId)
          select foo).ToList();

en resumen podemos decir, Recuerde siempre que el tiempo de búsqueda en una lista es O(n) mientras que el tiempo de búsqueda en una tabla de hash (o diccionario) es O(1).

Descargar Código Fuente