[셀의 행, 열]을 기준으로 색인을 사용할 수 있습니다. 데이터가 대각선에 있기 때문에 행 인덱스 및 관련 열 indeces를 데이터와 함께 저장하는 일반적인 방법은 최적이 아닙니다. T는 구조체 인 경우, 당신이 null이되지 않습니다 셀의 내용을 받고 이후 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();
}
참고하고 기본 값을가집니다 : 여기 당신이 그것을 할하는 데 사용할 수있는 몇 가지 코드입니다 그 타입에 대해서. 코드를 확장하여 Size 속성과 _cells.Count을 기반으로 한 빠른 "SparseRatio"를 제공 할 수도 있습니다.
편집 :
글쎄, 당신이 흥미있는 경우에 당신이 속도 대 공간의 트레이드 오프를 할 수있는 속도입니다. 사전이 하나만있는 대신 세 개를 가져라! 그것은 당신의 공간을 세배로 늘리지 만, 그것은 당신이 진정으로 쉽게 원하는 어떤 식 으로든 열거합니다. 당신은 모든 항목을 반복하려면
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>을 구현해야 함). 일하기 위하여 분류하기를 위해).
답을 업데이트했습니다. 공간 효율성보다 성능 효율성이 더 중요합니까? "희소 행렬을 효율적으로 처리 할 수있는 방법"이라고 말하면 사용 사례에서는 데이터에 액세스하는 여러 가지 방법에 대해 이야기합니다. –
필자는 성능이 공간 효율성보다 중요하다고 말할 것입니다. 우리는 매우 많은 양의 데이터를 처리 할 것이므로 매트릭스가 더 빨라지면 많은 공간을 사용하지 않아도됩니다. –