由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - text editor
相关主题
问一道A家的面试题问道关于LRU的题目
leetcode 上 wordladderII 求教大家有没有感觉,随着C++的淘汰linked list的问题越来越少了
发个evernote的code challenge发几个狗家onsite题
不明白leetcode OJ wordladder 2 总是 Time Limit Exceededleetcode #220很好
微软有组在招new grad software engineer吗?LRU适合在电面问吗?
今天Amazon的phone interview恭喜拿到Google的大offer
Topcoder与面试准备问一个数据结构的问题
今天没心情看书,上来聊聊我这1个半月都干嘛了amazon intern 3电
相关话题的讨论汇总
话题: 字符话题: 数据结构话题: piecetable话题: editor话题: piece
进入JobHunting版参与讨论
1 (共1页)
R**e
发帖数: 274
1
实现一个 text editor, 选用合适的数据结构,和 解释各种功能怎样实现。
估计占用的内存空间
thanks
y*********e
发帖数: 518
2
这个我以前写过一个notepad,大概解释一下数据结构吧。
我用的是C#写的(C#的string跟Java的string一样,是immutable的)。
这个数据结构应该支持如下功能:
1、快速的string读取,写入,以及删除
2、快速的获得某一个字符所在的行列号
3、支持较多的redo、undo
对于第一点要求,传统的string肯定不行,因为每次对string的修改都会产生一个新的
string。StringBuilder也不行,虽然它支持O(1)的Append,但是对于插入和删除最快
的还是O(N)。
考虑到第二点要求,可以用一个改进版的StringBuilder。即,每一行用一个
StringBuilder,然后行与行之间用LinkedList串联起来。这样做是假设每一行字符的
长度不会太长(大概百来个的字符删除O(N)还是很快的),然后行数也不会太长,因为
我们用的LinkedList把行数串联起来,要获得某一行的行号,也是O(N)的操作。
这就是第一版的数据结构,用它就可以实现一个简单的text editor,支持编辑不是很大
的文本文档。
这个数据结构可以改进的。我读了一些开源的editor的实现,大多数用到了如下的一个
很简单,但是非常有效率的实现:
考虑到对于一般的editor,用户要么只是打开文档进行浏览(移动鼠标不算对文档进行
修改),要么是只能在一个地方进行修改(这个是重点!)。也即,我们假设不会有多
个用户对一个文档进行同时的修改。那么实际上只是需要一个buffer就可以了。
所以这个editor其实都有2种模式,一种是阅读模式,一种是修改模式。用户会在这2个
模式之间相互却换。
这个数据结构跟第一版有点类似,把所有的行存在一个Array里面。每一行是一个字符
数组。有一个buffer,设定为初始80大小的字符Array(这个初始大小随便)。
当用户在某个位置开始删除字符的时候,直接把Array里面的对应的那个字符清空,不要
移动后面的字符。也即,HelloWorld,用户删除W之后,存在Array里面的是Hello-orld
。我这里用-来表示W这个字符被删除了。
当用户在某个位置开始插入字符的时候,把新的字符朝buffer里面写。当buffer满,或者
用户结束修改模式的时候,把buffer里面的字符插入Array里面(这里是一个O(N)的操作
,因为要把Array的字符后移)。比如,HelloWorld,用户欲插入the三个字符,在修改模
式下,the是写入buffer。当修改模式结束的时候,the就被插入到了Hello和World之间。
这个数据结构也是假设每一行的长度不会太长。所以O(N)的插入操作是可以接受的。
好了,终极方案,PieceTable,这个数据结构也是MS Word, VS,OpenOffice所使用的。
它支持无限次的redo, undo,对行的长度没有限制。
它用的是一个不同的思路。前面两个数据结构走过来,用的都是一个同样的原理:长的
string不好修改,我就把它砍成几小段,然后每一个小段里面的O(N)操作是可以接受的。这
个PieceTable的思路是,我把string视为一个数据库表存储的数据,然后在上面建立index,
以方面读写。
PieceTable内部分2个存储区域和一个索引区域。第一个区域是只读的,当editor载入新的
文档,文档内容会被保存在这个区域,而且是只读的。第二个区域是一个expandable的数
据结构,用来存储每一次用户插入的字符串。(当用户把光标移到一个位置,开始敲打键盘
输入字符,一直到用户结束修改模式,这算一次插入)。
存储区域的string总是expandable的,里面的字符不会被删除。
假设原本文档是HelloWorld,然后用户在第3位插入了the,那么保存的string会是
HelloWorldthe,在索引区域,产生的PieceTable是 [0-3] ~ [11-13] ~ [4-10]
(Hel the loWorld)
用户的每一次插入操作都会产生一个Piece。用户的一次删除操作就会把一个Piece分裂成2
个Piece。
对于示例HelloWorldthe,PieceTable是 [0-3] ~ [11-13] ~ [4-10]。假设用户删除
了W这个字符,那么PieceTable就变成了 [0-3] ~ [11-13] ~ [4-4] ~ [6-14]。
Piece之间的相对位置是存储在一个索引数据结构里面。对于Piece不多的文档,可以简单的
用LinkedList来做。若是Piece的数量大到一个规模(比如10K左右),就得用Tree了。
当Piece多到一定程度的时候,要进行Merge的操作了,用于降低Piece的数量。而Piece的数
量是和用户的操作数量直接相互关联的。
嗯,大概就解释到这么多了。有兴趣的筒子可以看一些开源editor的源码,比如VIM, Scintilla,
SharpStudio等等。

