Vous pouvez utiliser un indice basé sur la [ligne, colonne] de la cellule. Comme les données sont en diagonale, l'approche typique consistant à stocker l'index de ligne et les indeces de colonne associés avec des données n'est pas optimale. Voici un code que vous pouvez utiliser pour le faire:
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();
}
Notez que lorsque T est un struct, vous pourriez avoir à appeler le IsCellEmpty depuis l'obtention du contenu d'une cellule ne sera pas nulle et aura la valeur par défaut pour ce type. Vous pouvez également développer le code pour obtenir un "SparseRatio" rapide basé sur la propriété Size et _cells.Count.
EDIT:
Eh bien, si vous êtes intéressant est la vitesse, vous pouvez faire le compromis de l'espace vs vitesse. Au lieu de n'avoir qu'un seul dictionnaire, en avoir trois! Il triple votre espace, mais il rend l'énumération de toute façon que vous voulez vraiment facile. Voici un nouveau code qui montre 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 vous voulez itérer sur toutes les entrées, utilisez _cells. Si vous voulez toutes les lignes pour une colonne donnée, utilisez _columns. Si vous voulez toutes les colonnes d'une ligne donnée, utilisez _rows. Si vous souhaitez effectuer une itération par ordre trié, vous pouvez commencer à ajouter LINQ au mélange et/ou utiliser une liste triée avec une classe interne qui encapsule une entrée (qui doit stocker la ligne ou la colonne et implémenter IComparable<T> pour trier au travail).
J'ai mis à jour ma réponse. L'efficacité de la performance est-elle plus importante que l'efficacité de l'espace? Vous dites "moyen efficace de gérer les matrices creuses" et ensuite dans vos cas d'utilisation, vous parlez de multiples façons d'accéder aux données. –
Je dirais que la performance est plus importante que l'efficacité de l'espace. Nous allons traiter de très grandes quantités de données, donc ça ne me dérange pas d'utiliser beaucoup d'espace pour la matrice tant que ça va plus vite –