顺序表随机访问很快，但在光标附近连续插入字符时，朴素数组每次都可能搬动后缀。本文不用不稳定的墙钟时间，而以“元素移动次数”为压测指标，对比普通连续数组与间隙缓冲区，给出可运行的 Python 模拟器，并分析光标跳跃、扩容和最坏情况。

文本编辑器收到一千次键入，用户体感却偶尔卡顿。若底层把文本保存在普通连续数组中，光标位于中间时，每插入一个字符都要把后半段右移。机器跑分快慢会干扰毫秒数据，但“搬了多少个元素”与硬件无关，能更直接解释算法成本。这次压测只统计逻辑移动次数，不伪造吞吐或延迟。

第一组：普通顺序表的账单

顺序表的优势是第i个元素可O(1)访问，尾部追加在预留容量足够时也是摊还O(1)。但中间插入要移动n-i个元素。若固定在文档中点连续插入m次，移动量接近m*n/2，每次插入后文档变长，账单还会继续增长。

Python 自带列表已经高度优化，但它的底层移动仍存在。为了让计数精确，示例实现两个教学结构：FlatBuffer明确执行插入搬移；GapBuffer在数组中保留一段空隙，光标就是空隙位置。连续键入只消耗空隙，不移动已有字符；光标跳转时才把跨过的字符搬到空隙另一侧。

第二组：把空位留在手边

间隙缓冲区维护[左侧文本][空隙][右侧文本]。逻辑索引小于空隙左端时与物理索引相同，大于等于左端时要加上空隙长度。移动光标到左边，就把空隙左侧字符从后往前搬到右侧；移动到右边则反向搬。空隙耗尽时扩容，复制已有字符并在光标处建立更大空隙。

classFlatBuffer:def__init__(self,text=""):self.data=list(text)self.moves=0definsert(self,pos,ch):ifnot0<=pos<=len(self.data):raiseIndexError(pos)self.moves+=len(self.data)-pos self.data.insert(pos,ch)deftext(self):return"".join(self.data)classGapBuffer:def__init__(self,text="",gap=8):ifgap<=0:raiseValueError("gap must be positive")self.buf=list(text)+[None]*gap self.gap_left=len(text)self.gap_right=len(self.buf)self.moves=0def__len__(self):returnlen(self.buf)-(self.gap_right-self.gap_left)defmove_cursor(self,pos):ifnot0<=pos<=len(self):raiseIndexError(pos)whileself.gap_left>pos:self.gap_left-=1self.gap_right-=1self.buf[self.gap_right]=self.buf[self.gap_left]self.buf[self.gap_left]=Noneself.moves+=1whileself.gap_left<pos:self.buf[self.gap_left]=self.buf[self.gap_right]self.buf[self.gap_right]=Noneself.gap_left+=1self.gap_right+=1self.moves+=1defgrow(self):old_text_right=self.buf[self.gap_right:]extra=max(8,len(self.buf))left=self.buf[:self.gap_left]self.moves+=len(left)+len(old_text_right)self.buf=left+[None]*extra+old_text_right self.gap_right=self.gap_left+extradefinsert(self,pos,ch):self.move_cursor(pos)ifself.gap_left==self.gap_right:self.grow()self.buf[self.gap_left]=ch self.gap_left+=1deftext(self):return"".join(xfori,xinenumerate(self.buf)ifnot(self.gap_left<=i<self.gap_right))defrun_case(initial,pos,typed):flat=FlatBuffer(initial)gap=GapBuffer(initial,gap=max(8,len(typed)))foroffset,chinenumerate(typed):flat.insert(pos+offset,ch)gap.insert(pos+offset,ch)assertflat.text()==gap.text()returnflat,gapif__name__=="__main__":flat,gap=run_case("abcdefghij",5,"XYZ")assertflat.text()=="abcdeXYZfghij"assertflat.moves==15assertgap.moves==5tail_flat,tail_gap=run_case("hello",5," world")asserttail_flat.moves==0asserttail_gap.moves==0jumping=GapBuffer("0123456789",gap=4)jumping.insert(0,"A")jumping.insert(len(jumping),"Z")assertjumping.text()=="A0123456789Z"assertjumping.moves>=20print("middle moves:",flat.moves,gap.moves)print("gap-buffer checks passed")

压测结果怎么读

中间样本从长度 10 的文本位置 5 连续插入三个字符。普通数组每次都要跨过原后缀五个字符，移动计数为 15。间隙初始在文本尾部，只需先把光标移动到位置 5，搬五个字符；之后三次连续键入不再移动，所以计数为 5。尾部追加时两者都无需移动已有字符。

第三个样本故意让光标从尾跳到头、再跳回尾。间隙会跟着光标穿过几乎整段文本，移动量不再占优。这正是它的适用条件：编辑具有局部性，连续操作集中在光标附近。频繁随机多光标编辑、协同编辑或大块结构化修改，绳索树、piece table 等结构可能更合适。

复杂度不是一句 O(1)

在空隙足够且光标不动时，单字符插入是O(1)。移动光标距离d需要O(d)；扩容复制O(n)，但连续局部插入可按几何增长获得摊还效率。随机访问逻辑位置仍可O(1)映射到物理位置。空间为文本O(n)加预留空隙；空隙越大，扩容越少但内存浪费越多。

