2

显然,在实现通用文本编辑器时(例如,通用我的意思是它不必能够处理大文件(超过 100-200 MB(这仍然很多,更像是“一般情况”的极端示例)),仅将文本存储在一个连续的长缓冲区中是不可行的,因为插入/删除会降低性能。

虽然有很多方法可以解决这个问题,但它们都围绕着这样一个事实,即您必须将文本分成块,所以我的问题是:考虑到今天的计算机能力,最佳的块大小是多少?文本缓冲区的实际大小实际上开始变得太大而无法存储在简单的连续缓冲区中?当代计算机移动大块字节的速度有多快?(为了清楚起见,我们只说不能使用间隙缓冲区,每个块将是一个简单的连续数组。)

4

3 回答 3

3

在 Eclipse 中,几乎所有的编辑器都是使用GapTextStore.

GapTextStoreJaveDoc 中用于状态的有趣部分:

实现间隙管理文本存储。间隙文本存储依赖于对文档的连续更改位于同一位置的假设。间隙的起点始终移动到最后一次更改的位置。

性能:除非需要重新分配,否则键入样式的更改会在恒定时间内执行。一般来说,不引起重新分配的变化最多会引起一个长度约为d的arraycopy操作,其中d是与前一次变化的距离。设 a(x) 为长度为 x 的数组复制操作的算法性能,然后这样的更改在 O(a(x)) 中执行,get(int, length) 在 O(a(length)) 中执行,得到(int) 在 O(1) 中。

数组需要重新分配的频率由构造函数参数控制。

于 2012-05-13T19:05:26.140 回答
1

典型的消费系统可以在 DDR3 内存上实现 10 到 30 GB/s 的原始内存吞吐量。那是一种基数。

根据我的经验,我认为可以安全地假设在 Java 中实现每秒大约 100 MB 的内存操作没有问题(C++ 可能可以做到 4-8 倍)。由此看来,如果缓冲区大小为 64kb,您可以每秒进行 2^10 次操作,但仍然可以。

于 2012-05-13T19:31:13.927 回答
0

您应该阅读称为“绳索”的数据结构(绳索当然是一种重量级字符串)。最初的SGI STL 有它们以及字符串,虽然它们没有进入 C++ 标准库,但Gnu 将它们作为扩展

请注意,“块大小”在实现(注释)中不会像这样出现,这更多是关于以一种懒惰的、功能性的方式做事。

于 2012-05-13T20:33:59.557 回答