セルの [row,col] に基づくインデックスを使用できます。データは対角線上にあるため、行インデックスと関連する列インデックスをデータとともに格納する一般的な方法は最適ではありません。これを行うために使用できるコードを次に示します。
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();
}
T が構造体の場合、セルの内容を取得すると null にはならず、その型のデフォルト値を持つため、IsCellEmpty を呼び出す必要がある場合があることに注意してください。Size
コードを拡張して、プロパティ およびに基づいて簡単な「SparseRatio」を取得することもできます_cells.Count
。
編集:
速度に興味がある場合は、スペースと速度のトレードオフを行うことができます。辞書は 1 つだけではなく、3 つ持ってください。スペースが 3 倍になりますが、好きな方法で列挙するのが本当に簡単になります。以下は、次のことを示す新しいコードです。
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;
}
}
すべてのエントリを反復処理する場合は、 を使用します_cells
。特定の列のすべての行が必要な場合は、 を使用します_columns
。特定の行のすべての列が必要な場合は、 を使用します_rows
。
並べ替えられた順序で反復処理する場合は、LINQ をミックスに追加するか、エントリをカプセル化する内部クラスで並べ替えられたリストを使用することができます (行または列を格納し、IComparable<T>
並べ替えを機能させるために実装する必要があります)。 .