Lluís Franco on Geeks.ms
  • Home

¿Goodbye Dictionary?

  • By lfranco
  • Jul-15-2008
  • Sin categoría
  • 7 Comments.

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.

GenericsError1

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
image image image

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,

Comments

7 Responsesso far

  1. anonymous dice:
    15 julio, 2008 a las 5:32 pm

    Hey Creo que te falto algo!
    stopWatch.Reset();

    Soy aficionado a este tipo de test y por eso me parecio muy curioso lo que dices del Dictionary!
    Hice mis pruebas y mira mis resultados!

    //Resultados con tu algoritmo “Sin el stopWatch.Reset(); ”
    Compare load 100000 items in List vs. Dict. (ms.)
    List: 1951,2256
    Dict: 3857,355

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

    Compare verify one item by key in List vs. Dict. (ms.)
    List: 9,7361
    Dict: 9,7395

    //Lo que a priori nos dice que mi máquina mucho mas lenta que la tuya, y que Dictionary son malos, pero revisando tu codigo encontre que usas el Start Y Stop del stopwatch y no paras ni limpias el stopwatch, (Como un cronometro) y me puse a modificarlo para ver si los resultados puedes ser algo similares y mira lo que encontré!

    //Mis resultados
    Compare load 100000 items in List vs. Dict. (ms.)
    List: 1777,8614
    Dict: 1830,4485

    Compare get one item by key in List vs. Dict. (ms.)
    List: 8,85
    Dict: 0,0385

    Compare verify one item by key in List vs. Dict. (ms.)
    List: 8,6122
    Dict: 0,0036

    //hey que cambio! los Dictionary no son tan malos!, bien lo unico que hice fue agregar el reset(), entonces el Dictionary no es tan malo! XD

    Un saludo desde colombia!

    Responder
  2. anonymous dice:
    15 julio, 2008 a las 5:33 pm

    Ahhh y el codigo que modifique!
    es una app de consola!

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Diagnostics;

    namespace ConsoleApplication1
    {
    class Program
    {
    static void Main(string[] args)
    {
    LoadListDict();
    GetOneItemByKey(2);
    VerifyOneItemByKey(2);
    Console.ReadLine();
    }

    static List list = new List();
    static Dictionary dict = new Dictionary();

    private static 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; watch.Reset(); //Limpia el stopwatch dict.Clear(); watch.Start(); for (int i = 1; i <= max; i++) { dict.Add(i, new CPItem(i)); } watch.Stop(); TimeSpan ts2 = watch.Elapsed; Console.WriteLine( "Compare load {0} items in List vs. Dict. (ms.)rnList: {1}rnDict: {2}", max.ToString(), ts1.TotalMilliseconds.ToString(), ts2.TotalMilliseconds.ToString()); } private static 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.Reset();//Limpia el stopwatch watch.Start(); CPItem item2 = dict[keyvalue]; watch.Stop(); TimeSpan ts2 = watch.Elapsed; Console.WriteLine( "Compare get one item by key in List vs. Dict. (ms.)rnList: {0}rnDict: {1}", ts1.TotalMilliseconds.ToString(), ts2.TotalMilliseconds.ToString()); } private static 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.Reset();//Limpia el watch watch.Start(); bool v2 = dict.ContainsKey(keyvalue); watch.Stop(); TimeSpan ts2 = watch.Elapsed; Console.WriteLine( "Compare verify one item by key in List vs. Dict. (ms.)rnList: {0}rnDict: {1}", ts1.TotalMilliseconds.ToString(), ts2.TotalMilliseconds.ToString()); } } public 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; } } }

    Responder
  3. lfranco dice:
    15 julio, 2008 a las 5:59 pm

    :-)))
    Ja, ja, ja, ja!!! Muy buena Steven!!!

    Mira que olvidarme de resestear el crono… Efectivamente, acabo de realizar la modificación y los tiempos ahora son totalmente diferentes.
    Modifico el código y mañana lo publico…

    Repito: Muy buen apunte!
    Ya me extrañaba a mi… 😉

    Responder
  4. jorge dice:
    15 julio, 2008 a las 7:46 pm

    Tito, eso te pasa por escribir en C#. 😛

    Responder
  5. anonymous dice:
    15 julio, 2008 a las 8:33 pm

    Joder que cagada macho. Antes de publicar una cosa así, deberías revisar y vovler a revisar. Te pegas la currada de hacer gráficos y todo….no quiero ni pensar en los programas que haces

    Responder
  6. jorge dice:
    15 julio, 2008 a las 9:48 pm

    Siempre digo una cosa Anonimo… quien no hace nada, ese… nunca se equivoca.

    Responder
  7. fdiaz dice:
    17 julio, 2008 a las 10:04 am

    Y es más, retificar es de sabios [;)]. Gracias por el aporte Luis

    Responder

Deja un comentario Cancelar respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

← Previous Post Next Post →

Tags

async Back best practices

Entradas recientes

  • Video de mi charla en la #dotNetSpain2016
  • I’m back. Miss me?
  • Office365 actualizado a 2013 para nuevas suscripciones
  • Serializar listas genéricas en aplicaciones WinRT
  • [TPL] Problemas de concurrencia

Comentarios recientes

  • Darling Chavez en Tip: Mostrar objetos relacionados en DevExpress GridControl
  • Alexander en [TPL] Problemas de concurrencia
  • cristinakity en Funciones escalares en TSQL, JOINS, CROSS APPLY, y la madre que parió al topo.
  • cristinakity en Funciones escalares en TSQL, JOINS, CROSS APPLY, y la madre que parió al topo.
  • anonymous en HowTo: Crear una pantalla de inicio (splash screen)

Archivos

  • marzo 2016
  • marzo 2013
  • octubre 2012
  • septiembre 2012
  • agosto 2012
  • febrero 2012
  • diciembre 2011
  • noviembre 2011
  • octubre 2011
  • septiembre 2011
  • agosto 2011
  • junio 2011
  • mayo 2011
  • abril 2011
  • febrero 2011
  • enero 2011
  • diciembre 2010
  • noviembre 2010
  • octubre 2010
  • agosto 2010
  • julio 2010
  • marzo 2010
  • febrero 2010
  • enero 2010
  • diciembre 2009
  • noviembre 2009
  • octubre 2009
  • septiembre 2009
  • agosto 2009
  • julio 2009
  • junio 2009
  • mayo 2009
  • abril 2009
  • marzo 2009
  • febrero 2009
  • enero 2009
  • diciembre 2008
  • noviembre 2008
  • octubre 2008
  • septiembre 2008
  • agosto 2008
  • julio 2008
  • junio 2008
  • mayo 2008
  • abril 2008
  • marzo 2008
  • febrero 2008
  • enero 2008
  • diciembre 2007
  • noviembre 2007
  • octubre 2007
  • septiembre 2007
  • agosto 2007
  • abril 2007
  • febrero 2007
  • enero 2007

Categorías

  • .NET
  • C#
  • Channel9
  • Evento
  • Personal
  • Videos

Meta

  • Acceder
  • RSS de las entradas
  • RSS de los comentarios
  • WordPress.org
About This Site

A cras tincidunt, ut tellus et. Gravida scel ipsum sed iaculis, nunc non nam. Placerat sed phase llus, purus purus elit.

Archives Widget
  • January 2010
  • December 2009
  • November 2009
  • October 2009
Categories
  • Entertainment
  • Technology
  • Sports & Recreation
  • Jobs & Lifestyle
Search
  • facebook
  • twitter
  • rss

Powered by WordPress  |  Business Directory by InkThemes.

This site uses cookies: Find out more.