En el artículo anterior se expuso una descripción breve de dos posibles implementaciones de clases que definen colecciones para indexar objetos mediante dos índices independientes. Las colecciones propuestas, NestedDictionary y CoordinatedDictionary2D, son especialmente útiles cuando la densidad de objetos es baja; es decir, situaciones donde la representación matricial T[][] daría lugar a una matriz bidimensional prácticamente vacía.
En este artículo vamos a comparar el rendimiento de las colecciones propuestas bajo distintas operaciones de Inserción, Borrado y Búsqueda, comenzando por detallar las implementaciones de varios de estos métodos.
Métodos de Inserción y Borrado
Dos de las operaciones fundamentales en cualquier tipo de colección son la Inserción de nuevos elementos en la misma y el Borrado de elementos. En el caso de NestedDictionary, tanto la inserción como el borrado resultan en operaciones relativamente compleja dado que la estructura de diccionarios anidados implica realizar múltiples comprobaciones antes de incluir o eliminar el elemento. Una posible implementación del método de inserción podría ser:
public void Put(X x, Y y, T value)
{
Dictionary<Y, T> inner;
if (nestedDictionary.ContainsKey(x))
{
inner = nestedDictionary[x];
inner[y] = value;
}
else
{
inner = new Dictionary<Y, T>();
inner[y] = value;
nestedDictionary[x] = inner;
}
}
En primer lugar buscamos si el diccionario externo nestedDictionary contiene una entrada con Key = x. De ser así añadimos al diccionario interno Dictionary<Y,T> inner el valor deseado. En caso de no tener una entrada en el diccionario externo asociada al valor x, creamos un nuevo diccionario interno, añadimos el nuevo valor y asociamos el nuevo diccionario al diccionario externo para el valor x: nestedDictionary[x] = inner. Cabe señalar que esta es sólo una posible implementación para facilitar la legibilidad y que el código no está optimizado ya que podría usarse el método nestedDictionary.TryGetValue(x, out inner) aumentando el rendimiento y reduciendo el número de líneas.
Por el contrario, para el caso de la colección CoordinatedDictionary2D, la operación de inserción se reduce a:
public void Put(int x, int y, T value)
{
Point2D point = new Point2D(x, y);
dictionary[point] = value;
}
Es decir, creamos una instancia del struct Point2D, y añadimos directamente el valor al diccionario. Nótese que, en ambos casos, estamos realizado una inserción estricta en el diccionario; es decir, si hay previamente un objeto en esa posición será sustituido por el objeto a insertar.
Respecto a las operaciones de borrado, para el NestedDictionary tenemos:
public void Remove(int x, int y)
{
Dictionary inner;
if (nestedDictionary.TryGetValue(x, out inner))
{
inner.Remove(y);
if (inner.Count() == 0)
{
nestedDictionary.Remove(x);
}
}
}
De nuevo, al igual que en el caso de la inserción, se tiene que comprobar en primer lugar que exista un diccionario interno asociado al valor x; en este caso realizamos la búsqueda mediante nestedDictionary.TryGetValue(x, out inner). En el caso de existir pasamos a borrar la entrada asociada al valor y. Finalmente, debido a la estructura de diccionarios anidados, comprobamos si el diccionario interno se ha quedado sin entradas nestedDictionary.Remove(x); en caso de que sea así —si el diccionario interno que almacena las coordenadas y asociadas a un valor x queda sin entradas implicaría que no hay ninguna pareja de valores (x,y)— eliminamos la entrada del diccionario externo asociada al valor x nestedDictionary.Remove(x).
En el caso del CoordinatedDictionary2D tenemos, una vez más, una implementación mucho más sencilla al prescindir de una estructura de diccionarios anidados.
public void Remove(int x, int y)
{
Point2D point = new Point2D(x, y);
dictionary.Remove(point);
}
Comparación en el rendimiento de NestedDictionary y CoordinatedDictionary 2D
Si bien con lo expuesto hasta ahora se hace evidente que la colección CoordinatedDictionary2D es más sencilla de implementar y de mantener, la colección NestedDictionary es mucho más eficiente en los métodos de búsqueda de objectos almacenados tal y como se muestra en la siguiente tabla:
La operación GetAllToList es un método de control que se reduce a obtener todas las entradas de la colección y almacenarlas en una lista. Debido a la estructura anidada de NestedDictionary, es evidente que es más lenta de recorrer y de almacenar los elementos de los diccionarios internos que la colección CoordinatedDictionary2D.
Las operaciones de búsqueda en área muestran un comportamiento similar: la búsqueda que usa Dictionary.ContainsKey() es mucho más rápida, aunque esta tendencia no es siempre así y depende fuertemente del área de búsqueda y de la densidad de objetos almacenados —más detalles sobre esta operación en sucesivas entradas—. Sin embargo, comprobamos que tanto las búsquedas en área, como las búsquedas en línea —GetInX buscaría todos los puntos (x,y) con x fijado y variando los valores de y—, como en la búsqueda en un punto concreto, el rendimiento de NestedDictionary es muy superior.
La operación de inserción —en esta prueba de control se realizan 10.000 inserciones— puede ser más rápida en CoordinatedDictionary2D, tal y como se muestra en la tabla; no obstante, su comportamiento es complejo y varía con la densidad de datos y su distribución, pudiendo existir casos donde la inserción se realiza en unos tiempos prácticamente iguales y no existiendo diferencias notables con NestedDictionary.
Por tanto, a la vista de los resultados, podría parecer que la colección NestedDictionary es la clara vencedora para representar colecciones bidimensionales dispersas. En términos de rendimiento lo es, pero el impacto en memoria de una estructura de diccionarios anidados es muy superior al de un único diccionario utilizado en CoordinatedDictionary2D. Por tanto, en función del uso y del entorno donde se deba implementar, puede ser interesante utilizar una colección u otra atendiendo a las necesidades de cada caso.
Gonzalo García Martínez 