【在 R**e 的大作中提到】
: 实现一个 text editor, 选用合适的数据结构,和 解释各种功能怎样实现。
: 估计占用的内存空间
: thanks

d**e
发帖数: 6098
3
不错不错

(N

【在 y*********e 的大作中提到】
: 这个我以前写过一个notepad,大概解释一下数据结构吧。
: 我用的是C#写的(C#的string跟Java的string一样,是immutable的)。
: 这个数据结构应该支持如下功能:
: 1、快速的string读取,写入,以及删除
: 2、快速的获得某一个字符所在的行列号
: 3、支持较多的redo、undo
: 对于第一点要求,传统的string肯定不行,因为每次对string的修改都会产生一个新的
: string。StringBuilder也不行,虽然它支持O(1)的Append,但是对于插入和删除最快
: 的还是O(N)。
: 考虑到第二点要求,可以用一个改进版的StringBuilder。即,每一行用一个

R**e
发帖数: 274
4
great! thank you!

【在 y*********e 的大作中提到】
: 这个我以前写过一个notepad,大概解释一下数据结构吧。
: 我用的是C#写的(C#的string跟Java的string一样,是immutable的)。
: 这个数据结构应该支持如下功能:
: 1、快速的string读取,写入,以及删除
: 2、快速的获得某一个字符所在的行列号
: 3、支持较多的redo、undo
: 对于第一点要求,传统的string肯定不行,因为每次对string的修改都会产生一个新的
: string。StringBuilder也不行,虽然它支持O(1)的Append,但是对于插入和删除最快
: 的还是O(N)。
: 考虑到第二点要求,可以用一个改进版的StringBuilder。即,每一行用一个

y*********e
发帖数: 518
5
对于一般的编辑器,用第二种数据结构就足够了。PieceTable的实现太复
杂了,corner case特别多,特容易出bug。
我当初写的notepad也只是用Spanning Buffer做的。曾尝试写过一个
PieceTable类,但结果bug太多最后作罢。
建议读这本书:Dissecting A C# Application。
当初C#才出来的时候,有票人特喜欢C#简介的语言风格,但是痛恶M$收费
的Visual Studio,于是乎就他们动手写了一个开源的版本,功能几乎可
以跟VisualStudio相比肩。
随后他们就写了一本书。书名中的C# Application就是他们做的开源的
IDE,叫做SharpDevelop。现在Mono的MonoDevelop就是基于
SharpDevelop的。书里面详细的介绍了如何写一个Visual Studio规模
的IDE,也对PieceTable数据结构做了详细的解释。
主页是http://www.icsharpcode.net/opensource/sd/
在主页上可以免费下载书的电子PDF版本。

【在 R**e 的大作中提到】
: great! thank you!
P*******b
发帖数: 1001
6
你说的这些数据结构我都没有听过。哎

【在 y*********e 的大作中提到】
: 对于一般的编辑器,用第二种数据结构就足够了。PieceTable的实现太复
: 杂了,corner case特别多,特容易出bug。
: 我当初写的notepad也只是用Spanning Buffer做的。曾尝试写过一个
: PieceTable类,但结果bug太多最后作罢。
: 建议读这本书:Dissecting A C# Application。
: 当初C#才出来的时候,有票人特喜欢C#简介的语言风格,但是痛恶M$收费
: 的Visual Studio,于是乎就他们动手写了一个开源的版本,功能几乎可
: 以跟VisualStudio相比肩。
: 随后他们就写了一本书。书名中的C# Application就是他们做的开源的
: IDE,叫做SharpDevelop。现在Mono的MonoDevelop就是基于

1 (共1页)
进入JobHunting版参与讨论
相关主题
amazon intern 3电微软有组在招new grad software engineer吗?
贴几道某大公司的面试题今天Amazon的phone interview
排列组合害死人啊Topcoder与面试准备
问个string combination的问题今天没心情看书,上来聊聊我这1个半月都干嘛了
问一道A家的面试题问道关于LRU的题目
leetcode 上 wordladderII 求教大家有没有感觉,随着C++的淘汰linked list的问题越来越少了
发个evernote的code challenge发几个狗家onsite题
不明白leetcode OJ wordladder 2 总是 Time Limit Exceededleetcode #220很好
相关话题的讨论汇总
话题: 字符话题: 数据结构话题: piecetable话题: editor话题: piece