在内存中保存大型可编辑文档的最佳方法

Question

我需要在内存中保存文档的表示,并且正在寻找最有效的方法来执行此操作.

假设

• 文档可能非常大,高达100MB.
• 通常情况下,文档将保持不变 - (即我不想进行不必要的预先处理).
• 更改通常在文档中彼此非常接近(即,作为用户类型).
• 应该可以快速应用更改(不复制整个文档)
• 更改将应用​​于偏移量和新/删除的文本(而不是行/列).
• 在C#中工作

目前的考虑

• 将数据存储为字符串.易于编码,设置快速,更新速度非常慢.
• 行数组,模式易于编码,设置较慢(因为我们必须将字符串解析为行),更新速度更快(因为我们可以轻松插入删除行,但查找偏移量需要求和行长度).

对于这种事情,必须有大量标准算法(这不是一百万英里的磁盘分配和碎片).

谢谢你的想法.

Answer 1

我建议将文件分成块。加载时所有块的长度都相同，但如果用户编辑这些块，每个块的长度可能会改变。如果用户在前面插入一个字节，这将避免移动 100 兆字节的数据。

要管理块，只需将它们 - 连同每个块的偏移量 - 放入一个列表中。如果用户修改了块长度，则必须仅更新此块之后的块的偏移量。要查找偏移量，您可以使用二进制搜索。

文件大小： 100 MiB
块大小： 16 kiB
块：6400

使用二进制搜索查找偏移量（最坏情况）： 13 个步骤
修改一个块（最坏情况）：复制 16384 字节数据并更新 6400 个块偏移量
修改一个块（平均情况）：复制 8192 字节数据并更新 3200 个块偏移量

16 kiB 块大小只是一个随机示例 - 您可以通过选择块大小来平衡操作成本，可能基于文件大小和操作概率。做一些简单的数学运算将产生最佳块大小。

加载将非常快，因为您加载固定大小的块，并且保存也应该表现良好，因为您将不得不写入几千块而不是数百万行。您可以通过仅按需加载块来优化加载，并且可以通过仅保存所有更改的块（内容或偏移量）来优化保存。

最后，实施也不会很难。您可以只使用StringBuilder该类来表示一个块。但是，对于长度与块大小相当或更大的非常长的行，此解决方案不能很好地工作，因为您将不得不加载许多块并仅显示一小部分，其余部分位于窗口的左侧或右侧。我假设在这种情况下您将不得不使用二维分区模型。

Answer 2

好数学，坏数学不久前写了一篇关于绳索和间隙缓冲区的优秀文章，详细介绍了在文本编辑器中表示文本文件的标准方法，甚至还比较了它们的实现简单性和性能。简而言之：间隙缓冲区 - 一个大型字符数组，紧随光标当前位置之后有一个空部分 - 是最简单也是最好的选择。