¿Goodbye Dictionary?

Corrección al artículo (16/07/2008):

Todas las mediciones de tiempo efectuadas en las compartivas entre listas y diccionarios han sido mal efectuadas y no son válidas. Porqué? Porque a un servidor se le olvidó ‘resetear’ el cronómetro del StopWatch entre una medición y otra (ay, ay, ay…), de modo que los tiempos tomados para el objeto dictionary incluyen también los de la lista, y por eso son mucho mayores de lo esperado.

Un ‘pequeño’ olvido pero que afecta totalmente al sentido del post, ya que la conclusión del post era que acceder a un elemento de un diccionario NO era más rápido que acceder a un elemento de una lista, cuando la realidad es que SI lo es… y mucho. Siento haber publicado lo contrario y aquí me retracto.

De este error puedo sacar varias conclusiones:

• Revisar: Acostumbrarme a revisar más en profundidad lo que publico. He usado infinidad de veces el objeto StopWatch y no es nuevo para mi, así que todavía me duele más haberme olvidado de reiniciar el crono… Muchas gracias por el comentario Steven.
• No hacer tantas cosas al mismo tiempo: La verdad es que cuando escribí el post estaba haciendo varias cosas al mismo tiempo, entre las cuales me encontraba realizando unas pruebas para una aplicación, y al medir los tiempos me quedé muy sorprendido y empecé a escribir el post sin detectar el error en mi código.
• Todos nos equivocamos: Eso es evidente, y cualquiera puede cometer un error como este. Lo malo es que en lugar de escribir el post rápidamente y publicarlo, debería haberlo dejado para revisarlo hoy… pero lo hecho hecho está.
• Hay que aprender de los errores: Prefiero hacer algo y equivocarme a no hacer nada y no equivocarme. Con todo, espero aprender algo de todo esto, porque todos seguimos aprendiendo día a día (y malo del día que no lo hagamos).

Pero vamos con la corrección. Los nuevos tiempos si agregamos un watch.Reset(); antes de empezar a tomar los tiempos del diccionario son los siguientes:

Compare load 100000 items in List vs. Dict. (ms.)
List: 678,4068
Dict: 759,5071

Compare get one item by key in List vs. Dict. (ms.)
List: 0,3645
Dict: 0,0058

Compare verify one item by key in List vs. Dict. (ms.)
List: 0,2748
Dict: 0,0058

La conclusión es que cargar datos en un diccionario es sólamente un poco más lento que cargarlos en una lista. mientras que es mucho más rápido acceder a los elementos que contiene (del orden 50 veces más rápido aproximadamente). Evidentemente esto justifica sobradamente el uso de diccionarios.

Bueno… Tal vez el título del artículo ahora debería quedar como «¿Goodbye Dictionary? ¡Hola melón!» 😛

Saludos desde Andorra,

Fin de la corrección al artículo

El artículo original (15/07/2008):

Generics

La aparición del framework 2.0 nos trajo una grata sorpresa: La aparición de Generics, que nos proveía por fin de un conjunto de colecciones fuertemente tipadas, que mejoraban mucho el rendimiento al evitar el uso de boxing y unboxing, y permitían un código mucho más legible, elegante, así como detectar y prevenir muchos errores en tiempo de compilación.

Desde ,entonces, de todos los distintos tipos de colecciones genéricas, en el 90% de los casos he usado estos dos: List y Dictionary. El primero de ellos es obviamente una lista de objetos <T>, algo de uso cotidiano, y el segundo es el equivalente genérico del viejo diccionario, que permite guardar una colección de elementos y una clave para acceder a ellos <TKey>, <TValue>:

Dictionary<int, CPItem> dict = new Dictionary<int, CPItem>();

Este tipo diccionario es ideal para almacenar una serie de objetos (por ejemplo clientes que provienen de una BD) y poder acceder a uno de ellos a través de su campo clave o identificador, sea éste del tipo que sea (por ejemplo en el caso anterior la clave es de tipo int):

CPItem item2 = dict[24];

De este modo, es muy sencillo acceder a un elemento de la colección a través del valor de su identificador (no confundir con su posición dentro de la lista). Sin embargo y a pesar de su innegable potencia, hay un par de cosas que no me gustan de los diccionarios:

• Siempre es más lento cargar los objetos en un diccionario que en una lista (del orden de 2 a 1 aproximadamente)
• Un diccionario no es serializable ‘per se’ (al menos sin hacer trucos), y esto SI puede ser un problema.

Sin embargo, tiene la gran ventaja frente a la lista de que permite acceder de forma casi instantánea a un elemento de la misma, y además contiene métodos que permiten verificar si la colección contiene un elemento, ya sea por clave o por valor.

List vs. Dictionary

Veamos un ejemplo rápido, declaramos una clase con algunos miembros de diversos tipos de datos (para tener de todo un poco) y usamos esta clase para cargar varios objetos en una lista y un diccionario respectivamente:

class CPItem

{

    const int max = 1000000;

    public int propInt { get; set; }

    public string propString { get; set; }

    public DateTime propDateTime { get; set; }

    public bool propBool { get; set; }

    public double propDouble { get; set; }

    public CPItem(int propint)

    {

        Random r = new Random(max);

        propInt = propint;

        propString = string.Format("Item {0}", propint.ToString("000000"));

        propDateTime.AddDays(propint);

        propBool = propint <= 0.5 ? false : true;

        propDouble = r.NextDouble() * max;

    }

}

Declaramos los dos objetos genéricos:

