Introducción
Llamamos colecciones bidimensionales a aquellas que utilizan dos índices (i,j) para asociar a cada elemento una posición dentro de la colección. La mayoría de lenguajes de programación permite crear de forma nativa matrices bidimensionales ya sea como una única matriz de dos índices T[,] o como una superposición de matrices donde cada elemento de la matriz externa es a su vez otra matriz T[][]. La principal ventaja de este tipo de colecciones es que sus elementos están alojados de forma contigua en la memoria, permitiendo que se pueda recorrer rápidamente elemento a elemento. Sin embargo, aunque el hecho de que los elementos estén agrupados de forma compacta sea interesante desde el punto de vista del rendimiento a la hora de alojar y acceder a los elementos, el tamaño de las matrices queda fijado en el momento de su declaración, y la única forma de redimensionarlas es crear una nueva matriz con las nuevas dimensiones y copiar los elementos, haciendo que en determinados escenarios tengamos que buscar alternativas a este tipo de colecciones.
Aunque existen formas de reducir la dimensionalidad a una única coordenada si los índices son números enteros —por ejemplo, utilizando la Cantor pairing function—, consiguiendo en última instancia una estructura lineal, el problema que aquí nos ocupa es el de colecciones bidimensionales con dos índices independientes y no necesariamente enteros. Imaginemos que queremos almacenar un conjunto reducido de objetos basándonos en coordenadas (i,j) cuyas posiciones pueden tomar valores entre 0-999. Si quisiéramos utilizar una colección de tipo T[][] para este propósito tendríamos que generar una matriz externa de tamaño 1000, y, a su vez, generar 1000 matrices internas de tamaño 1000; es decir, una colección que podríamos representar como una única matriz cuadrada de 1000 x 1000 elementos. Si el conjunto de elementos es muy poco denso, es decir, si tenemos una colección dispersa, estaríamos generando una matriz enorme donde prácticamente todos los huecos estarían vacíos —más bien ocupados por null—. En este caso, nos interesaría generar una colección de tamaño variable que sólo almacenara los objetos necesarios asociados a sus coordenadas (i,j) sin crear espacios vacíos.
Por otro lado, las matrices usan como índices números enteros que van desde 0 hasta el tamaño-1 de la matriz —una matriz unidimensional de longitud 100 tendría como índices los números enteros entre 0 y 99— haciendo imposible su uso en situaciones donde necesitemos que los elementos estén indexados mediante cadenas de texto u otros elementos que no sean números. Si unimos este hecho a la cuestión de que el tamaño de las matrices queda fijado al ser declaradas se hace evidente el interés en crear estructuras de datos alternativas para colecciones bidimensionales dispersas.
Interfaz I2DCollection
La interfaz I2DCollection define los métodos comunes que deben implementar las distintas clases que representan colecciones bidimensionales. El uso de la interfaz permite exigir el uso de una clase que implemente I2DCollection sin fijar una clase concreta en situaciones complejas donde podría no estar claro cuál provee mejor rendimiento —unas implementaciones son más rápidas para hacer inserciones y cambios, mientras que otras son más rápidas para hacer lecturas de los elementos—.
interface I2DCollection<X,Y,T>
{
T TryGet(X x, Y y);
T Get(X x, Y y);
List<T> GetAllToList();
List<T> GetInXToList(X x);
List<T> GetInYToList(Y y);
void Put(X x, Y y, T value);
//Resto de declaraciones de la interfaz...
}
interface I2DCollection<T>
{
T TryGet(int x, int y);
T Get(int x, int y);
List<T> GetAllToList();
List<T> GetInXToList(int x);
List<T> GetInYToList(int y);
List<T> GetAnyInAreaToList(int x1, int x2, int y1, int y2);
void Put(int x, int y, T value);
//Resto de declaraciones de la interfaz...
}
Las clases propuestas como implementación de la interfaz son NestedDictionary y CoordinatedDictionary2D, que se dan en dos versiones: una con índices genéricos que implementaría I2DCollection<X,Y,T> y otra con índices enteros no genéricos I2DCollection<T>.
NestedDictionary
Definimos la clase NestedDictionary<X,Y,T> como una colección genérica donde X y Y hacen referencia a los tipos que serán utilizados como índices —no tienen por qué coincidir, el primero podría ser un String, y el segundo un int— y T al tipo de los objetos que almacena la colección. NestedDictionary es una clase que envuelve a una estructura anidada de diccionarios genéricos: Dicionary<X, Dictionary<Y,T>>. NestedDictionary provee de métodos para acceder, modificar y buscar dentro del diccionario anidado y permite un rápido acceso a costa de un mayor uso de memoria dado que se estaría creando un diccionario interno Dictionary<Y,T> por cada valor de la clave externa X. La versión con índices no genéricos sería más cercana a una versión de la matriz bidimensional T[,] o T[][] y permite, además de todo lo disponible en la versión de índices genéricos <X,Y >, búsquedas en área.
La implementación de la interfaz I2DCollection<X,Y,T> requiere un método T TryGet(X i, Y j) que en el caso de la versión de índices no genéricos se puede implementar en la forma:
public T TryGet(int x, int y)
{
T value = default(T);
Dictionary<int, T> inner;
if (nestedDictionary.TryGetValue(x, out inner))
{
if (inner.TryGetValue(y, out value))
{
return value;
}
}
return value;
}
Por otro lado, para realizar búsquedas en área sobre la colección bidimensional se proveen dos métodos cuyo rendimiento es mejor o peor en función de la densidad de objetos almacenados y será detallado en posteriores artículos. Uno de ellos obtiene todos los elemenentos encerrados en un área determinada y los almacena en una lista:
public List<T> GetAnyInAreaToList(int x1, int x2, int y1, int y2)
{
List<T> result = new List<T>();
foreach (KeyValuePair<int, Dictionary<int, T>> outkv in nestedDictionary)
{
if (outkv.Key >= x1 && outkv.Key <= x2)
{
foreach (KeyValuePair<int, T> inkv in outkv.Value)
{
if (inkv.Key >= y1 && inkv.Key <= y2)
{
result.Add(inkv.Value);
}
}
}
}
return result;
}
El segundo método hace uso del método Dictionary.ContainsKey() para realizar la misma operación:
public List<T> GetAnyInAreaToListContains(int x1, int x2, int y1, int y2)
{
List<T> result = new List<T>();
Dictionary<int, T> inner;
for (int i = x1; i <= x2; i++)
{
if (nestedDictionary.ContainsKey(i))
{
inner = nestedDictionary[i];
for (int j = y1; j <= y2; j++)
{
if (inner.ContainsKey(j))
result.Add(inner[j]);
}
}
}
return result;
}
CoordinatedDictionary2D
De forma análoga, definimos la clases CoordinatedDictionary2D<T> : I2DCollection<T> y CoordinatedDictionary2D<X,Y,T> : I2DCollection<X,Y,T> como implementaciones de las correspondientes interfaces. La principal diferencia de esta implementación respecto a NestedDictionary es que en este caso no se usa una estructura de diccionarios anidados como colección donde almacenar datos sino un único diccionario que utiliza como Key una struct llamada Point2D que envuelve el par de coordenadas que da nombre a esta clase:
public struct Point2D
{
public int i { get; set; }
public int j { get; set; }
public Point2D(int i, int j)
{
this.i = i;
this.j = j;
}
//override Equals(object obj)
//GetHashCode()...
}
Y la versión para coordenadas genéricas:
public struct Point2D<I,J>
{
public I i { get; set; }
public J j { get; set; }
public Point2D(I i, J j)
{
this.i = i;
this.j = j;
}
//override Equals(object obj)
//GetHashCode()...
}
Al igual que en el caso anterior, la implementación de la interfaz requiere un método T TryGet(X i, Y j) que detallamos para la versión con índices enteros:
public T TryGet(int x, int y)
{
Point2D point = new Point2D(x, y);
T value = default(T);
if (dictionary.TryGetValue(point, out value))
{
return value;
}
return value;
}
Finalmente, mostramos una posible implementación de la búsqueda en área en analogía con el método correspondiente de NestedDictionary.
public List<T> GetAnyInAreaToList(int x1, int x2, int y1, int y2)
{
List<T> result = new List<T>();
Point2D point;
foreach (KeyValuePair<Point2D, T> pair in dictionary)
{
point = pair.Key;
if (point.i >= x1 && point.i <= x2)
{
if (point.j >= y1 && point.j <= y2)
{
result.Add(pair.Value);
}
}
}
return result;
}
Con estas definiciones sentamos las bases de dos posibles implementaciones de Colecciones Bidimensionales para escenarios de baja densidad que pasaremos a comparar en posteriores artículos.
Gonzalo García Martínez 
2 comentarios
Los comentarios están cerrados.