Вы можете использовать индекс, основанный на [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 является структурой, вам может потребоваться вызвать IsCellEmpty, поскольку получение содержимого ячейки не будет нулевым и будет иметь значение по умолчанию для этого типа. Вы также можете расширить код, чтобы получить быстрое «SparseRatio» на основе свойства Size и _cells.Count.
РЕДАКТИРОВАТЬ:
Что ж, если вам интересна скорость, вы можете найти компромисс между пространством и скоростью. Вместо одного словаря используйте три! Это втрое увеличивает ваше пространство, но делает перечисление любым удобным для вас способом. Вот новый код, который показывает, что:
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> для сортировки для работы ).
person
Erich Mirabal
schedule
16.04.2009