普通动态数组中间插入最坏O(n)，尾部追加摊还O(1)，随机访问O(1)。因此不能笼统说间隙缓冲区“比数组快”，它其实仍是数组，只是把批量空位主动放在预计的编辑位置。

边界、删除和真实实现

空文本可直接插入，位置必须落在[0,len]。示例只实现插入；删除光标左侧字符可扩大空隙左端，删除右侧字符可扩大空隙右端，不需要搬动其他元素。真实 Unicode 编辑器还要区分代码点、字素簇和 UTF-8 字节偏移，一个屏幕字符不一定对应一个数组元素。

扩容时示例把左右文本各复制一次，并把复制数计入移动账单。初始空隙专门设到足以容纳测试输入，是为了单独观察局部移动；这不是隐藏成本，另一个跳跃样本会触发扩容并计数。若压测比较完整工作负载，应统一初始容量和增长策略。

常见错误包括：移动空隙时覆盖尚未复制的字符；逻辑长度把空隙也算进去；扩容后忘记更新右边界；把毫秒微基准当成复杂度证明；只测连续键入却宣称适合随机编辑；文件保存时把None空隙写入结果。

可复制测试覆盖中间连续插入、尾部追加和长距离跳转。进一步可生成随机的光标移动与插入序列，同时用 Python 字符串或列表作为参考模型，每一步比较完整文本。移动计数负责解释性能，参考模型负责证明内容正确，两类断言缺一不可。

压测的结论不是一个漂亮的耗时数字，而是成本发生的位置：顺序表为每次中间插入反复付后缀搬移费，间隙缓冲区把费用集中到光标移动和扩容。工作负载是否具有局部性，才决定这笔预付账单值不值。

把三种编辑轨迹分开测

第一种是持续尾部输入，普通数组和位于尾部的间隙都几乎不搬已有字符，差别主要来自扩容策略。第二种是固定光标附近输入，普通数组反复移动同一后缀，间隙只在首次定位时付款。第三种是每次在文档两端交替插入，间隙几乎整段往返，移动量可接近每次O(n)，优势消失。

因此压测报告不应只给“插入十万字符”。它还要给初始文本长度、光标位移分布、连续输入批次长度、删除比例和初始空隙。相同操作数在三种轨迹下成本可能相差几个数量级。用真实编辑日志时只需保留位置变化和操作类型，不必保存用户文本内容，也能重放结构性工作负载。

移动计数并不等同于 CPU 指令数。底层memmove搬连续内存可能比 Python 循环移动同样元素快很多，缓存与对象引用也影响耗时。本篇计数用于验证增长趋势和定位成本，实际选型还要在目标语言实现上做基准。基准应预热运行时、重复多轮、报告分位数，并确认两种结构输出完全相同。

删除为何是间隙结构的另一半

退格删除光标左侧字符时，只需让gap_left减一，并清空该槽；Delete 键删除右侧字符则让gap_right加一。两者都扩大空隙，不移动其余字符。连续替换一段文本可以先删除形成空隙，再插入新内容，成本与替换附近的局部性相符。

选区删除若跨越光标两侧，要先把空隙移动到选区边界，再扩大空隙覆盖选区。撤销操作不能只记录最终文本，通常保存操作类型、位置和内容。间隙位置是内部状态，不应进入持久化格式；撤销重做通过逻辑位置重放，结构可以自行决定空隙在哪里。

扩容策略也能影响最坏停顿。示例按当前缓冲区长度增加空隙，属于几何增长；文本较大时一次复制可能造成明显延迟。可以分块存储或在后台准备新块，但这会改变结构。仅把增长改成固定 8 个槽会导致连续输入频繁复制，总成本退化到平方级。

随机访问与行列定位

逻辑索引到物理下标是常数时间，但编辑器常问“第 500 行第 20 列”，不能每次从头数换行符。可额外维护行起点索引、换行统计树或分块摘要。插入换行会更新这些辅助结构，算法成本不再只有字符缓冲区。评估编辑器数据结构时，应把实际查询一起列入，而不是只比较插入。

Unicode 更容易制造错误。UTF-8 中中文字符占多个字节，组合附加符和表情序列又可能由多个代码点组成。按字节移动结构本身没问题，但光标不能落在编码单元中间；按代码点也不一定符合用户看到的字素簇。结构层与文本分段层需要明确边界合同，测试加入多字节字符、组合字符和换行符。

间隙内容应视为未定义，不能依赖全是None才判断空隙。高性能实现可能保留旧字节，只用左右边界界定有效区。保存、搜索和计算长度都必须跳过区间[gap_left,gap_right)；清零只用于调试可见性，不是正确性的依据。

随机模型测试可以维护一个普通字符串oracle。每一步随机选择合法光标，随机插入或删除短文本，然后比较GapBuffer.text()与参考字符串。与此同时检查0<=gap_left<=gap_right<=capacity、逻辑长度公式和空隙外元素顺序。性能计数断言只针对精心设计的轨迹，不要在随机数据上要求固定数字。