网格数据结构

Question

4

通常，“可扩展”的网格被表示为列表，其中包含多个列表（行的列表，每一行有单元格的列表），这些列表是某种链表。

在这个数据结构中操作（删除、插入）行很容易且廉价，只需要重新链接上一个节点，但是当涉及到列时，例如删除一列，它就变成了一个非常耗时的操作，我需要“循环”所有行来删除那些索引单元格。显然，对于我的情况来说，这不是良好的行为。

我不是在讨论数据库；我找到的一个很好的例子是文本编辑器中的一些文本文件（据我所知），文本编辑器大多将文本分成行，并且删除行很容易。我希望删除列和删除某些行一样廉价和高效。

最后，我需要的是一些多维网格，但我认为任何2D简单网格都可以适用于MD，我是正确的吗？

- KA1

所以你想要对行和列进行O(1)删除？ - Keith Randall

是的，那就是我询问的内容。 - KA1

谢谢大家，我在下面所有的回答中都发现了非常有用的想法。但我不能真正推荐其中的任何一个。所有的回答都很棒，对于这样的问题需要仔细阅读。 - KA1

3个回答

1

保持现有的数据结构不变。此外，在创建每个列时，为其分配一个唯一的ID。当您删除该列时，只需将其ID添加到所有已删除列ID的哈希表中。每次遍历行时，请检查每个元素的列ID（需要与所有其他数据一起存储）是否与哈希表中的ID匹配，并在已删除时从行中剪切它。

如果您拥有每个网格元素都可以指向的每列数据结构，则哈希表和ID是不必要的。然后，您只需要在该数据结构中添加一个已删除位。

顺便说一下，Edmund的方案对您也很好。即使删除长度为n的行或列需要O（n）时间，您可以假定将该成本分摊到创建这些n个元素的成本上，使删除的平均时间为O（1）。

- Keith Randall

1

我知道“链表”通常从理论角度受到赞赏，但在实践中它们通常效率低下。

我建议使用随机访问容器来提高速度。最简单的是数组，但双端队列或索引跳表/B*树可能更好，这取决于我们所讨论的数据大小。

从概念上讲，它并没有太大变化，但您可以通过O(1)（数组，deque）/ O(log N)（跳表/B*树）操作移动到给定索引的位置，而不是使用简单链表的O(N)。

然后就是魔法时间了。

Keith已经介绍了基本思想：不是真正删除列，而是将其标记为已删除，然后在遍历结构时“跳”过它。但哈希表需要线性遍历才能到达第N列。使用Fenwick树将产生一种计算真实索引的有效方法，然后您可以直接跳转到那里。

请注意，将行标记为已删除的一个关键好处是显然可以进行“撤消”操作。

还要注意，您可能需要构建一个压缩函数，以便不时地消除已删除的列，而不是让它们积累。

- Matthieu M.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edmund · Accepted Answer

你可以使用一个二维的“链接矩阵”（我忘记了正确的术语）：

... Col 3 ... Col 4 ...
      |         |
... --X-- ... --Y-- ...
      |         |
...  ...  ...  ...  ...

每个单元格都有四个邻居，如图所示。此外，您需要行和列标题，这些标题可能指示行/列位置，并指向每行或每列的第一个单元格。最容易表示为没有上邻居的特殊单元格（用于列标题）。

在3和4之间插入新列意味着迭代下列3中的单元格X，并插入新的右邻居Z。这个新的单元格Z向左链接到X，向右链接到Y。您还需要添加新的列标题，并垂直链接新单元格。然后可以重新编号所有4之后的列的位置（列4变为列5）。

... Col 3 Col 4 Col 5 ...
      |     |     |
... --X-----Z-----Y-- ...
      |     |     |
...  ...   ...   ...  ...

插入列的成本为O（n），用于插入和链接新单元格，再次为更新列标题的O（m）。删除也是类似的过程。

因为每个单元格只有四个链接，所以行插入/删除使用相同的算法。