用于 Excel 克隆的正确数据结构

Question

假设我正在使用 C# 开发 Excel 克隆。 我的网格表示如下：

private struct CellValue
{
    private int column;
    private int row;
    private string text;
}
private List<CellValue> cellValues = new List<CellValue>();

每次用户添加文本时，我只是将其打包为 CellValue 并将其添加到 cellValues 中。 给定一个 CellValue 类型，我可以在 O(1) 时间内确定它的行和列，这很棒。 但是，给定一列和一行，我需要循环遍历整个 cellValues 来查找该列和行中的文本，这是非常慢的。 另外，给定一个文本，我也需要循环遍历整个内容。 是否有任何数据结构可以让我在 O(1) 时间内完成所有 3 个任务？

更新： 浏览了一些答案，我认为我没有找到我喜欢的答案。 我可以：

1. 不要保留超过 2 个 CellValue 副本，以避免同步它们。 在 C 世界中，我会很好地使用指针。
2. 行和列可以动态添加（与 Excel 不同）。

Answer 1

我认为您应该使用索引集合之一来使其工作得相当快，完美的一个是 KeyedCollection

您需要通过扩展此类来创建自己的集合。 这样，您的对象仍将包含行和列（因此您不会丢失任何内容），但您将能够搜索它们。 可能您必须创建一个封装（行，列）的类并使其成为键（因此使其不可变并覆盖 equals 并获取哈希码）

Answer 2

我将创建

 Collection<Collection<CellValue>> rowCellValues = new Collection<Collection<CellValue>>();

外部集合，

Collection<Collection<CellValue>> columnCellValues = new Collection<Collection<CellValue>>();

每一行或每一列都有一个条目，按行号或列号索引，内部集合包含该行或列中的所有单元格。 这些集合应作为创建新 CellValue 对象的过程的一部分进行填充。

rowCellValues[newCellValue.Row].Add(newCellValue);
columnCellValues[newCellValue.Column].Add(newCellValue);

Answer 3

这有点过早优化的味道。

也就是说，Excel 有一些功能对于选择良好的结构非常重要。

首先，Excel 以适度非线性的方式使用单元格。 求解公式的过程涉及以有效的随机顺序遍历电子表格。 该结构需要一种机制，可以轻松、廉价地查找随机键的值，将它们标记为脏的、已解析的或由于循环引用而无法解析的。 它还需要某种方式来知道何时不再有未解析的单元格，以便它可以停止工作。 任何涉及链表的解决方案可能都不是最佳的，因为它们需要线性扫描来获取这些单元格。

另一个问题是 Excel 一次显示一系列单元格。 这可能看起来微不足道，而且在很大程度上确实如此，但如果应用程序能够一次提取绘制一系列单元格所需的所有数据，那肯定是理想的。 其中一部分可能是跟踪行和列的显示高度和宽度，以便显示系统可以迭代该范围，直到收集到所需的单元格宽度和高度。 以这种方式迭代的需要可能会妨碍使用散列策略来进行单元的稀疏存储。

最重要的是，电子表格的表示模型存在一些弱点，可以通过采取稍微不同的方法来更有效地解决这些弱点。

例如，列聚合有点笨重。 在 Excel 中实现列总计很容易，但它有一种神奇的行为，在大多数情况下都有效，但并非总是有效。 例如，如果您将一行添加到聚合区域中，对该聚合的进一步计算可能会继续进行，也可能不会进行，具体取决于添加方式。 如果您复制并插入一行（并替换值），一切都会正常工作，但如果您将单元格剪切并粘贴到下一行，事情就不会那么顺利。

Answer 4

鉴于数据是二维的，我将有一个二维数组来保存它。

Answer 5

那么，您可以将它们存储在三个字典中：两个用于行和列的 Dictionary 对象，以及一个用于文本的 Dictionary 对象。 不过，您必须小心地使这三个部分保持同步。

我不确定我是否会选择一个大的二维数组......

Answer 6

如果它是精确克隆，则为 CellValue[256] 数组的数组支持列表。 Excel 有 256 列，但行数不断增加。

Answer 7

如果可以“动态”添加行和列，则不应将行/列存储为单元格的数字属性，而应存储为对行或列对象的引用。

示例：

private struct CellValue
{
  private List<CellValue> _column;
  private List<CellValue> _row;
  private string text;

  public List<CellValue> column {
     get { return _column; }
     set {
         if(_column!=null) { _column.Remove(this); }
         _column = value;
         _column.Add(this);
        }
     }

  public List<CellValue> row {
     get { return _row; }
     set {
         if(_row!=null) { _row.Remove(this); }
         _row = value;
         _row.Add(this);
        }
     }
}

private List<List<CellValue>> MyRows    = new List<List<CellValue>>;
private List<List<CellValue>> MyColumns = new List<List<CellValue>>;

每个 Row 和 Column 对象都实现为 CellValue 对象的列表。 这些是无序的——特定行中单元格的顺序与列索引不对应，反之亦然。

每个工作表都有一个行列表和一个列列表，按工作表的顺序排列（如上面所示为 MyRows 和 MyColumns）。

这将允许您重新排列和插入新的行和列，而无需循环和更新任何单元格。

删除行应循环遍历该行上的单元格，并在删除该行本身之前从各自的列中删除它们。 对于列来说反之亦然。

要查找特定的 Row 和 Column，请查找相应的 Row 和 Column 对象，然后查找它们共同包含的 CellValue。

示例：（

public CellValue GetCell(int rowIndex, int colIndex) {
  List<CellValue> row = MyRows[rowIndex];
  List<CellValue> col = MyColumns[colIndex];
  return row.Intersect(col)[0];
  }

我对 .NET 3.5 中的这些扩展方法有点模糊，但这应该是大概的情况。）

Answer 8

如果我没记错的话，可能在 80 年代初的 Byte 杂志上有一篇关于 Visicalc 如何做到这一点的文章。 我相信这是某种稀疏数组。 但我认为存在上下和左右的链接，因此任何给定的单元格都有一个指向其上方单元格（无论距离可能有多少单元格）、下方单元格、左侧单元格的指针，以及它的右侧。

Answer 9

我会选择稀疏数组（链表的链表），以最小的存储空间提供最大的灵活性。

在此示例中，您有一个行链接列表，其中每个元素都指向该行中的单元格链接列表（您可以根据需要反转单元格和行）。

 |
 V
+-+    +---+             +---+
|1| -> |1.1| ----------> |1.3| -:
+-+    +---+             +---+
 |
 V
+-+             +---+
|7| ----------> |7.2| -:
+-+             +---+
 |
 =

每个行元素都有行号，每个单元格元素都有一个指向其行元素的指针，因此从单元格获取行号的时间复杂度为 O(1)。

类似地，每个单元格元素都有其列号，也使得 O(1) 复杂度。

没有简单的方法可以让 O(1) 立即查找给定行/列的单元格，但是稀疏数组的速度是最快的，除非您为每个可能的单元格预先分配信息以便可以进行索引查找在数组上 - 这在存储方面会非常浪费。

您可以做的一件事是使一维非稀疏，例如使列成为主数组（而不是链接列表）并将它们限制为 1,000 - 这将使列查找索引（快速），然后在稀疏上进行搜索行。

我认为您不可能仅仅因为文本可以在多个单元格中重复（与行/列不同）而获得 O(1) 的文本查找。 我仍然相信稀疏数组将是搜索文本的最快方法，除非您在另一个数组中维护所有文本值的排序索引（同样，这可以使其更快，但会占用大量内存）。