セルの[row、col]に基づくインデックスを使用できます。データが対角線上にあるので、行インデックスおよび関連する列インデクスをデータで保存する典型的なアプローチは最適ではありません。ここではあなたがそれを行うために使用できるいくつかのコードは次のとおりです。Tが構造体であるとき、あなたは、セルの内容を取得して以来、IsCellEmptyを呼び出すために必要がある場合がありますことを
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();
}
注意がnullではありませんし、デフォルト値を持っていますそのタイプのSize
プロパティと_cells.Count
に基づいた簡単な "SparseRatio"コードを展開することもできます。
EDIT:
さて、あなたは興味深い場合は、スピード対スペースのトレードオフを行うことができ、速度です。辞書を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>
仕事を分類するため)。
私の回答が更新されました。スペース効率よりパフォーマンス効率が重要ですか?あなたは「スパース行列を効率的に処理する方法」と言い、ユースケースではデータへの複数のアクセス方法について話します。 –
私はパフォーマンスがスペース効率よりも重要だと言います。とにかく非常に大量のデータを扱うので、行列が高速になる限り多くのスペースを使っても構いません。 –