南京明辉建设集团网站安阳青峰网站建设

南京明辉建设集团网站,安阳青峰网站建设,淘宝客网站哪里可以做,永久免费域名注册近笔者正在优化 Android 开源代码编辑器项目 TextWarrior 的一些算法#xff0c;包括时间、空间两方面。TextWarroir 的文本编辑器算法采用经典的 GapBuffer#xff0c;其基本思想是利用编辑时的局部性原理#xff0c;在光标处维护一个缓冲区#xff0c;实现高效替换。但是…近笔者正在优化 Android 开源代码编辑器项目 TextWarrior 的一些算法包括时间、空间两方面。TextWarroir 的文本编辑器算法采用经典的 GapBuffer其基本思想是利用编辑时的局部性原理在光标处维护一个缓冲区实现高效替换。但是笔者需要对其代码高亮、自动断行等功能用到的标记数组进行优化原编辑器的代码高亮标记数组直接采用差分数组存储其文本下标好处是文章内容频繁更新时差分数组可以只需要改动其中一两个元素的值便能导致后面整体的改动缺点是查找某个下标时需要从头开始时间复杂度为()O(N)。原编辑器的自动断行标记数组直接存储文本下标好处是定位时可以采用二分查找但是当文本改动时需要对整个数组光标处的后半段进行修改时间复杂度()O(N)。不管是差分数组还是直接存下标貌似都有其缺陷。那有没有一种两全其美的方法呢答案是有的。这要从 GapBuffer 说起。GapBuffer 基本思想GapBuffer 又叫间隙缓冲区是一种文本编辑器算法主要对编辑器中频繁的字符串插入、删除操作进行优化。我们知道对于中间插入数组的时间复杂度为()O(N)而链表的时间复杂度为(1)O(1)。字符串常常用数组的方式存储若采用链表每个字符都会附带一个指针指向下一个字符结点数据冗余度很高。而 GapBuffer 则实现了对于数组高效的中间插入删除。GapBuffer 利用编辑时的局部性——编辑操作在一段时间内往往集中在最初光标附近换位置的情况比较少这一事实——进行优化。GapBuffer 在原字符串数组光标附近维护一个缓冲区即所谓间隙缓冲区后文简称间隙并通过双指针限定该间隙的范围。由于间隙内的内容实际不可见当我通过字符串索引获取字符时需要跳过间隙此时存在一个下标映射将获取字符时的逻辑下标映射到所维护字符数组的实际下标。基本操作局部性编辑当光标位于间隙开始位置时输入时直接将输入内容从间隙开始位置拷贝到间隙并后移起始指针删除时直接前移起始指针。此时时间复杂度为(1)O(1)。跨域编辑若出现跨域编辑即此时光标位置不在间隙开始处则需要进行整体复制以将间隙移动到当前光标处再进行相关操作。时间复杂度()O(m)其中m 表示间隙区移动的距离。若插入时间隙所剩空间不足则需要进行扩容并把间隙后的字符全部向后整体复制。时间复杂度()O(k)其中k 为间隙之后的部分数组长度。插入操作示例插入前|H|e|l|l|o| | | | |W|o|r|l|d|^ Gap (size4)插入后|H|e|l|l|o|!| | | |W|o|r|l|d|^ Gap (size3)删除操作示例删除前|H|e|l|l|o|!| | | |W|o|r|l|d|^ Gap (size3)插入后|H|e|l|l|o|!| | | |W|o|r|l|d|^ Gap (size4)基于下标映射的标记记录法既然 GapBuffer 采用下标映射实现实际下标和逻辑下标的转换而在编辑的过程中某个字符的逻辑下标往往是不断变动的而其实际下标则要稳定得多因此完全可以记录实际下标实现高效率的标记管理。记录实际下标即记录标记在原字符数组中的下标当间隙发生变动时维护下标的映射关系。可以对比逻辑下标和差分下标实际下标映射方式兼具二者有点同时避免了各自的缺陷。下标映射在需要访问下标时会用到 GapBuffer 的下标映射函数将记录的实际下标转为逻辑下标再返回而增加记录时会把逻辑下标转为实际下标进行记录。private ArrayListInteger records;private int mapToReal(int i) {return i gapStart ? i : i gapLength();}private int mapToLogical(int i) {return i gapEnd ? i : i - gapLength();}public void getMark(int i) {return mapToLogical(records.get(i));}public void addMark(int i) {records.add(mapToReal(i));}搜索在需要进行查找时只需要将逻辑下标转为实际下标并应用二分查找即可时间复杂度(log⁡)O(logN)继承了记录逻辑下标的优点而记录差分下标则必须从头遍历累加。public int findMark(int i) {return Collections.binarySearch(records, mapToReal(i));}维护由于记录为实际下标因此维护需保证与 GapBuffer 的一致性。对于间隙维护的三种情况均需考虑其时间复杂度也和三种情况基本对等局部性编辑在间隙开头插入时如果间隙不需要扩容则记录不变如果是删除检查并处理实际下标落入间隙区中的下标移动或删除平均时间复杂度(1)O(1)。由于间隙发生了改变虽然实际下标没有改变但映射函数的参数发生变化因此映射到的逻辑下标会变化。跨域编辑在间隙以外的地方插入或删除此时只需检查移动区间内的下标并加或减去间隙长度再同上处理插入删除情况时间复杂度()O(m)此处m 为移动区间内标记数量。间隙扩容当间隙大小不足插入时需要进行扩容此时需要将间隙之后的所有标记加上扩容量时间复杂度()O(k)此处k 为间隙之后的标记数量。实际下标记录的维护在满足局部性的情况下时间复杂度为(1)O(1)与差分下标记录同级同时避免了逻辑辑下标记录的不足。当然实际下标记录的维护难度要比二者大一些。对比下标记录方法 逻辑下标 差分下标 实际下标访问 直接读取O(1) 前缀和O(n) 线性映射O(1)搜索 二分O(logN) 线性O(n) 二分O(logN)维护 O(k) O(1) O(1),最坏O(k)总结本文讨论文本编辑器经典算法 GapBuffer 的标记记录优化方案利用算法中的局部性思想提出配套的基于映射的下标记录算法并对比了 TextWarrior 用到的两种记录方案表现出该方法在时间复杂度上的优势。另外局部性原理也是很多算法的依据在计算机软硬件设计很多地方都有所体现值得研究。希望本文为读者提供一些参考帮助。