List<CPItem> list = new List<CPItem>();

Dictionary<int, CPItem> dict = new Dictionary<int, CPItem>();

Y a continuación usamos un StopWatch para medir los tiempos de carga de 100.000 elementos… y podremos observar una gran diferencia:

private void LoadListDict()

{

    const int max = 100000;

    Stopwatch watch = new Stopwatch();

    list.Clear();

    watch.Start();

    for (int i = 1; i <= max; i++)

    {

        list.Add(new CPItem(i));

    }

    watch.Stop();

    TimeSpan ts1 = watch.Elapsed;

    dict.Clear();

    watch.Start();

    for (int i = 1; i <= max; i++)

    {

        dict.Add(i, new CPItem(i));

    }

    watch.Stop();

    TimeSpan ts2 = watch.Elapsed;

    this.ResultsTextBox.Text = string.Format(

        "Compare load {0} items in List vs. Dict. (ms.)rnList: {1}rnDict: {2}",

        max.ToString(),

        ts1.TotalMilliseconds.ToString(),

        ts2.TotalMilliseconds.ToString());

}

En mi estación estos son los tiempos promedio de carga después de ejecutar 5 veces:

Compare load 100000 items in List vs. Dict. (ms.)
List: 737,1392
Dict: 1479,4486

Bien, está claro que si hay que elegir entre ambos hay que tener un buen motivo para escoger el diccionario… ¡ya que la lista es el doble de rápida!

LINQ to objects

Con la aparición de VS2008 y del framework 3.5, aparecen las expresiones de consulta. Éstas nos permiten manipular colecciones de objetos en memoria, para filtrarlos, ordenarlos y agruparlos según nuestras necesidades.

Así que es posible que nos preguntemos ¿es necesario el uso de diccionarios, si ahora disponemos de LINQ para manejar listas? Es decir, si puedo cargar los datos en una lista genérica y acceder mediante LINQ to objects a un elemento, o a un subconjunto de éstos… ¿qué sentido tiene usar un dictionary?

Uhm… Pues supongo que el rendimiento podría ser un factor, ya que según la documentación de este objeto: Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<(Of <(TKey, TValue>)>) class is implemented as a hash table. O dicho de otro modo: Recuperar un valor utilizando su clave es muy rápido, porque la clase Dictionary se implementa como una tabla hash.

Ya sabía yo que había un buen motivo para usar un diccionario: Debe ser más mucho más rápido al acceder a un objeto a través de su clave que extraerlo de una lista mediante LINQ… seguro! …. ¿o tal vez no?

Hagamos un par de pruebas:

A) Cuanto tardamos en recuperar a un elemento a través de su clave:

private void GetOneItemByKey(int keyvalue)

{

    if (list.Count == 0 || dict.Count == 0) LoadListDict();

    Stopwatch watch = new Stopwatch();

    watch.Start();

    CPItem item1 = (from l in list where l.propInt == keyvalue select l).Single();

    watch.Stop();

    TimeSpan ts1 = watch.Elapsed;

    watch.Start();

    CPItem item2 = dict[keyvalue];

    watch.Stop();           

    TimeSpan ts2 = watch.Elapsed;

    this.ResultsTextBox.Text = string.Format(

        "Compare get one item by key in List vs. Dict. (ms.)rnList: {0}rnDict: {1}",

        ts1.TotalMilliseconds.ToString(),

        ts2.TotalMilliseconds.ToString());

}

En mi estación estos son los tiempos promedio de carga después de ejecutar 5 veces:

Compare get one item by key in List vs. Dict. (ms.)
List: 3,8518
Dict: 3,8566

Pues parece que ambos tiempos son iguales. Es más, acceder a la colección a través de LINQ ¡es incluso un poquito más rápido! Uhm, vaya… bueno, veamos el segundo ejemplo antes de sacar conclusiones:

B) Cuanto tardamos en verificar si existe un elemento a través de su clave:

private void VerifyOneItemByKey(int keyvalue)

{

    if (list.Count == 0 || dict.Count == 0) LoadListDict();

    Stopwatch watch = new Stopwatch();

    watch.Start();

    var items = from l in list where l.propInt == keyvalue select l;

    bool v1 = (items.Count() == 0);

    watch.Stop();

    TimeSpan ts1 = watch.Elapsed;

    watch.Start();

    bool v2 = dict.ContainsKey(keyvalue);

    watch.Stop();

    TimeSpan ts2 = watch.Elapsed;

    this.ResultsTextBox.Text = string.Format(

        "Compare verify one item by key in List vs. Dict. (ms.)rnList: {0}rnDict: {1}",

        ts1.TotalMilliseconds.ToString(),

        ts2.TotalMilliseconds.ToString());

}

En mi estación estos son los tiempos promedio de carga después de ejecutar 5 veces:

Compare verify one item by key in List vs. Dict. (ms.)
List: 3,906
Dict: 3,9111

Pues parece que en este caso ambos tiempos son también iguales. Entonces definitivamente NO ES MÁS RÁPIDO UTILIZAR UN DICCIONARIO PARA ACCEDER A LOS ELEMENTOS QUE CONTIENE A TRAVÉS DE SU CLAVE:

Carga	Recuperar elemento	Existe elemento

Conclusión 

Pues sinceramente, si no es más rápido el acceso a un diccionario, pero es más lento en su carga y encima no es serializable… ¿en qué casos podemos seguir usando diccionarios en lugar de listas?

Espero vuestras opiniones,