Inicio > .NET Framework, C#, Tutorial > Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Tres diccionarios especializados

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Tres diccionarios especializados


Hasta el momento, la serie de artículos dedicados a colecciones solo ha presentado un simple diccionario: Hashtable. Como habíamos visto antes, éste diccionario agrupa los pares llave-valor basándose en el hash de la llave. Ahora bien, este tipo de ordenamientos suele ser eficiente, sobre todo cuando tenemos diccionarios enormes. Pero hay situaciones en las que Hashtable no es tan eficiente, o bien bajo ciertas circunstancias algun enfoque diferente puede ser mejor. En esta entrada vamos a analizar tres diccionarios que se encuentran dentro del espacio de nombres System.Collections.Specialized, y que ofrecen dichos enfoques para escenarios muy específicos: ListDictonary, HybridDictionary y OrderedDictionary.

Comencemos por estudiar ListDictionary. A primera vista, ListDictionary luce como una implementación normal de IDictionary, y de hecho así es. No añade métodos nuevos. Cuenta con los métodos y propiedades que implementan ICollection, como Count, IsSynchronized, SyncRoot, CopyTo; y también con propiedades y métodos propios de un IDictionary, como IsFixedSize, IsReadOnly, Keys, Values, Add, Clear, Contains, Remove y el indexador para acceder a los valores dada una llave; todos estos miembros que ya hemos explicado en entradas anteriores. De hecho, incluso contiene menos métodos que Hashtable. Entonces la pregunta es: ¿para qué nos sirve ListDictionary?

La respuesta es que mientras Hashtable almacena los pares llave-valor en bloques de memoria que son accesibles vía el código hash de la llave, ListDictionary los almacena como si fuera una lista enlazada. Es decir, el primer elemento contiene el par llave-valor, más un apuntador (o referencia, en el argot de C#) al elemento siguiente, y así sucesivamente hasta llegar al final de la lista. Esto implica que ListDictionary no manipula la memoria (o al menos, no de la forma en que Hashtable lo hace) y por lo tanto el acceso a los elementos es más eficiente en términos de memoria y procesamiento.

Sin embargo esto tiene su precio. Si recuerdas tus viejas clases de estructuras de datos que llevaste en la universidad, sabrás entonces que una lista enlazada tiene un mal rendimiento cuando intentamos acceder a los elementos de forma secuencial. De hecho, esta es la diferencia más grande que hay entre un array o vector (donde los elementos se almacenan en bloques de memoria contigua, haciendo posible el acceso secuencial) y la lista enlazada, donde se comienza a navegar por la cabeza de la lista, yendo de uno en uno hasta localizar el elemento que nos interesa. Luego entonces, el rendimiento de una lista (y por ende, de ListDictionary) al querer acceder a un elemento disminuye considerablemente conforme el número de elementos contenidos aumenta.

Para probar lo anterior, consideremos el siguiente código.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            const int elements = 10;

            IDictionary dic = new ListDictionary();
            for (int i = 0; i < elements; i++)
            {
                string key = i.ToString();
                string val = string.Format("Cadena {0}", i);
                dic.Add(key, val);
            }

            DateTime start = DateTime.Now;
            for (int i = 0; i < elements; i++)
            {
                var key = i.ToString();
                var val = dic[key];
                Console.WriteLine("{0}: {1}", key, val);
            }

            TimeSpan duration = DateTime.Now - start;
            Console.WriteLine("Duración: {0}", duration);

            Console.ReadKey(true);
        }
    }
}

En este pequeño programita, creamos un ListDictionary (línea 13), le añadimos un número determinado de elementos (especificado en la constante definida en la línea 11) y posteriormente recorremos todo el diccionario y lo mostramos en la consola. Para hacer el ejemplo más interesante, tomamos el tiempo de inicio (línea 21) y el tiempo final (línea 29) y mostramos el tiempo que tardó el diccionario en obtener los valores. Si ejecutamos el programa, obtendríamos un resultado similar al siguiente (puede variar dependiendo de las características de la máquina que lo ejecute).

0: Cadena 0
1: Cadena 1
2: Cadena 2
3: Cadena 3
4: Cadena 4
5: Cadena 5
6: Cadena 6
7: Cadena 7
8: Cadena 8
9: Cadena 9
Duración: 00:00:00.0020001

Después de ejecutar el programa en repetidas ocasiones, el tiempo empleado suele estar entre 2 y 3 milésimas de segundo. Ahora bien, si en lugar de diez elementos cambiamos la línea 11 para que sean mil, el tiempo de ejecución me aparece entre 186 y 199 milésimas de segundo. Para comparar, cambiemos la línea 13 para que en lugar de un ListDictionary creemos un Hashtable:

IDictionary dic = new Hashtable();

Si añadimos diez elementos, el tiempo promedio se encuentra entre 3 y 4 milésimas de segundo, un pequeño aumento con respecto a ListDictionary. Sin embargo, al añadir mil elementos, obtengo un tiempo promedio de entre los 155 y 170 milésimas. Una baja sensible con respecto a ListDictionary. Repitiendo el ejercicio pero ahora con 10,000 elementos, tenemos que mientras Hashtable me da tiempos de entre 800 milésimas y 1.06 segundos, ListDictionary me da tiempos de entre 2.9 y 3.2 segundos.

Este pequeño experimento nos permite concluir que ListDictionary es más eficiente que Hashtable cuando nuestro conjunto de datos es pequeño, pero que conforme dicho conjunto crece, el rendimiento comienza a bajar considerablemente. De hecho, el último ejercicio con diez mil elementos mostró que el rendimiento de Hashtable con respecto a ListDictionary puede ser entre 200% y 300% mayor.

Luego entonces tenemos la premisa de ListDictionary: es un diccionario optimizado para trabajar con pocos elementos (la documentación dice que no más de diez), de tal suerte que si el número de elementos es grande, es preferible utilizar otro tipo de diccionario, pero que si el número permanece bajo se obtendrán mejores resultados con ListDictionary.

Y esto precísamente nos lleva al segundo diccionario especializado a tratar. Supongamos que tenemos un escenario en el cual tenemos un diccionario que generalmente tiene pocos elementos. Pero que bajo ciertas circunstancias, éste puede crecer. Para no perder el rendimiento, tendríamos que usar ListDictionary y cuando éste crezca, copiar todos los elementos a un Hashtable. Pues bien, hay una colección que hace precísamente eso: HybridDictionary. Esta clase emplea de forma interna un ListDictionary cuando el número de elementos se mantiene bajo, pero que cambia a Hashtable cuando el número crece.

Al igual que ListDictionary, HybridDictionary implementa las mismas propiedades y métodos que definen ICollection e IDictionary, con la salvedad que el constructor nos permite especificar el número de elementos que contendrá la colección de forma inicial. Pero evidentemente la fortaleza de la clase radica en las estrategias utilizadas para optimizar el acceso a los pares llave-valor. Para mostrar esto, tomemos el ejercicio que habíamos practicado anteriormente y modifiquémoslo para utilizar HybridDictionary.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            const int elements = 10;

            IDictionary dic = new HybridDictionary();
            for (int i = 0; i < elements; i++)
            {
                string key = i.ToString();
                string val = string.Format("Cadena {0}", i);
                dic.Add(key, val);
            }

            DateTime start = DateTime.Now;
            for (int i = 0; i < elements; i++)
            {
                var key = i.ToString();
                var val = dic[key];
                Console.WriteLine("{0}: {1}", key, val);
            }

            TimeSpan duration = DateTime.Now - start;
            Console.WriteLine("Duración: {0}", duration);

            Console.ReadKey(true);
        }
    }
}

Cuando ejecuto en repetidas ocasiones este código, obtengo un tiempo promedio de entre 2 y 3 milésimas, similar al que obteníamos usando ListDictionary. Pero si cambiamos el número de elementos de diez a diez mil, en lugar de obtener el promedio de entre 2.9 y 3.2 segundos, obtenemos un promedio de 0.88 a 0.92 segundos, similar al que habíamos obtenido con Hashtable. Esto es así, en efecto, debido al comportamiento interno de HybridDictionary.

El tercer diccionario especializado que vamos a tratar, a diferencia de los dos anteriores, no se distingue de Hashtable o algún otro diccionario por la optimización hecha en base al número de elementos que contenga, sino más bien porque permite el acceso aleatorio a los elementos: es decir, a través de un índice. La clase se llama OrderedDictionary y, como su nombre lo sugiere, es un diccionario que mantiene ordenados los elementos basados en la llave de los mismos en bloques de memoria contigua, de forma muy similar a como los almacena un array o un vector. La principal ventaja de esto es que podemos acceder a los elementos no solamente a través de la llave, sino también a través de un índice.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            OrderedDictionary dic = new OrderedDictionary();
            dic.Add("John", "Imagine");
            dic.Add("Ringo", "Photograph");
            dic.Add("Paul", "Another day");
            dic.Add("George", "My sweet lord");

            for (int i = 0; i < dic.Count; i++)
            {
                Console.WriteLine("{0} - {1}", i, dic[i]);
            }

            Console.ReadKey(true);
        }
    }
}

