Какие структуры данных могут эффективно хранить 2-х "сетчатые" данные?

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

Каким будет лучший способ хранения моих данных здесь? Я рассмотрел как структуру плоского списка/массива, но это кажется неэффективным, поскольку я должен многократно выполнять вычисления, чтобы определить, какая ячейка находится "выше" текущей ячейки (при наличии произвольного размера сетки) и вложенных списков, что не Кажется, это очень хороший способ представления данных.

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

(заметьте, я не думаю, что это действительно субъективный вопрос, но переполнение стека кажется, что это так.. Я очень надеюсь, что там принят способ хранения таких данных)

Ответ 1

Вот несколько подходов. Я попытаюсь проиллюстрировать эти примеры представлением сетки 3x3.

Плоский массив

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+

a[row*width + column]

Чтобы получить доступ к элементам слева или справа, вычтите или добавьте 1 (позаботьтесь о границах строк). Чтобы получить доступ к элементам выше или ниже, вычтите или добавьте размер строки (в этом случае 3).

Двумерный массив (для таких языков, как C или FORTRAN, которые поддерживают это)

+-----+-----+-----+
| 0,0 | 0,1 | 0,2 |
+-----+-----+-----+
| 1,0 | 1,1 | 1,2 |
+-----+-----+-----+
| 2,0 | 2,1 | 2,2 |
+-----+-----+-----+

a[row,column]
a[row][column]

Доступ к соседним элементам просто увеличивает или уменьшает число строк или столбцов. Компилятор по-прежнему выполняет ту же арифметику, что и в плоском массиве.

Массив массивов (например, Java)

+---+   +---+---+---+
| 0 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 1 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 2 |-->| 0 | 1 | 2 |
+---+   +---+---+---+

a[row][column]

В этом методе список указателей строк (представленных слева) представляет собой новый независимый массив. Подобно 2-мерному массиву, доступ к смежным элементам осуществляется путем настройки соответствующего индекса.

Полностью связанные ячейки (2-й двусвязный список)

+---+   +---+   +---+
| 0 |-->| 1 |-->| 2 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 3 |-->| 4 |-->| 5 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 6 |-->| 7 |-->| 8 |
|   |<--|   |<--|   |
+---+   +---+   +---+

Этот метод содержит каждую ячейку, содержащую до четырех указателей на ее соседние элементы. Доступ к соседним элементам осуществляется через соответствующий указатель. Вам нужно будет сохранить структуру указателей на элементы (возможно, используя один из вышеуказанных методов), чтобы избежать необходимости последовательно проходить через каждый связанный список. Этот метод немного громоздкий, однако он имеет важное приложение в алгоритме Knuth Dancing Links, где ссылки изменяются во время выполнения алгоритма до пропустите "пустое" пространство в сетке.

Ответ 2

Если для вас важно время поиска, тогда вам может понадобиться двумерный массив, так как поиск соседей сотовой ячейки - это операция с постоянным временем, заданная координатами (x, y) ячейки.

Ответ 3

Динамически распределенный массив массивов делает тривиальным указание на ячейку над текущей ячейкой и поддерживает произвольные размеры сетки.

Ответ 4

В дополнение к моему комментарию вы можете найти Hashlife алгоритм.

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

Это верно для Жизни, которая представляет собой сетку в основном-ложных булевых. Верно ли это для вашей проблемы, я не знаю.

Ответ 5

Вы должны абстрагироваться от того, как вы храните свои данные. Если вам нужно выполнять относительные операции внутри массива, Slice - это общий patterd для этого. У вас может быть что-то вроде этого:

public interface IArray2D<T>
{
    T this[int x, int y] { get; }
}

public class Array2D<T> : IArray2D<T>
{
    readonly T[] _values;
    public readonly int Width;
    public readonly int Height;

    public Array2D(int width, int height)
    {
        Width = width;
        Height = height;
        _values = new T[width * height];
    }

    public T this[int x, int y]
    {
        get
        {
            Debug.Assert(x >= 0);
            Debug.Assert(x < Width);
            Debug.Assert(y >= 0);
            Debug.Assert(y < Height);

            return _values[y * Width + x];
        }
    }

    public Slice<T> Slice(int x0, int y0)
    {
        return new Slice<T>(this, x0, y0);
    }
}

public class Slice<T> : IArray2D<T>
{
    readonly IArray2D<T> _underlying;
    readonly int _x0;
    readonly int _y0;

    public Slice(IArray2D<T> underlying, int x0, int y0)
    {
        _underlying = underlying;
        _x0 = x0;
        _y0 = y0;
    }

    public T this[int x, int y]
    {
        get { return _underlying[_x0 + x, _y0 + y]; }
    }
}