java - 现代文本编辑器中Piece Table和Rope的内存管理

Question

我知道我们可以使用两个堆栈来为文本编辑器实现撤消/重做。对于 Piece Table，您可以简单地将受影响的节点插入堆栈，如前所述 here (顺便说一句，关于 Piece Table 的文章很棒)。对于 Rope，我的理解是，由于 Rope 应该是不可变的，只要有变化，只需将旧树的根压入堆栈，如前所述 here :

“不仅可以在非常大的文档中以近乎恒定的时间执行文本插入和删除，而且绳索的不变性使得撤消堆栈的实现变得微不足道:只需存储对前一个绳索的引用每一个变化。“

如果是这种情况，那么 Rope 似乎非常占用内存，并且在几次修改后可以很快用一个大文件填满您的内存。这在现代文本编辑器中是如何处理的？

这就引出了另一个问题:如果有一个5​​GB的文件，而你只有2GB的内存，你会怎么做？我在想也许使用分页或动态加载，所以当你向下滚动时，它会丢弃内存中的一些旧文本并从磁盘加载更多。那么在Piece Table and Rope中是如何实现的呢？当我们加载更多内容并将其放入我们的数据结构时，也许我们可以将数据结构的较旧部分序列化到磁盘上，但这对我来说似乎不是最佳解决方案。

干杯!

Answer 1

不可变对象(immutable对象)的主要优点之一是它们可以相互共享结构。因为结构永远不会改变，所以不需要复制整个结构；只有受修改影响的部分需要复制。这意味着每次添加只需要相对少量的内存。这是如何用另一种树状结构实现的很好的解释:Understanding Clojure's Persistent Vector .

即使进行了内存节省优化，不适合 RAM 或程序允许的内存空间的超大文件仍然会造成问题。为了解决这个问题，文本编辑器将存储文件中未直接编辑的部分 swap file .一些编辑器使用他们自己的虚拟内存实现来实现这一点，而其他人则只选择文件中离光标足够远的部分。作为一个(假设的)示例，如果在一定时间内未对其进行任何修改，则可以将绳子的子树保存到文件中。