Se podría utilizar un índice basado en el [fila, columna] de la célula. Dado que los datos están en diagonal, el enfoque típico de almacenar el índice de fila y los datos de columna asociados con los datos no es óptimo. Aquí hay un código que puede utilizar para hacerlo:
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long Size { get; private set; }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.Size = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
}
}
}
static void Main()
{
var sm = new SparseMatrix<int>(512, 512);
sm[42, 42] = 42;
int val1 = sm[13, 13];
int val2 = sm[42, 42];
Console.WriteLine("VAL1 = " + val1); // prints out 0
Console.WriteLine("VAL2 = " + val2); // prints out 42
Console.ReadLine();
}
Tenga en cuenta que cuando T es una estructura, es posible que tenga que llamar a la IsCellEmpty desde conseguir el contenido de una celda no será nulo y tendrá el valor por defecto para ese tipo. También puede expandir el código para darle un "SparseRatio" rápido basado en la propiedad Size y _cells.Count.
EDIT:
Bueno, si usted es interesante es la velocidad, que puede hacer la compensación del espacio vs velocidad. ¡En lugar de tener solo un diccionario, tiene tres! Triplica tu espacio, pero hace que la enumeración de la forma que quieras sea realmente fácil. Aquí está un nuevo código que muestra que:
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long MaxSize { get; private set; }
public long Count { get { return _cells.Count; } }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
private Dictionary<int, Dictionary<int, T>> _rows =
new Dictionary<int, Dictionary<int, T>>();
private Dictionary<int, Dictionary<int, T>> _columns =
new Dictionary<int, Dictionary<int, T>>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.MaxSize = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
UpdateValue(col, row, _columns, value);
UpdateValue(row, col, _rows, value);
}
}
private void UpdateValue(int index1, int index2,
Dictionary<int, Dictionary<int, T>> parent, T value)
{
Dictionary<int, T> dict;
if (!parent.TryGetValue(index1, out dict))
{
parent[index2] = dict = new Dictionary<int, T>();
}
dict[index2] = value;
}
}
Si desea iterar sobre todas las entradas, utilice _cells. Si desea todas las filas para una columna determinada, use _columns. Si desea todas las columnas en una fila determinada, use _rows.
Si desea iterar en orden ordenado, puede comenzar a agregar LINQ en la mezcla y/o utilizar una lista ordenada con una clase interna que encapsula una entrada (que debería almacenar la fila o columna e implementar IComparable<T> para clasificar para trabajar).
He actualizado mi respuesta. Entonces, ¿la eficiencia del rendimiento es más importante que la eficiencia del espacio? Usted dice "forma eficiente de manejar matrices dispersas" y luego en sus casos de uso habla sobre múltiples formas de acceder a los datos. –
Yo diría que el rendimiento es más importante que la eficiencia del espacio. Manejaremos grandes cantidades de datos de todos modos, así que no me importa usar mucho espacio para la matriz, siempre que vaya más rápido –