Реализация трехмерной разреженной матрицы?

Question

Я нашел довольно хорошую реализацию разреженной матрицы для c # более http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net.

Но так как я работаю в 3d-системе координат, мне нужна реализация разреженной матрицы, которую я могу использовать для отображения 3D-координированная система.

Подробности: Я храню большие объемы данных примитивных фигур в памяти, например, в кубах.У меня есть большое их количество (около 30 миллионов), и у меня есть много нулевых (ноль) записей вокруг.Учитывая, что каждая моя запись стоит 1 байт записи, я бы хотел реализовать разреженную матрицу, чтобы я мог достаточно экономить место в памяти.

Примечание. Быстрый доступ к ячейкам матрицы является довольно важным фактором дляменя, так что я буду торговать со скоростью, превышающей потребление памяти.

Answer 1

Решение Лассе Эспехолта практично, но его можно улучшить, удалив элементы, когда они обнуляются или обнуляются.Если вы не сделаете эту матрицу или массив может потерять разреженность.Вот альтернативное решение, которое предполагает, что если элемент какого-либо типа не был вставлен, то это тип по умолчанию для этого типа.Например, для double это означает 0,0, а для string это означает null.

public class Sparse3DArray<T>
{
  private Dictionary<Tuple<int, int, int>, T> data = new Dictionary<Tuple<int, int, int>, T>();

  public int Nnz { get { return data.Count; } }

  public T this[int x, int y, int z]
  {
    get
    {
      var key = new Tuple<int, int, int>(x, y, z);
      T value;
      data.TryGetValue(key, out value);
      return value;
    }

    set
    {
      var key = new Tuple<int, int, int>(x, y, z);
      if (null == value)
        data.Remove(key);
      else if (value.Equals(default(T)))
        data.Remove(key);
      else
       data[key] = value;
     }
   }
}

Answer 2

Очень простое решение, которое я только что принял, состоит в следующем:

public class Sparse3DMatrix<T>
{
    Dictionary<Tuple<int,int,int>, T> values = new Dictionary<Tuple<int, int, int>, T>();

    public T this[int x, int y, int z]
    {
        get { return values[new Tuple<int, int, int>(x, y, z)]; }
        set { values[new Tuple<int, int, int>(x, y, z)] = value; }
    }

    public bool ContainsKey(int x, int y, int z)
    {
        return values.ContainsKey(new Tuple<int, int, int>(x, y, z));
    }
}

использование:

var test = new Sparse3DMatrix<float>();
test[1, 1, 1] = 1f;
Console.WriteLine(test[1, 1, 1]);

Это можно расширить с помощью методов, подобных тем, которые есть в его версии, и проверками наx, y, z значения и т. Д.

Я уверен, что кто-то может что-то сказать о его производительности.Это будет достойная реализация, если вам действительно не нужно что-то для высокой производительности.Это зависит от реализации хеш-кода Tuple и вашего конкретного использования.Если мы предположим, что хэши хороши, у нас будет O(1) время поиска.Если вы знаете, что у вас будет много элементов, вы можете использовать new Dictionary<...>(initial capacity), чтобы избежать ненужного изменения размера при добавлении элементов.

В отличие от его , у него есть только один Dictionary со всеми предметами.У его версии есть словари словарей.Преимущество его в том, что если вам нужно сканировать всю строку, вы можете просто выполнить итерацию словаря второго уровня (это не поможет вам, если вы хотите сканировать столбцы), что быстрее, чем поиск отдельных элементов.Но наличие одного словаря означает меньшее использование памяти, особенно когда в строке мало элементов.

Answer 3

Я бы использовал словарь, но вместо ключа Tuple<int, int, int> вы можете использовать один длинный ключ в качестве ключа и использовать его для хранения координат (при условии, что они являются короткими).Это уменьшит объем используемой памяти и может даже повысить производительность.

private Dictionary<long, T> data = new Dictionary<long, T>();
private long GetKey(short x, short y, short z)
{
   return (x * 10000 + y) * 10000 + z;
}

Answer 4

Почему бы не использовать KD-Tree или аналогичную структуру данных (например, Octtree)?Есть отличные реализации C ++, например: FLANN

Answer 5

Тот факт, что вы работаете в трехмерной системе координат, не меняет, можете ли вы использовать эту структуру данных.Матрица для трехмерного пространства может содержаться с использованием разреженной матрицы, такой же, как двумерная матрица;меняются только записи.

Вы бы использовали разреженную матрицу для больших матриц с большим количеством нулевых записей.Это типично в дискретных представлениях проблем физики, которые приходят из конечно-разностных и конечно-элементных методов.У них есть полосы ненулевых элементов, сгруппированных по диагонали;записи вне диагональной полосы обычно равны нулю.Разреженная матрица не будет хранить их;необходимо разложить такие разложения, как LU и QR, чтобы знать, как справляться с разреженностью.

Эти матрицы могут описывать проблемы как в 2D, так и в 3D пространствах.

Я полагаю, что вы ошибаетесь, если выдумаю, вам нужна другая структура данных.