Какие структуры данных могут эффективно хранить 2-е данные “сетки”?
@Hank Gay
Как продолжение моего собственного (довольно бесполезного) комментария: Находка похожа на способ пойти. Если по любой причине Вы хотели придерживаться стандартного JDK, ConcurrentMap и , AtomicLong может сделать код крошечным , укусил более хороший, хотя YMMV.
final ConcurrentMap map = new ConcurrentHashMap();
map.putIfAbsent("foo", new AtomicLong(0));
map.get("foo").incrementAndGet();
уедет 1 как значение в карте для foo. Реалистично, увеличенное дружелюбие к поточной обработке - все, что этот подход должен рекомендовать его.
5 ответов
Вот несколько подходов. Я (попытаюсь) проиллюстрировать эти примеры представлением сетки 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-й двусвязный список)
+---+ +---+ +---+
| 0 |-->| 1 |-->| 2 |
| |<--| |<--| |
+---+ +---+ +---+
^ | ^ | ^ |
| v | v | v
+---+ +---+ +---+
| 3 |-->| 4 |-->| 5 |
| |<--| |<--| |
+---+ +---+ +---+
^ | ^ | ^ |
| v | v | v
+---+ +---+ +---+
| 6 |-->| 7 |-->| 8 |
| |<--| |<--| |
+---+ +---+ +---+
В этом методе каждая ячейка содержит до четырех указателей на соседние элементы. Доступ к соседним элементам осуществляется через соответствующий указатель. Вам все равно нужно будет сохранить структуру указателей на элементы (возможно, используя один из вышеперечисленных методов), чтобы избежать необходимости последовательно проходить каждый связанный список. Этот метод немного громоздок, однако он имеет важное применение в алгоритме Танцующих ссылок Кнута , где ссылки изменяются во время выполнения алгоритма, чтобы пропускать «пустое» пространство в сетке.
Вам все равно нужно будет сохранить структуру указателей на элементы (возможно, используя один из вышеперечисленных методов), чтобы избежать последовательного просмотра каждого связанного списка. Этот метод немного громоздок, однако он имеет важное применение в алгоритме Танцующих ссылок Кнута , где ссылки изменяются во время выполнения алгоритма, чтобы пропускать «пустое» пространство в сетке. Вам все равно нужно будет сохранить структуру указателей на элементы (возможно, используя один из вышеперечисленных методов), чтобы избежать последовательного просмотра каждого связанного списка. Этот метод немного громоздок, однако он имеет важное применение в алгоритме Танцующих ссылок Кнута , где ссылки изменяются во время выполнения алгоритма, чтобы пропускать «пустое» пространство в сетке.Вы должны абстрагироваться от того, как вы храните свои данные. Если вам нужно выполнять относительные операции внутри массива, Slice - это обычный шаблон для этого. У вас может быть что-то вроде этого:
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]; }
}
}
В дополнение к моему комментарию вас может заинтересовать алгоритм Hashlife .
По сути (если я правильно понимаю), вы храните свои данные в дереве квадратов с хеш-таблицей, указывающей на узлы дерева. Идея здесь в том, что один и тот же шаблон может встречаться в вашей сетке более одного раза, и каждая копия будет иметь одно и то же значение, поэтому вам нужно вычислить его только один раз.
Это верно для Life, которая представляет собой сетку из в основном ложные логические значения. Верно ли это для вашей проблемы, я не знаю.
Если для вас важно время поиска, то двумерный массив может быть вашим лучшим выбором, поскольку поиск соседей ячейки - это операция с постоянным временем, учитывая координаты (x, y) ячейка.
Динамически выделяемый массив массивов упрощает указание на ячейку над текущей ячейкой, а также поддерживает произвольные размеры сетки.