什么数据结构可以高效地存储2D“网格”数据？

Question

我正在尝试编写一个应用程序，对一组数字的网格执行操作。每次函数运行时，每个单元格的值都会更改，并且每个单元格的值都取决于其邻居的值。每个单元格的值将是一个简单的整数。

在这里存储数据的最佳方式是什么？我考虑了使用平面列表/数组结构，但这似乎不太有效，因为我必须反复计算出哪个单元格在当前单元格的“上方”（当网格大小是任意的时候），以及嵌套列表，它似乎不是表示数据的很好的方式。

我无法摆脱这种感觉，即在内存中表示此类目的的更好方法必须存在。有什么想法吗？

（请注意，我认为这确实不是主观问题，但 stack overflow 似乎认为它是...我希望有一种被接受的方式来存储这种数据）

- Elliot Hughes

---

在大多数情况下，要求以“最佳”方式执行某些操作是主观的。但我认为在这种情况下，它非常明确。 - Matthew Scharley

你正在做的很像细胞自动机。你可以在你喜欢的编程语言中查找Conway's Life的开源实现，看看他们是怎么做的。 - John Fouhy

Answer 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维数组类似，通过调整适当的索引来访问相邻的元素。

完全链接单元格（2D双向链表）

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

这种方法使每个单元格最多包含四个指向其相邻元素的指针。通过适当的指针可以访问相邻元素。您仍需要保留一个指向元素的指针结构（可能使用上述方法之一），以避免必须按顺序遍历每个链接列表。虽然这种方法有点笨重，但它在Knuth's Dancing Links算法中具有重要应用，在该算法的执行过程中修改链接以跳过网格中的“空白”区域。

- Greg Hewgill

---

哇，太棒了，伙计。你付出了真正不错的努力来回答这个问题。+1 - Tarik

“二维数组”（2da）比“数组的数组”（aoa）解决方案更快吗？它们似乎在做同样的事情，但是用两种不同的方式。第二个（aoa）似乎需要2次查找操作，但是第一个（2da）呢？它也需要2次操作吗？ - Sebastian Norr

@SebastianNorr 这几乎肯定是与编程语言有关的。我检查了Python，因为那是我知道的，我发现访问10000x10000 ndarray（2da）中间元素的时间大约是访问10000x10000列表的列表（aoa）中间元素的两倍半左右。这是一个非常粗略的速度测试，很可能在不同的系统上甚至使用不同的编程语言时会有所不同。 - realityChemist

Answer 2

如果查找时间对您很重要，那么二维数组可能是最好的选择，因为在给定单元格的（x，y）坐标的情况下，查找单元格的邻居是一个常数时间操作。

- bstamour

---

在 John 的答案正确的情况下，我会支持 +1，但是根据语言，二维数组和数组的数组（锯齿状数组）之间存在差别。大多数语言中，数组的数组很难使用，因为它们不直接支持二维数组。 - Matthew Scharley

+1 - 计算“确定当前单元格上方的单元格”的量是微不足道的 - 它与解除指针引用并没有太大的区别，而数组的开销也远远不及其他更复杂链接结构。 - Amber

Answer 3

针对我的评论，你可能会发现Hashlife算法很有趣。

本质上（如果我理解正确的话），你可以在四叉树中存储数据，并使用哈希表指向树的节点。这里的想法是相同的模式可能会在网格中出现多次，每个副本都将哈希到相同的值，因此你只需要计算一次。

这对于Life（大部分为false的布尔网格）是正确的。至于对于你的问题是否正确，我不知道。

- John Fouhy

Answer 4

你应该抽象出数据存储的方式。 如果你需要在数组内进行相关操作，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]; }
    }
}

- Konstantin Spirin

Answer 5

动态分配的数组使得指向当前单元格上方的单元格变得轻而易举，并支持任意网格大小。

- John Lockwood