Bạn có thể sử dụng chỉ mục dựa trên [hàng, col] của ô. Vì dữ liệu nằm trên đường chéo, cách tiếp cận điển hình để lưu trữ chỉ mục hàng và phân đoạn cột được liên kết với dữ liệu không phải là tối ưu. Dưới đây là một số mã bạn có thể sử dụng để làm điều đó:
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();
}
Lưu ý rằng khi T là một cấu trúc, bạn có thể phải gọi IsCellEmpty kể từ khi nhận được nội dung của một tế bào sẽ không được null và sẽ có giá trị mặc định cho loại đó. Bạn cũng có thể mở rộng mã để cung cấp cho bạn một "SparseRatio" nhanh chóng dựa trên thuộc tính Size và _cells.Count.
EDIT:
Vâng, nếu bạn thú vị là tốc độ, bạn có thể thực hiện giao dịch không gian so với tốc độ. Thay vì chỉ có một từ điển, có ba từ! Nó tăng gấp ba không gian của bạn, nhưng nó làm cho liệt kê theo bất kỳ cách nào bạn muốn thực sự dễ dàng. Dưới đây là một số mã mới cho thấy rằng:
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;
}
}
Nếu bạn muốn lặp qua tất cả các mục nhập, hãy sử dụng _cells. Nếu bạn muốn tất cả các hàng cho một cột nhất định sử dụng _columns. Nếu bạn muốn tất cả các cột trong một hàng nhất định sử dụng _rows.
Nếu bạn muốn lặp lại theo thứ tự sắp xếp, bạn có thể bắt đầu thêm LINQ vào danh sách kết hợp và/hoặc sử dụng danh sách được sắp xếp với lớp bên trong đóng gói một mục nhập (có thể lưu trữ hàng hoặc cột và triển khai IComparable<T> để sắp xếp hoạt động).
Tôi đã cập nhật câu trả lời của mình. Vậy hiệu quả hoạt động có quan trọng hơn hiệu quả không gian? Bạn nói "cách hiệu quả để xử lý các ma trận thưa thớt" và trong các trường hợp sử dụng của bạn, hãy nói về nhiều cách để truy cập dữ liệu. –
Tôi cho rằng hiệu suất là quan trọng hơn hiệu quả của không gian. Chúng tôi sẽ xử lý một lượng lớn dữ liệu anyways vì vậy tôi không nhớ sử dụng nhiều không gian cho ma trận miễn là nó đi nhanh hơn –