El ejemplo anterior muestra cómo podemos usar el indexador de OrderedDictionary para acceder por medio del índice. Esto es algo que no podemos lograr con Hashtable, y nos proporciona la comodidad de poder iterar sobre los elementos sin tener que conocer las llaves de antemano.

Un aspecto importante de esta clase es que, como hemos mencionado, internamente mantiene ordenados los elementos. Por lo mismo, es necesario poder contar con una forma de controlar el cómo comparar elementos, y es por ello que el constructor de OrderedDictionary admite una interfaz de tipo IEqualityComparer. Esta interfaz nos permite comparar dos objetos, además de obtener un código hash para alguno de ellos. A través de esto, podemos controlar cómo la colección ordena sus elementos. Por ejemplo, si las llaves son cadenas de texto (como en el ejemplo) podríamos crear una clase que implemente dicha interfaz para que las comparaciones se hicieran sin distinguir entre mayúsculas y minúsculas. Por ejemplo:

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class StringComparer : IEqualityComparer
    {
        public StringComparer()
        {
        }

        public bool Equals(object x, object y)
        {
            string xstr = x as string;
            string ystr = y as string;

            return xstr.Equals(ystr, StringComparison.InvariantCultureIgnoreCase);
        }

        public int GetHashCode(object obj)
        {
            string str = obj as string;
            str = str.ToUpper();

            return str.GetHashCode();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StringComparer comparer = new StringComparer();
            OrderedDictionary dic = new OrderedDictionary(comparer);
            dic.Add("John", "Imagine");
            dic.Add("Ringo", "Photograph");
            dic.Add("Paul", "Another day");
            dic.Add("George", "My sweet lord");

            for (int i = 0; i < dic.Count; i++)
            {
                Console.WriteLine("{0} - {1}", i, dic[i]);
            }

            Console.ReadKey(true);
        }
    }
}

La clase StringComparer que creamos compara dos cadenas de texto sin distinguir entre mayúsculas y minúsculas (método Equals), mientras que GetHashCode regresa el código hash de la cadena de texto en mayúsculas, de tal suerte que “John”, “JOHN” y “john” regresen el mismo código. Y ahora sí, inicializamos nuestro OrderedDictionary con una instancia de este comparador.

A lo largo de esta entrada analizamos los tres diccionarios especializados que nos ofrece .NET, cada uno con sus ventajas, virtudes y desventajas. Vimos cómo ListDictionary y HybridDictionary nos pueden ayudar a optimizar nuestro código, mientras que OrderedDictionary nos permite acceder a valores mediante un índice, sin necesidad de conocer las llaves de antemano. Así las cosas, la regla a seguir pudiera expresarse así. Si un diccionario tiene un número bajo de elementos, ListDictionary es la opción con mejor rendimiento. Si el diccionario tiene un número inicial bajo de elementos, pero es posible que éste crezca, la mejor opción es utilizar HybridDictionary. Por otra parte, si el número de elementos inicial es alto, es mejor utilizar Hashtable desde un principio. Finalmente, si tenemos un diccionario cuyas llaves no son conocidas, o en algún punto no se tiene alguna forma de inferirlas, podemos optar por emplear OrderedDictionary, que nos provee esta funcionalidad.

Después de leer esta entrada, pudieras pensar que a final de cuentas los tres diccionarios especializados son una pérdida de tiempo. Al fin y al cabo, Hashtable puede hacer todo el trabajo, y quizás una diferencia de dos segundos no parezca significativa para un programa de negocios tradicional. Pero estas tres clases muestran la riqueza del .NET Framework, dado que proveen opciones para escenarios muy específicos. Y ciertamente, vale la pena, creo, conocerlos para poder sacarles provecho cuando nos encontremos en una situación similar.

Ahora que por supuesto, estos tres diccionarios no son los únicos que hay. En entradas futuras veremos otros tipos de diccionarios diseñados para otras situaciones específicas, pero también algunos de propósito general. No te pierdas las siguientes entradas en la serie, para conocer más sobre este fascinante y amplio tema de las colecciones en .NET.

Categorías:.NET Framework, C#, Tutorial Etiquetas:
  1. Natalia
    enero 4, 2012 a las 10:40 am

    Muchas gracias! Me ha sido muy útil

  1. No trackbacks yet.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s